Drzewo Steinera

Drzewo Steinera dla trzech punktów A, B, C (zauważmy, że nie ma bezpośredniego połączenia pomiędzy A, B, C). Punkt Steinera S jest punktem Fermata trójkąta ABC.
Rozwiązanie dla 4 punktów—zauważmy, że są tu dwa punkty Steinera S1 i S2

Drzewo Steinera dla ustalonego zbioru punktów to najmniejsza figura łącząca te punkty. Nazwa pochodzi od Jakoba Steinera. Znalezienie drzewa Steinera dla ustalonego zbioru punktów jest problemem NP-trudnym.

Linki zewnętrzne

  • Marek Cygan, Drzewo Steinera: jedno zagadnienie, mnóstwo problemów, „Delta”, kwiecień 2011, ISSN 0137-3005 [dostęp 2024-10-28].
This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.