Štajnerovo drvo — разлика између измена

Садржај обрисан Садржај додат

Инлајн

Верзија на датум 13. мај 2014. у 22:26

Problem Štajnerovog stabla, ili najmanjeg Štajnerovog stabla, nazvanog po Jakobu Štajneru, je problem iz kombinatorike i optimizacije, koji se može formulisati na više načina, kojima je zajedničko da se traži najkraća veza između datih objekata.

Problem Štajnerovog drveta sličan je problemu najmanjeg razapinjućeg stabla problem: dati set V tačaka (čvorova)treba povezati (napraviti Graf) najmanje dužine, gde je dužina zbir dužina svih ivica. Razlika između Štajnerovog drveta i najmanjeg razapinjućeg drveta je u tome što se u Štajnerovo drvo mogu ubaciti dodatni(pomoćni) čvorovi i ivice kako bi se smanjila dužina razapinjuceg stabla. Ovakvi čvorovi, koji se dodaju zarad smanjivanja ukupne dužine stabla zovu se Štajnerove tačke ili Štajnerovi čvorovi. Dokazano je da se ovim postupkom dolazi do stabla, poznatog kao Štajnerovo stablo. Za zadati set tačaka može postojati više Štajnerovih stabala.

Većina verzija problema Štajnerovog drveta je NP kompletna.Čak se jedna verzija nalazi medju Karpovih 21 NP-kompletih problema. Neke uprošćene verzije mogu se rešiti u polinomijalnom vremenu.

Euklidsko Štajnerovo drvo

Originalni problem je bio formulisan onako kako sada formulisemo Problem Euklidskog Štajnerovog stabla ili geometrijskog Štajnerovog stabla: za N tačaka ravni, cilj je povezati ih tako da su svake dve povezane ili direktno ili preko drugih tačaka.

Može se dokazati da se tako dobijene ivice ne seku sem u čvorovima, i da je rezultat stablo.

Za problem euklidskog Štajnerovog stabla, čvorovi koji se dodaju grafu (Štajnerovi čvorovi) moraju imati stepen 3, i susedne ivice koje polaze iz tog čvora moraju medjusobno zaklapati uglove od 120 stepeni. Sledi da je maksimalan broj Štajnerovih čvorova N − 2, gde je N broj na početku zadatih čvorova.

Za N = 3 postoje dva moguća slučaja:ako su uglovi trougla koji formiraju zadate tačke manji od 120 stepeni, Štajnerova tačka se poklapa sa Toričelijevom tačkom tog trougla; u suprotnom ivice grafa su stranice trogla koje zaklapaju ugao veći od 120 stepeni.

Za opšte N, problem Euklidskog Štajnerovog stabla je NP težak problem, i zato se ne zna da li se da li se optimalno resenje može naci u polinomijalnom vremenu. Doduše u polinomijalnom vremenu se može naći aproksimacija optimalnog resenja(približno optimalno rečenje).^[1]

Pravolinijsko Štajnerovo stablo

Ovaj problem je varijanta Euklidskog poblema samo sto su euklidske razdaljine zamenjene takozvanim pravolinijskim rastojanjem(zbir apsoutnih razlika x i y koordinata tačaka).

Uopštenje najmanjeg Štajnerovog stabla

Štajnerova stabla se takože izučavaju u oblasti težinskih grafova(drafova čije grane imaju težinu ). U opštem problemu Štajnerovog stabla yadat nam je težinski graf G = (V, E, w) i podskup čvorova S ⊆ V. Štajnerovo stablo je stablo uGkoje sadrži sve čvorove iz S. Postoje dve verzije prblema:u prvoj (problemu optimizacje), cilj je pronaći Štajnerovo stablo sa najmanjom težinom; u drugom (problemu odlučivanja), za zadatu vrednost ktreba da proverimo da li postoji Štajnerovo stablo sa težinom ne većom od k exists. Problem odlučivanja je bio jedan od Karpovih 21 NP-kompletih problema.

Specijalan slučaj problema je kada je G kompletan graf i težine ivica zadovoljavaju nejednakost trougla.Ova verzija je poznata kao metrička varijanta problema Štajnerovog stabla. Za zadati primer (nemetričkog) Štajnerovog stabla možemo naći ekvivalentan primer metričkog Štajnerovog stabla, u polinomijalnom vremenu, transformacija čuva faktor aprofsimacije.^[2]

Problem Štajnerovog stabla jr takože izučavan u drugim dimenzijama i na različitim povrčinama. Algoritmi za pronalaženje najmanjeg Štajnerovog stabla pronaćeni su i za sferu, projektivnu ravan, konus i druge.^[3]

Druga uopštenja problema su ona gde se traži graf koji ostaje povezan kada se iz njega ukloni ne više bilo kojizan kada se ukloni ne vise od k bilo kojih čvorova, za neko k.(k-edge-connected graph i k-vertex-connected graph)

Štajnerov količnik

Štajnerov količnik je supremum količnika ukupne dužine minimalnog Štajnerovog stabla i minimalnog razapinjućeg stabla za zadat set tačaka u Euklidskoj ravni.^[4]

