Štajnerovo drvo

Štajnerovo stablo za tri tačke A, B, and C. Štajnerova tačka S se nalazi u Toričelijevoj tački trougla ABC.

Rešenje za 4 tačke—primetimo da postoje dve štajnerove tačke, S₁ i S₂

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).

Pravolinijsko Štajnerovo stablo

Главни чланак: 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.

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.

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)

Aproksimacija Štajnerovog stabla

U opštem grafu Štajnerovog stabla, minimalno razapinjuće stablo indukovono skupom graničnih tačaka $R$ zatvaranja $G_{m}$ of $G$. Ovo stablo je ostvarljivo ali ne obavezno optimalno rešenje problema Štajnerovog stabla. Metričko zatvaranje $G_{m}$ može biti zamenjeno sa $G$ bez umanjenja opštosti, i opisuje se tako što se izmedju svaka dva čvora u ubacuje ivica težine jednake težini najkraćeg puta izmedju njih. Ovakvih ivica ima $|V|*(|V|-1)/2=O(|V|^{2})$, pa se njihove dužine mogu naći u polinomijalnom vremenu primenom Djikstrinog algoritma. Trivijalno se dokazuje da je optimalno rešenje na $Opt_{G}$ optimalno i na $G$.

Minimalno stablo je razapinjuće stablo na potpunom podgrafu metričkog zatvaranja koje sadrži samo granične tačke i ivice koje ih spajaju. Ovakvo stablo je $2-2/|R|$ aproksimacija gde je $|R|$ broj graničnih tačaka.

Š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.

U Euklidskom problemu Štajnerovog stabla, za Štajnerov količnik se samo pretpostavlja da iznosi ${\frac {2}{\sqrt {3}}}$. Uprkos ranijim tvrdnjama o dokazu, pitanje je još otvoreno, U pravolinijskom Štajnerovom stablu , količnik iznosi ${\frac {3}{2}}$.

Извори

• 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 . стр. 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 978-0-444-89098-6. 
• 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 978-5-93972-292-6. 
• Korte, Bernhard; Vygen, Jens (2006). „Section 20.1”. Combinatorial Optimization: Theory and Algorithms (3rd изд.). Springer. ISBN 978-3-540-25684-7. 
• Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 978-3-540-65367-7. 
• 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 978-1-58488-436-1. 
• Bern, Marshall W.; Graham, Ronald L. (1989). „The Shortest-Network Problem”. Scientific American. 260 (1): 84—89. doi:10.1038/scientificamerican0189-84. 
• Cieslik, Dietmar (1998). Steiner Minimal Trees. стр. 319. ISBN 978-0-7923-4983-9. 

Spoljašnje veze

• 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)