Семинар по Геометрии

Очередное заседание состоится в четверг, 22 февраля 2007 года, в 18.30
в МЦНМО (Большой Власьевский пер. д.11).

Тема: «Экстремальные сети. Проблема Штейнера и ее обобщения ».

Докладчики: А.О.Иванов, А.А.Тужилин (МГУ).

Аннотация доклада:

Проблема Штейнера состоит в поиске кратчайшего связного плоского графа (плоской сети), содержащего все точки заранее заданного конечного подмножества плоскости (граничного множества). Простейшая версия этой проблемы возникла еще у Ферма, который интересовался тем, куда на плоскости нужно поместить точку, чтобы суммарное расстояние от нее до трех фиксированных точек плоскости было бы наименьшим. Одна из естественных интерпретаций проблемы Штейнера – это построение кратчайшей сети дорог, соединяющей данные конечные пункты, например города. Предполагая, что издержки на прокладку дорог пропорциональны длине искомой сети, получаем вполне осмысленную экономическую интерпретацию, называемую транспортной задачей.

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

Приведем некоторые задачи теории экстремальных сетей:

• разработка алгоритмов построения искомых сетей (на плоскости, например, имеется алгоритм Мелзака-Ду-Хванга поиска кратчайшей сети);
• определение сложности (например, в случае плоскости доказано, что проблема Штейнера является NP-трудной, т.е., скорее всего, не существует полиномиального алгоритма, решающего эту задачу);
• поиск приближенного решения (простейшим приближенным решением являются минимальные остовные деревья, которые минимизируют длину в классе всех связных остовных графов, построенных на граничном множестве);
• оценка точности приближения (мера относительной ошибки при замене кратчайшего дерева на минимальное остовное называется отношением Штейнера, вычисление которого – крайне нетривиальная задача);
• изучение того, какие ограничения накладывает геометрия граничных множеств на возможные структуры экстремальных сетей (например, связь числа вращения плоского локально минимального бинарного дерева с числом уровней выпуклости граничного множества);
• изучение локальной структуры экстремальных сетей (как выглядят сети в окрестностях своих вершин);
• изучение глобальной структуры экстремальных сетей (классификация экстремальных сетей для границ заданного типа, например образующих множества вершин плоских выпуклых многоугольников);
• изучение единственности (например, единственность кратчайших сетей для границ общего положения);
• изучение того, как меняется структура экстремальных сетей при изменении граничного множества (теория бифуркаций);
• изучение устойчивости сетей (неустойчивость означает, что сколь угодно малой деформацией сети можно уменьшить ее длину);
• изучение связи геометрии экстремальных сетей с геометрией объемлющего пространства.

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

Приглашаются все желающие.