На главную страницу ЛШСМ-2005

Аркадий Борисович Скопенков

Введение в топологическую теорию графов

А.Б.Скопенков планирует провести 4 занятия.

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

Любому участнику Летней Школы достаточно знаний для овладения этим курсом. Однако предполагается, что участники либо имеют опыт работы с графами, либо готовы потратить много времени и сил на приобретение такого опыта в Летней Школе. Большая часть материала будет преподноситься в виде задач. Будет предложено также много задач для исследования.

Примерная программа

(с запасом: несколько первых или несколько последних тем могут быть опущены по желанию слушателей)

1. Формула Эйлера для плоских графов. Следствия: непланарность полного пятивершинника и теорема о пяти красках.
2. Простое доказательство критерия Куратовского планарности графов.
3. Классификации Маклейна-Эдкисона и Уитни узлов из графов на плоскости.
4. Основная теорема топологии и классификация отображений графов в плоскость с непересекающимися образами. Орнаменты.
5. Узкие деревья на плоскости. Теорема Мура о несчетных семействах триодов на плоскости и ее обобщения.
6. Аппроксимируемость вложениями путей и циклов на плоскости: препятствие Ван Кампена и теоремы М.Скопенкова.
7. Спроектированные вложения графов в плоскость: препятствие Ван Кампена.