Описание:Цель спецкурса --- познакомить слушателей с геометрическими аспектами теории графов, которые находят приложения в геометрии, топологии и вариационном исчислении, в частности, теории экстремальных сетей. Мы также сформулируем много нерешенных задач, связанных с этой тематикой.
Примерная программа:
(1) Краткое введение в теорию графов. Деревья, остовные деревья, теорема Кирхгофа. Минимальные остовные деревья. Алгоритм Краскала.
(2) Задачи о достижимости и о кратчайшем пути: алгебраический подход. Идемпотентные полукольца, индуктивно упорядоченные множества, теорема о неподвижной точке непрерывного отображения, замкнутые идемпотентные полукольца, решение линейных уравнений, приложения к оптимизационным задачам на графах.
(3) Евклидово минимальное остовное дерево. Триангуляции Делоне и диаграммы Вороного.
(4) Кратчайшие деревья на плоскости. Локальная структура. Алгоритм Мелзака и Хванга--Мелзака на плоскости. Гипотеза Гилберта--Поллака. Что мы знаем и чего не знаем об отношении Штейнера.
(5) Связь геометрии границы с возможным устройством минимальной сети.
(6) Плоские графы. Теоремы Понтрягина--Куратовского и Вагнера (идеи доказательства). Линейные вложения графов в плоскость с предзаданными углами. Графы на поверхностях. Эйлерова характеристика. Род графа.