Š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, S1 i S2

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[уреди]

Vista-xmag.png За више информација погледајте чланак Rectilinear Steiner tree

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 = (VEw) 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)

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.[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 još otvoreno,[5][6] U pravolinijskom Štajnerovom stablu , količnik iznosi \frac{3}{2}.

Reference[уреди]

  1. ^ Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000). „A Compendium of NP Optimization Problems“Шаблон:Inconsistent citations .
  2. ^ Vazirani 2003, стране 27–28.
  3. ^ Dingzhu Du, Frank Hwang (1995). Computing in Euclidean geometry. Lecture Notes of Computing. 4 (2nd ed.). River Edge, NJ: World Scientific Publishing Co. ISBN 981-02-1876-1. , p. 361
  4. ^ Ganley, Joseph L. (2004). „Steiner ratio“. In Black, Paul E.. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology Приступљено 24. 5. 2012.Шаблон:Inconsistent citations .
  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.; A. A. Tuzhilin (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.. 
  • 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. 

Spoljašnje veze[уреди]