Назовем паутиной объединение конечного множества отрезков в пространстве. Длина паутины — сумма длин составляющих ее отрезков.
В пространстве (более простой вариант — на плоскости) дано конечное множество точек с целочисленными декартовыми координатами. Нужно найти длину кратчайшей паутины, в которой можно найти путь, соединяющий любые две из данных точек.
(Концы отрезков, составляющих паутину не обязательно принадлежат исходному множеству точек.)
Здравствуйте, nikov, Вы писали:
N>Назовем паутиной объединение конечного множества отрезков в пространстве. Длина паутины — сумма длин составляющих ее отрезков. N>В пространстве (более простой вариант — на плоскости) дано конечное множество точек с целочисленными декартовыми координатами. Нужно найти длину кратчайшей паутины, в которой можно найти путь, соединяющий любые две из данных точек. N>(Концы отрезков, составляющих паутину не обязательно принадлежат исходному множеству точек.)
Дерево Штейнера? целочисленность идет лесом(!?).
N>Признаюсь, что я пока не могу решить эту задачу.
Здравствуйте, 67108864, Вы писали:
6>Дерево Штейнера?
А интересно, для случая 3-х мерного пространства дерево Штейнера может содержать точки Штейнера 4-й степени (соединяющие 4 ребра)? На плоскости вроде бы только 3 степень получается.
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, 67108864, Вы писали:
6>>Дерево Штейнера?
N>А интересно, для случая 3-х мерного пространства дерево Штейнера может содержать точки Штейнера 4-й степени (соединяющие 4 ребра)? На плоскости вроде бы только 3 степень получается.
Запросто, возьмем четыре точки в вершинах тетраэдра и его центр...
Здравствуйте, Chorkov, Вы писали:
N>>А интересно, для случая 3-х мерного пространства дерево Штейнера может содержать точки Штейнера 4-й степени (соединяющие 4 ребра)? На плоскости вроде бы только 3 степень получается.
C>Запросто, возьмем четыре точки в вершинах тетраэдра и его центр...
Там угол между ребрами будет arccos (-1/3), что примерно 109 градусов. Если разделить вершину на две с перемычкой и сделать все углы по 120, должно быть покороче.
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, Chorkov, Вы писали:
N>>>А интересно, для случая 3-х мерного пространства дерево Штейнера может содержать точки Штейнера 4-й степени (соединяющие 4 ребра)? На плоскости вроде бы только 3 степень получается.
C>>Запросто, возьмем четыре точки в вершинах тетраэдра и его центр...
N>Там угол между ребрами будет arccos (-1/3), что примерно 109 градусов. Если разделить вершину на две с перемычкой и сделать все углы по 120, должно быть покороче.
Да неподумал.
Меняю ответ на противоположенный.
Лемма: среди любых череырех точек на поверхности единичной сферы найдуться две
точки A и B, такие что угол AOB меньше 2/3 pi.
Доказательсво лемы:
Пусть существую такие четыре точки ( W X Y Z ) на единичной сфере, что AOB > 2/3 pi.
Без нарушени можно полагать , что W==(-1,0,0). (W.x==-1, W.y==0, W.z==0) (Разворот сферы отностительно ее центра.)
Тогда координаты XYZ удовлетворяю неравенству: x>=1/2.
Также без нарушения общности можно полагать, что X.y==0 && X.z<0. (Разворот относительно оси x.)
Тогда из выражения |XY|<2 sqtr(3/2) и |XZ|<2 sqtr(3/2), для того чтобы точки Y и Z существовали ,
X==(1/2, 0, -sqrt(3/2)), а точки Y==Z==(1/2, 0, sqrt(3/2)). Но это (от, что Y и Z совпадают) противоречит
ограничению на угол YOZ. Противоречие.
Теорема:
Сеть Штейнера не может иметь узлов более чем третьего порядка.
Д-во:
Пусть у нас есть узел чтвертого порядка O связанный ребрами с узлами ABCD.
Обозначим r — длинна самого короткого из ребер OA, OB, OC, OD.
Обозначим A', B', C', D' -точки пересечения ребер, со сферой радиуса r и центром в O.
Согласно леме среди этих точек найдется две тиакх что X'0Y' меньше 2/3 pi.
Тогда на биссектриссе этого удла найждется точка O', такя что X'0'Y' = 2/3 pi.
Очевидно |X'O'|+|Y'O'|+|OO'| < |Y'O|+|X'O|, следовательно исходная сеть не кратчайшая.
.
Перекуём баги на фичи!
