УДК 514.774.8, 519.176

Длина минимального дерева заданной топологии: обобщенная формула Максвелла / А. О. Иванов, А. А. Тужилин. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2010. № 3. С. 7-14.

Классическая формула Максвелла вычисляет длину плоского, локально минимального, бинарного дерева по координатам граничных вершин и направлениям приходящих в них ребер. Однако, если для заданной бинарной структуры соответствующее экстремальное дерево с фиксированной границей имеет вырожденные ребра, классическая формула Максвелла непосредственно неприменима: чтобы вычислить длину экстремального дерева в этом случае, необходимо знать, какие ребра выродились. В настоящей статье мы обобщаем формулу Максвелла на произвольные экстремальные деревья в евклидовом пространстве произвольной размерности: теперь для вычисления длины такого дерева не нужно знать, ни какие ребра выродились, ни направления невырожденных граничных ребер. Ответом является максимальное значение линейной функции на выпуклом компактном подмножестве евклидова пространства, образованном пересечением цилиндров.

Ключевые слова: локально минимальные деревья, проблема Штейнера, формула Максвелла.

Библиогр. 6.