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 S₁ i S₂

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

• MarekM. Cygan MarekM., Drzewo Steinera: jedno zagadnienie, mnóstwo problemów, „Delta”, kwiecień 2011, ISSN 0137-3005 [dostęp 2024-10-28] .