Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.5. Раскраска графов и вопросы топологии

Формула Эйлера и связанность поверхности

Тела, изображенные на рис. 3.73, удовлетворяют формуле Эйлера:

n – m + f = 2,

где n — вершины, m — ребра, f — грани любого правильного, полуправильного или звездчатого многогранника. Почему верна для них эта формула, понять несложно, если принять во внимание элементарный геометрический факт. Все упомянутые тела образуют из своих вершин и ребер вершины и ребра планарных графов, спроецированные на поверхность сферы, по которой эти вершины и ребра могут свободно скользить. Грани выпуклых и звездчатых тел образуют ячейки, которые всегда можно разбить на треугольные области. Один или множество треугольников, образующих планарный граф, удовлетворяют простому равенству: n – m + f = 1. Если учесть еще и внешнюю область планарного графа, то мы как раз и получим формулу Эйлера.

Аналогичные простые рассуждения дают ответ на вопрос: не пропустил ли Платон, а вслед за ним Архимед и другие геометры какое-нибудь правильное тело? Нет, не пропустили: формула Эйлера и наглядные рассуждения доказывают, что существует только пять правильных тел. В самом деле, пускай в вершине правильного многогранника сходятся k ребер или k граней (это все равно). Если число вершин равно n, то общее число ребер составляет m = kn/2. Допустим, что каждая грань представляет собой l-многоугольник с l сторонами. Тогда число ребер можно найти по другой формуле: m = lf/2. Найдем из двух последних выражений число вершин n и число граней f и, подставив их в формулу Эйлера, получим:

2m/k – m + 2m/l = 2 или 1/k – 1/m + 1/l = 1/2.

Судя по последнему выражению, грани и вершины находятся в одинаковом положении, а ребра — нет. Это свойство как раз и проявляется при построении двойственных геометрических тел и графов. Согласно последнему выражению при k = 3, l может принимать три и только три значения — 3, 4 и 5. Аналогично, при l = 3 имеем k = 3, 4, 5. Из симметрии вершин и граней находим одно и то же число ребер:

m = 6k/(6 – k) = 6l/(6 – l) = {6, 12, 30}.

Таким образом, целочисленные значения k и l не могут принимать значения меньше 3 и больше 5, иначе, число ребер будет равно либо бесконечности, либо отрицательному числу, что невозможно с точки зрения рациональной геометрии. Число правильных тел равно 6, так как тетраэдр повторяется дважды. Все правильные тела распадаются на взаимно двойственные пары: додекаэдр — икосаэдр, гексаэдр — октаэдр, правый тетраэдр — левый тетраэдр (если один из вписанных в куб тетраэдров назвать правым, то двойственный к нему тетраэдр будет левым).

Абсолютное пространство классической физики характеризует призматическая рама с квадратом в сечении (рис. 3.74а). Невозможная рама, изображенная рис. 3.74б, ассоциируется с образом релятивистской физики, когда невозможно подсчитать числа n, m и f. Образ классической физики встает в голове метанаблюдателя, выстраивающего свои пространственные модели в абсолютном пространстве; образ же релятивистской физики продиктован двумя объектными наблюдателями, для которых две внутренние стенки рамы оказываются вывернутыми в сторону зрителя, что и приводит к парадоксальной топологии. Подсчет основных элементов многогранника, иллюстрирующий образ классической физики, дает: n = 16, f = 10 и m = 24; эти значения удовлетворяют формуле Эйлера. Теперь обратимся к нашей раме с образующими в виде трехгранных призм (рис. 3.70). Топологические отличия рамы с трехгранными и четырехгранными призмами отсутствуют, обе рамы при их накачке воздухом переходят в тор. Однако, подсчитав основные элементы: n = 12, f = 12, m = 24 и подставив их в формулу Эйлера, мы убеждаемся, что она не выполняется. Таким образом, у нас появилась проблема.

Рис. 3.74

Чтобы разобраться, в чем тут дело, почему топологически эквивалентные тела дали столь различные результаты, нам надо обратиться к понятию связанности, которую обозначим как σ. Многогранное тело называется σ-связанным, если на нем можно отыскать σ – 1 ломаных, составленных из его ребер, причем первая из ломаных должна быть замкнутой, а все последующие — разомкнутыми и соединяющими точки предыдущих ломаных. На раме с трехгранными призмами одну ломаную можно провести по периметру треугольника, образованного двумя внешними и одной внутренней вершинами. Другую ломаную проводим по периметру прямоугольника, лежащего на четырех внутренних вершинах. Таким образом, мы распластали нашу раму, вскрыв все замкнутые объемы и не нарушив связанности ее поверхности. Если провести третью ломаную, то связанная поверхность распадется на две несвязанные. Поэтому связанность рамы (рис. 3.70) с образующими в виде трехгранных призм имеет значение σ = 3.

Рама, изображенная на рис. 3.74б, соответствующая релятивистской физике, логически противоречива и не может быть идентифицирована с какой-либо определенной топологической формой. Но рама, отвечающая классической физике (рис. 3.74а), может быть идентифицирована с тором, если каждую ее внешнюю вершину соединить ребром с ближайшей внутренней вершиной. Тогда по вновь проведенным ребрам можно будет провести замкнутую ломаную, которая разрежет раму, превратив ее в отрезок четырехгранной трубы. Второй разрез, сделанный по четырем ребрам вдоль трубы, разомкнет все внутренние объемы, сохраняя связанность всех ее граней. Это указывает на то, что связанность рамы с образующими в виде квадратных призм тоже равна трем. Но число ребер и граней увеличится: f = 16, m = 32. Проводя аналогичный подсчет вершин, граней и ребер в рамах с 5-гранными, 6-гранными и т.д. образующими, обнаруживается, что все они удовлетворяют формуле Эйлера, если в ней учесть величину связанности:

n – m + f + σ = 3.

Все многогранники (рис. 3.73), вершины и ребра которых в виде планарного графа можно разместить на сфере, имеют σ = 1, поскольку любая замкнутая ломаная, проведенная по ребрам планарного графа, разбивает единую связанную область на две несвязанные части. Все рамы путем плотной накачки воздухом можно свести к тору, связанность которого составляет σ = 3. Так, для рамы с трехгранными призмами (рис. 3.70) в соответствии с модернизированной формулой Эйлера будем иметь:

n – m + f + σ = 12 – 24 + 12 + 3 = 3;

для рамы с четырехгранными призмами (рис. 3.74а):

n – m + f + σ = 16 – 32 + 16 + 3 = 3;

для рамы с пятигранными призмами получим:

n – m + f + σ = 20 – 40 + 20 + 3 = 3.

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

n – m + f + σ = 9 – 18 + 9 + 3 = 3.

Во всех случаях n = f = m/2, вряд ли здесь можно наткнуться на неожиданность, хотя от формалиста нужно требовать доказательств.