Деревья Штейнера: различия между версиями

Хорошо известной задачей является гипотеза Гилберта-Поллака об отношении Штейнера, представляющем собой минимальное отношение длин между минимальным деревом Штейнера и минимальным остовным деревом на том же множестве точек. Гилберт и Поллак в 1968 году предположили, что отношение Штейнера на евклидовой плоскости равно <math>\sqrt{3} / 2 \;</math> и достигается для трех вершин равностороннего треугольника. Доказательству этой гипотезы было посвящено множество работ, в конечном итоге ее доказали Ду и Хван [7].