Аннотация:Работа посвящена моделированию оптимальных геометрических графов с помощью шарнирных механизмов. Особое внимание уделяется графам, являющимся критическими точками функционалов взвешенной длины (при заданной структуре графа) и абсолютным минимумам функционала длины (при заданной границе связных графов). В первом случае теорема о локальной структуре таких графов описывает, под какими углами соединяются смежные ребра (эти углы вычисляются через веса ребер, причем если степени вершин не превосходят трех, то углы определяются однозначно). Во втором случае из всевозможных структур деревьев, соединяющих данное граничное множество, нужно выбирать те, для которых кратчайшие деревья этой структуры (здесь минимизация происходит по расположению неграничных вершин) будут иметь наименьшую возможную длину по всем структурам. Известно, что в последнем случае можно ограничиться деревьями, у которых имеются лишь вершины степени 1, 2 и 3, причем вершины степени 1 и 2 составляют граничное множество. Отметим, что при таких ограничениях и заданном числе граничных вершин имеется лишь конечное число описанных только что структур деревьев.
Для решения первой строятся геометрические реализации (в виде линейных графов в евклидовом пространстве) произвольных графов, для которых, в качестве ограничения, заданы углы между некоторыми парами смежных ребер, а длина ребер может независимо меняться (в некоторых допустимых пределах).
Для решения второй задачи
1) для заданного множества точек плоскости и структуры дерева Штейнера, соединяющего эти вершины, строятся вершины погруженного в плоскость дерева этой структуры, причем так, что в случае, когда структура реализуется в виде локально минимального дерева, результатом построения является как раз оно (работает алгоритм Мелзака);
2) для произвольного погруженного дерева строится отрезок, длина которого равна длине этого дерева;
3) для конечного семейства отрезков строится семейство отрезков тех же длин, и эти последние отрезки располагаются в трехмерном пространстве в горизонтальных плоскостях так, чтобы более короткие отрезки находились в плоскостях с меньшей аппликатой (отрезки, имеющие одинаковые длины, попадают в одну и ту же плоскость); при этом плоскость с наименьшей аппликатой заранее фиксирована;
4) построенные в пункте 1) деревья перемещаются в те же плоскости, в которых лежат соответствующие им отрезки.
Таким образом, кратчайшие деревья, т.е. минимальные деревья Штейнера (точнее, все их вершины), оказываются в заранее заданной плоскости (с самой маленькой аппликатой). Кроме того, название каждой вершины содержит информацию как о принадлежности вершины к тому или иному минимальному дереву Штейнера, так и то, с какими другими вершинами она соединена (тем самым, в названиях вершин закодирована и топология минимальных деревьев Штейнера).
Заметим, что граничные вершины могут независимо друг от друга менять свое начальное расположение, так что построенный М.Ю.Житной механизм реализует минимальные деревья Штейнера для всех классов подобия граничных вершин, т.е. фактически дает полное решение проблемы Штейнера в терминах шарнирных механизмов. В действительности, работа еще более общая: ведь разработанная техника может быть применена не только к семейству деревьев, кратчайшие из которых являются минимальными деревьями Штейнера, а вообще к произвольным семействам таких деревьев; при этом, не обязательно искать самое короткое из деревьев (можно, например, строить дерево максимальной длины).