Drzewo Steinera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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.