U Euklidskom problemu Štajnerovog stabla, za Štajnerov količnik se samo predpostavlja da iznosi  ${\frac {2}{\sqrt {3}}}$ . Uprkos ranijim tvrdnjama o dokazu, pitanje je jos otvoreno,^[5] the conjecture is still open.^[6]

U pravolinijskom Štajnerovom stablu , količnik iznosi ${\frac {3}{2}}$ .

Notes

^ Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000). „A Compendium of NP Optimization Problems” |contribution= игнорисан (помоћ).
^ Vazirani 2003, стр. 27–28.
^ Dingzhu Du, Frank Hwang (1995). Computing in Euclidean geometry. Lecture Notes of Computing. 4 (2nd изд.). River Edge, NJ: World Scientific Publishing Co. ISBN 981-02-1876-1. , p. 361
^ Ganley, Joseph L. (2004). „Steiner ratio”. Ур.: Black, Paul E. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Приступљено 2012-05-24 .
^ The New York Times, Oct 30, 1990, reported that a proof had been found, and that Ronald Graham, who had offered $500 for a proof, was about to mail a check to the authors.
^ Ivanov, A. O. (2012). „The Steiner Ratio Gilbert–Pollak Conjecture Is Still Open: Clarification Statement”. Algorithmica. 62 (1-2): 630—632. doi:10.1007/s00453-011-9508-3. Приступљено 1. 3. 2012. Непознати параметар |coauthors= игнорисан [|author= се препоручује] (помоћ)

Reference

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5 , p. 208–209, problems ND12 and ND13.
F. K. Hwang, D. S. Richards, P. Winter (1992). The Steiner Tree Problem. Annals of Discrete Mathematics. 53. North-Holland: Elsevier. ISBN 0-444-89098-X.
A. O. Ivanov, A. A. Tuzhilin (1994). Minimal Networks: The Steiner Problem and Its Generalizations. N.W., Boca Raton, Florida: CRC Press. ISBN 978-0-8493-8642-8.
A. O. Ivanov, A. A. Tuzhilin (2000). Branching solutions to one-dimensional variational problems. Singapore-New Jersey-London-Hong Kong: World Scientific. ISBN 978-981-02-4060-8.
A. O. Ivanov, A. A. Tuzhilin (2003). Extreme Networks Theory (на језику: руски). Moscow-Izhevsk: Institute of Computer Investigations. ISBN 5-93972-292-X.
Korte, Bernhard; Vygen, Jens (2006). „Section 20.1”. Combinatorial Optimization: Theory and Algorithms (3rd изд.). Springer. ISBN 3-540-25684-9.
Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8.

Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander (2009). „1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2”. Lecture Notes in Computer Science. 5664: 86—97. doi:10.1007/978-3-642-03367-4_8.

Wu, Bang Ye; Chao, Kun-Mao (2004). „Chapter 7”. Spanning Trees and Optimization Problems. Chapman & Hall/CRC. ISBN 1-58488-436-3.
Bern, Marshall W.; Graham, Ronald L. (1989). „The Shortest-Network Problem”. Scientific American. 260 (1): 84—89. doi:10.1038/scientificamerican0189-84.
Dietmar Cieslik (1998). Steiner Minimal Trees. стр. 319. ISBN 0-7923-4983-0.

External links

Hazewinkel, M. (2001). „Steiner tree problem”. Ур.: Hazewinkel Michiel. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104.
M. Hauptmann, M. Karpinski (2013): A Compendium on Steiner Tree Problems
GeoSteiner (Steiner tree solver, Source available, for non commercial use)
http://www.archive.org/details/RonaldLG1988 (Movie: Ronald L Graham: The Shortest Network Problem (1988)
Fortran subroutine for finding the Steiner vertex of a triangle (i.e., Fermat point), its distances from the triangle vertices, and the relative vertex weights.
Phylomurka (Solver for the Steiner tree problem in networks)

[1] Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000). „A Compendium of NP Optimization Problems” |contribution= игнорисан (помоћ).

[2] Vazirani 2003, стр. 27–28.

[3] Dingzhu Du, Frank Hwang (1995). Computing in Euclidean geometry. Lecture Notes of Computing. 4 (2nd изд.). River Edge, NJ: World Scientific Publishing Co. ISBN 981-02-1876-1. , p. 361

[4] Ganley, Joseph L. (2004). „Steiner ratio”. Ур.: Black, Paul E. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Приступљено 2012-05-24 .

[5] The New York Times, Oct 30, 1990, reported that a proof had been found, and that Ronald Graham, who had offered $500 for a proof, was about to mail a check to the authors.

[6] Ivanov, A. O. (2012). „The Steiner Ratio Gilbert–Pollak Conjecture Is Still Open: Clarification Statement”. Algorithmica. 62 (1-2): 630—632. doi:10.1007/s00453-011-9508-3. Приступљено 1. 3. 2012. Непознати параметар |coauthors= игнорисан [|author= се препоручује] (помоћ)

[1]

[2]

[3]

[4]

[5]

[6]