О планарности оснащенных 4-валентных графов|Василий Мантуров|Лекция №25

Общеизвестна теорема Понтрягина-Куратовскго: граф можно нарисовать на плоскости, если он "не содержит графов" K_{5} и K_{3,3}. Мы рассматриваем оснащенные 4-графы, т.е. графы, в каждой вершине которых сходится 4 ребра, при этом строго фиксируется, какие ребра следует считать противоположными. При рисовании таких графов на плоскости формальная "противоположность" ребер в вершинах должна согласовываться со структурой, диктуемой плоскостью. В ноябре 2004 академик РАН В.А.Васильев выдвинул гипотезу, которую автор доказал в тот же день: оснащенный 4-граф нельзя нарисовать на плоскости, если он содержит два цикла без общих ребер, имеющих единственное трансверсальное перекрестие. То есть два цикла могут иметь общие вершины, в которых каждый из циклов формально переходит с ребра на "не противоположное", но не наоборот. Фактически, в мире "оснащенных 4-графов" "запрещенным" является только граф, у которого единственная вершина и два цикла, проходящие трансверсально через эту вершину. Тем самым, набор "запрещенных" графов меньше (один, а не два), да и сами графы проще, чем в общем случае. Доказательство теоремы Понтрягина-Куратовского можно свести к гипотезе Васильева. Будет рассказано о ряде задач, связанных с оснащенными четырехвалентными графами, в частности сформулирована глобальная проблема: какие вопросы из теории графов можно решать с помощью оснащенных 4-валентных графов? Предварительных знаний не требуется (но на неделе мы выложим несколько материалов лектора, с которыми можно будет ознакомиться). Василий Мантуров — профессор МФТИ, специалист по геометрии и топологии, автор книг по теории узлов. 00:00:00 четырёхвалентные графы 00:12:20 гипотеза Васильева 00:23:50 поворачивающие обходы 00:28:50 структура источник-сток 00:40:00 перерыв 00:44:20 хордовые диаграммы 00:48:30 доказательство гипотезы 01:06:30 ответы на вопросы Страничка семинара turing.tilda.ws/lectures