На день Пи мы предложили задачку: классифицировать все правильные графы. Решений пришло не очень много, но все они, к сожалению, оказались неправильными. Большинство не смогло доказать, что других графов, кроме классических, циклов и двойственных им не существует. Одно решение продвинулось достаточно далеко, однако автор не доказал, что представленным тройкам не соответствует ни один граф. На самом деле, конечно, суть задачи была в разборе довольно большого числа - в нашем случае 17 - случаев. Перейдем, собственно, к решению.
Прежде, чем решать, напомним основные понятия. Граф называется планарным, если его можно изобразить на плоскости набором точек, которые соединены ребрами без самопересечений. Мы считаем, что в графе нет внутренних ребер, то есть ребер, к которым с двух сторон прилегает одна и та же грань. Кроме этого в графе нет вершин степени один.
Если дан граф G, то к нему можно построить двойственный граф. Делается так: сначала выбираем на каждой грани точку. Соединяем две точки, если у граней есть общее ребро. Легко проверяется, что двойственный к планарному графу тоже планарен. Планарный граф называется правильным, если у всех вершин одинаковые степени, равно как и у всех граней. Обозначим первое число через a, а второе через b.
Для решения задачи нам потребуется одно нетривиальное утверждение, известное как теорема Жордана.
Теорема Жордана: Замкнутая непрерывная кривая на плоскости без самопересечений разбивает плоскость на две части. При этом один кусок оказывается ограничен — он называется внутренним. Другой неограничен и называется внешним.
Теорема сложная, поэтому ссылаемся на нее без доказательства. Второе утверждение, которым мы воспользуемся при решении, называется леммой об AB-обходе. Ее мы докажем.
Лемма об AB-обходе: Пусть у нас есть планарный связный граф, степени всех вершин которого как минимум два. Выберем произвольную упорядоченную пару вершин A и B, соединенную ребром. Определим AB-обход следующим образом:
Утверждается, что:
Доказательство. На плоскости есть ориентация, то есть определено вращение по часовой или против часовой стрелки. Если взять любую грань, то на ее границе можно задать направление обхода. Если выбрать это направление по часовой стрелке, то при таком обходе грань остается всегда справа.
Покажем теперь, что с нашим алгоритмом обхода мы всегда остаемся на границе грани. Действительно, пусть после некоторой вершины мы сошли с грани. Без ограничения общности пусть это произошло после первого шага. То есть из B выходит два ребра — BC и BD — одно из которых представляет собой продолжение границы грани (скажем, BD), а другое — ребро, по которому мы пошли (это BC).
Посмотрим, в каком порядке, начиная с AB, эти ребра идут вокруг B, если считать против часовой стрелки. По нашему алгоритму порядок может быть только AB, BC, BD. Заметим, что если идти по границе, то ребро BC окажется справа, а, значит, целиком лежит в границе. В частности, к нему с двух сторон прилегает одна и та же грань, что противоречит нашим условиям. Лемма доказана.
Сначала разберем несколько простых случаев.
Мы такой случай запрещали, но, все равно, разберем его. Возьмем любую вершину. Из нее выходит ребро. Оно заходит в другую вершину. То есть граф представляет собой несвязное объединение «отрезков».
Выберем произвольную вершину и начнем двигаться по графу. После каждого шага возможны два варианта:
Если имеет место второй вариант, то из вершины выходит ровно одно ребро, по которому мы еще не ходили. Так как количество вершин конечно, получаем, что в какой-то момент мы вернулись в первоначальную точку.
В общем случае мы получили, что наш граф распался на насвязное объединение циклов. Так как число циклов конечно, то есть хотя бы одинцикл, внутри которого ничего не лежит. Возьмем его. Если таких несколько, возьмем любой.
Пусть выбранный цикл состоит из n ребер. Выберем теперь связный кусок плоскости, который прилегает в выбранному циклу снаружи. Граница этого куска состоит из нашего цикла и, возможно, еще чего-то. Если это что-то не пусто, то порядок такой грани строго больше n.
Значит, в этом случае граф состоит из одного единственного цикла длины n. Это включает случаи n = 1 и n = 2.
Пусть все грани ограничены ровно одним ребром. Так как все множества конечны, найдется грань, внутри которой нет петель. Аналогично предыдущему случаю, граница грани, прилегающей к выбранной снаружи, состоит как минимум из двух кусков. Значит, мы получили «одноугольник», то есть предыдущий случай для n = 1.
Пусть G — правильный граф с условием b = 2. Рассмотрим его компоненты связности. Среди всех компонент есть та, внутри которой нет ни одной другой компоненты связности. Если таких несколько, выберем одну и назовем ее специальной.
Если внешняя граница специальной компоненты состоит из двух кусков, то никакой другой компоненты связности нет — рассуждения здесь аналогичны предыдущему случаю. Возьмем двойственный к этому связному графу, получим правильный граф с условием a = 2. Это в точности цикл. То есть исходный граф состоит из двух вершин и n-кратного ребра.
Пусть теперь внешняя граница специальной компоненты состоит из одного куска. В этом случае компонента — это граф, обладающий таким свойством: все внутренние грани двуугольные, кроме внешней, которая из одного куска. Выкинем границу.
Заметим, что внешняя граница компоненты по-прежнему состоит из одного куска. Действительно, если это не так, и компонент больше, то вернем границу и получим, что граница внутренней грани состоит как минимум из трех компонент. То есть после выкидывания границы мы получили из специальной компоненты компоненту с тем же (описанном чуть выше) свойством.
Так как граф у нас конечный, продолжим этот процесс до тех пор, пока не закончатся ребра. Пусть это произошло на шаге N + 1. Тогда на шаге N мы получим, что наш граф — 1-угольник. Для него не выполняется b = 2. Значит, такое невозможно и для b = 2 мы получаем связный граф, двойственный к циклу.
Пусть в графе F граней, E ребер и V вершин. К всякому ребру прилегает по две грани, у каждой грани по b ребер в границе. Значит, bF = 2E, то есть F = 2E/b. Аналогично, к каждой вершине прилегает a ребер, значит aV = 2E и, следовательно, V = 2E/a.
Запишем формулу Эйлера для несвзяного графа на плоскости с K компонентами связности. Она имеет вид
V — E + F = 1 + K.
Подставляем полученные выражения в эту формулу и получаем
E (2/a + 2/b — 1) = 1 + K.
Справа стоит выражение больше нуля. Таким образом, получаем ограничение на a,b вида
2/a + 2/b — 1 > 0.
Дальше, заметим, что при a > 5 из неравенства вытекает, что b < 3. Значит, a принимает значения 3, 4, 5. Получаем следующие пары (3,3), (3, 4), (3, 5), (4, 3), (5, 3). Если граф связный, то это в точности графы третраэдра, куба, икосаэдра, октаэдра и додэкаэдра.
***
Пусть теперь у графа как минимум две компоненты связности. Теперь снова выберем самую глубокую компоненту связности для случая (a, b), то есть компоненту, которая внутри себя не содержит других компонент связности. Если таких несколько, возьмем любую. Ее внешняя грань не может состоять из b ребер (рассуждения тут аналогичны проведенным выше). Значит, она состоит из меньшего числа, которое мы обозначим c.
Всего допустимых троек существует 13 штук: (3, 3, 1), (3, 3, 2), (3, 4, 1), (3, 4, 2), (3, 4, 3), (3, 5, 1), (3, 5, 2), (3, 5, 3), (3, 5, 4), (4, 3, 1), (4, 3, 2), (5, 3, 1), (5, 3, 2).
Покажем, сначала, что тройки (3, 3, 1), (3, 4, 1), (3, 5, 1) невозможны. Действительно, граница во всех случаях состоит из одного ребра и одной вершины. При этом степень вершины как минимум три. Поэтому внутри контура из вершины на границе выходит ровно одно ребро. Обозначим вершину B, а это внутреннее ребро через AB. Тогда, начиная обход с A, мы пройдем сначала AB, потом, границу, потом AB в противоположном направлении. При этом грань всегда остается справа. Однако, так как мы прошли ребро в обоих направлениях, получаем, что одна и та же грань прилегает к ребру с двух сторон. Это противоречит нашему условию.
Заметим еще, что невозможна тройка (3, 4, 3). Пусть такой граф есть. Возьмем двойственный ему граф. В этом графе все вершины имеют степень 4 кроме одной, которая имеет степень 2. То есть по построению 4(V - 1) + 3 = 2 E. Слева стоит нечетное число, справа четное. Это невозможно, значит, тройка не реализуема в виде графа в принципе.
***
У нас осталось 9 случаев. Разберем их по порядку.
На границе имеется две вершины A и B. У них степени три, значит, помимо того, что они дважды соединены друг с другом, каждая из них соединена с другой вершиной внутри нашего контура. Пусть это вершины A_1 и B_1 соответственно. По лемме об AB-обходе из треугольности граней получаем, что A_1 = B_1. Но степень полученной вершины два. При этом любое ребро, выходящее из этой вершины либо лежит целиком в одной грани, либо в другой. Получаем противоречие. Такого графа нет.
На границе снова вершины A и B. У них степени три, значит, помимо того, что они дважды соединены друг с другом, каждая из них соединена с другой вершиной внутри нашего контура. Пусть это вершины A_1 и B_1 соответственно. Так как степени вершин равны трем, то из каждой из этих вершин выходят по два ребра. Пусть они входят в вершины A_11, A_12, B_11, B_12 соответственно. Считаем, что нумерация вершин идет против часовой стрелки.
При обходе, начиная с A_11 получаем по лемме, что A_11 и B_12 совпадают и A_12 и B_11 совпадают. Но при этом получается, что внутри такого графа есть грань, ограниченная двумя ребрами. Противоречие. Рассуждения удобно изобразить в графической форме.
Остальные случаи разбираются аналогично, поэтому приведем только их графическое исполнение