Steinerboomprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Voorbeeld: de Steinerboom voor drie punten A, B en C wordt bekomen met één Steinerpunt S, dat het punt van Fermat is van de driehoek ABC.
De Steinerboom voor vier punten A, B, C en D. Er zijn twee Steinerpunten gebruikt.

Het (minimale) Steinerboomprobleem is een wiskundig probleem uit de grafentheorie. Het is een veralgemening van het probleem van de minimaal opspannende boom. Daarin zoekt men voor een gegeven verzameling van punten in het tweedimensionele vlak een boom (een graaf zonder cycli), waarvan de knopen de gegeven punten zijn en waarvan de som van de lengten van de takken minimaal is.

Definitie[bewerken]

In het Steinerboomprobleem, genoemd naar Jakob Steiner, zoekt men ook voor een gegeven verzameling van punten een boom met de kleinste lengte. Het verschil met het probleem van de minimaal opspannende boom is, dat men nu bijkomende knopen en takken aan de boom mag toevoegen om de lengte ervan nog te verkleinen. Men noemt deze bijkomende knopen Steinerpunten en de resulterende graaf is de Steinerboom. Voor een gegeven verzameling van punten kunnen er meerdere Steinerbomen bestaan.

Men kan bewijzen dat een Steinerboom van een verzameling van n punten, ten hoogste n-2 Steinerpunten heeft. Alle Steinerpunten liggen binnen het convex omhulsel van de puntenverzameling.[1] In elk Steinerpunt van een minimale Steinerboom komen drie takken samen die met elkaar een hoek van exact 120° maken.

Analogie[bewerken]

Een Steinerboom kan met een zeepbelanalogie gevisualiseerd worden. Stel twee evenwijdige glasplaten voor die door een aantal staven loodrecht op de platen verbonden zijn. Elke staaf stelt in bovenaanzicht een gegeven punt voor. Wanneer men het geheel in een zeepoplossing onderdompelt en er weer uithaalt, ontstaat tussen de staven een zeepvlies dat in bovenaanzicht een minimale Steinerboom is.[1]

Complexiteit[bewerken]

In het algemeen is het Steinerboomprobleem NP-compleet; het is trouwens een van de 21 NP-complete beslissingsproblemen die Richard Karp in 1972 opsomde. Net als voor andere NP-complete problemen kan er voor een Steinerboomprobleem met een beperkt, klein aantal knopen een optimale oplossing gevonden worden, maar in het algemeen gebruikt men heuristieken om een goede, maar niet noodzakelijk de beste, oplossing te vinden in een aanvaardbare rekentijd.

De minimaal opspannende boom, die wel kan bepaald worden in polynomiale tijd, kan overigens dienen als een eerste benadering van de minimale Steinerboom. Het vermoeden van Gilbert en Pollak, geformuleerd in 1968, stelt dat de verhouding van de lengten van de minimale Steinerboom en de minimaal opspannende boom voor eenzelfde verzameling punten in het Euclidische vlak, altijd groter dan of gelijk is aan  \frac{\sqrt{3}}{2}. Deze verhouding noemt men de Steinerverhouding.[2] Als dit vermoeden waar is, is de lengte van de minimaal opspannende boom dus een overschatting van de lengte van de minimale Steinerboom met hooguit \frac{2}{\sqrt{3}} - 1 of ongeveer 15,47 percent. In 1990 publiceerden Du en Hwang een bewijs van dit vermoeden.[3] Maar later is aangetoond dat een van de aannames in hun bewijs onterecht was. Het vermoeden van Gilbert en Pollak zou dus nog open staan.[4]

Algoritmen[bewerken]

Zdzislaw Alexander Melzak publiceerde het eerste eindige, zij het niet efficiënte, algoritme voor het Steinerboomprobleem.[5]

Latere algoritmes zijn er van onder meer Pawel Winter[6], Dan Trietsch en Frank Hwang.[7], Warren D. Smith,[8] en François Chapeau-Blondeau, Fabrice Janez en Jean-Louis Ferrier.[9]

Toepassingen[bewerken]

Het Steinerboomprobleem komt onder meer voor bij het ontwerp van wegen- en telecommunicatienetwerken en de layout van geïntegreerde schakelingen. In dit laatste geval is er meestal een bijkomende randvoorwaarde, namelijk dat de kanten van de Steinerboom enkel horizontaal of verticaal kunnen lopen. Deze versie van het Steinerboomprobleem noemt men het "Rechtlijnige Steinerboomprobleem". Hiervoor gebruikt men de Manhattan-metriek als maat van de afstand in plaats van de Euclidische afstand.

Bronnen, noten en/of referenties
  1. a b uit een lezing van prof. dr. J.H. van Lint, 26 april 1967, Stichting Mathematisch Centrum Amsterdam
  2. E.N. Gilbert en H.O. Pollak. "Steiner Minimal Trees." SIAM J. Appl. Math. Vol. 16 No. 1, pp. 1-29 (1968). DOI:10.1137/0116001
  3. D.-Z. Du en F. K. Hwang. "The Steiner ratio conjecture of Gilbert and Pollak is true." Proc. Natl. Acad. Sci. USA, Vol. 87, pp. 9464-9466 (December 1990)
  4. Innami, N., Kim, B., Mashiko, Y., Shiohama, K. "The Steiner Ratio Conjecture of Gilbert-Pollak May Still Be Open." Algorithmica, Vol. 57 Nr. 4, pp. 869-872 (2010) DOI:10.1007/s00453-008-9254-3
  5. Z.A. Melzak, "On the problem of Steiner", Canad. Math. Bull. 4 (1961), blz. 143-148
  6. P. Winter, "An algorithm for the Steiner problem in the Euclidean plane", Networks, vol. 15 (1985), blz. 323-345 DOI:10.1002/net.3230150305
  7. D. Trietsch, F.K. Hwang, "An improved algorithm for Steiner trees", SIAM J. Appl. Math. 50 (1990), blz. 244-263. DOI:10.1137/0150015
  8. W. D. Smith, "How to find Steiner minimal trees in Euclidean d-space?" Algorithmica 7 (1992), blz. 137-177 DOI:10.1007/BF01758756
  9. Chapeau-Blondeau, F., Janez, F., en Ferrier, J. "A Dynamic Adaptive Relaxation Scheme Applied to the Euclidean Steiner Minimal Tree Problem", SIAM Journal on Optimization 7 (1997), blz. 1037-1053 DOI:10.1137/S1052623494275069