Возможно, придет время для разговора о неплоских графинях, их телах и прочих неплатонических материях — но потом. Не сейчас. Сейчас давайте побеседуем о графах. Мы уже обсудили проблему четырех красок и там же доказали теорему о пяти и дале контрпример к трем. И остался один нюансик: почему у плоского графа непременно есть вершина, из которой выходит менее шести ребер?
В общем-то, нарисовать граф, у которого ребра не пересекаются и из каждой вершины их выходит пять — задачка со звездочкой. Попробуйте. Надо нарисовать сколько хотите городов так, чтобы между ними были непересекающиеся дороги и из каждого города выходило не менее пяти дорог.
Начнем с того, что граф — это теоретический объект, состоящий из конечного множества "вершин" и подмножества пар вершин, именуемых ребрами. Граф удобно представлять себе нарисованным на плоскости (или в пространстве): вершины суть точки, ребра — отрезки или гладкие кривые, соединяющие вершины.
Так вот, если граф так нарисован на плоскости, причем ребра не пересекаются (вне вершин), то он называется плоским. Это геометрический объект.
Планарный граф — это граф, который может быть изображен плоским. Хотя сделать это может быть совсем не просто. И есть теорема: планарный граф может быть изображен плоским графом с прямыми ребрами.
Плоский граф делит плоскость на области. Например, три вершины, попарно соединенные ребрами, образуют треугольник. Пересекать ребра нельзя, так что если внутри нет вершин, то войти в треугольник никак не получится. Эти области называют гранями графа. "Остаток" плоскости вне графа — тоже грань, иногда единственная.
Связный граф — это в котором из любой вершины можно пройти в любую по ребрам (возможно, через другие вершины). Несвязный граф как бы состоит из двух или более отдельных связных графов: компонент связности.
И имеет место формула Эйлера:
V + F = E + 2,
где V — число вершин, E — число ребер, F — число граней связного плоского графа.
Давайте ее докажем. Делается это по индукции.
Граф из одной вершины формулу не нарушает: V=1, F=1, E=0.
Добавить ребро без вершины нельзя. Грань тем более.
Добавить вершину без ребра нельзя: нарушится связность. Добавление вершины и ребра не нарушает формулу.
Соединение двух вершин новым ребром образует новую грань. Формула опять-таки выдерживает это.
Разбиение ребра на два вершиной формулу не ломает.
Всё.
Получается, что как плоский граф не рисуй, а число граней постоянно. Хотя кажется, что с чего бы. Но оно однозначно определяется числом вершин и ребер.
Теперь, грань определяют не менее трех ребер, а ребро разделяет две грани. Поэтому число ребер не меньше 3F/2:
3F ≤ 2E,
а тогда по формуле 3(E+2-V) ≤ 2E, то есть E ≤ 3V - 6.
Конечно, можно нарисовать граф из двух вершин, соединенных ребром, и нарушить эту формулу. Но других нарушений нет, так как предположения при большем числе вершин работают.
Отсюда следует тот вывод, который мы использовали при доказательстве теоремы о пяти красках: найдется вершина, из которой выходит менее шести ребер. Ведь если нет, то число ребер не меньше 6V/2 (по 6 ребер на вершину, две вершины делят одно ребро), и у нас противоречие. А вот не менее пяти ребер из каждой вершины может и может торчать, но вершин тогда надо не менее 12.
Ну и полный граф с пятью (пентаграмма) и более вершинами планарным не является. Полный — значит любая пара вершин соединена ребром. Ребер получается по четыре на вершину, но каждое сосчитано дважды. Всего 10 ребер. А вершин пять, то есть 3V-6=9.
В общем случае получается неравенство (n-3)(n-4)≤0, то есть в целых числах только два решения: 3 и 4. Почему 2 исключение, мы уже обсудили; полный 3-граф это треугольник, а полный 4-граф изображен выше.
Теперь посмотрим на граф как на "код" многогранника в пространстве. Ведь можно представить себе, что одну грань многогранника растянули и на нее "уложили" остальные грани вместе с вершинами и ребрами. И получится как раз плоский граф.
Отсюда сразу получается формула Эйлера для многогранников, такая же:
V + F = E + 2,
только теперь ребра, вершины и грани относятся к многограннику в пространстве. И это оправдывает термин "грань" для графа.
И можно решить вопрос о правильных многогранниках, известных также как платоновы тела. У них в каждой вершине поровну ребер (по e) и каждая грань образована одним и тем же числом ребер f.
Тогда число вершин V=N, число ребер E=eN/2 (по е ребер на вершину, и каждое ребро сосчитано дважды), число граней F=2eN/(2f) — по две грани на ребро, но каждую грань сосчитали f раз, так как каждое ее ребро ее "сосчитало". Получается, по формуле, равенство, которое мы перепишем так:
2Nf + 2Ne - Nef - 4f = 0.
При этом число вершин от четырех, число ребер из вершины от трех, число ребер на грань тоже от трех. Кажется, что решений будет много, но нет: их только пять.
Вот скрипт на Перле, который их находит:
use warnings; use 5.10.0;
%names = ('4:6:4'=>'тетраэдр', '8:12:6'=>'гексаэдр', '6:12:8'=>'октаэдр', '20:30:12'=>'додекаэдр', '12:30:20'=>'икосаэдр');
for$n(3..50) {for$e(3..50) {for$f(3..50) { unless(2*$n*$f+2*$n*$e-$n*$e*$f-4*$f) {
$E=$e*$n/2;$F=$e*$n/$f;say "N=$n,E=$E,F=$F,f=$f,e=$e, $names{$n.':'.$E.':'.$F}"} } } }
А вот результат его работы:
N=4,E=6,F=4,f=3,e=3, тетраэдр
N=6,E=12,F=8,f=3,e=4, октаэдр
N=8,E=12,F=6,f=4,e=3, гексаэдр
N=12,E=30,F=20,f=3,e=5, икосаэдр
N=20,E=30,F=12,f=5,e=3, додекаэдр
Да, здесь заранее занесены названия многогранников, но скрипт нашел бы и другие, если бы они были. Конечно, надо доказать, что других решений нет: скрипт перебирает лишь конечное множество вариантов. Но это делается.
А интересно, как греки отыскивали вот это вот всё? Ни Перла, ни формулы Эйлера (она же "Эйлера", а не "Платона"), ни теории графов, ни теории групп (которая тоже может отыскать все и доказать, что больше нет)...
