Карты метро и нейронные сети. Теория графов
Шрифт:
C + Vn+1 = n + 1 + Vn + K = (n + Vn) + (K + 1) = (An + 2) + (K + 1) = (An + K + 1) + 2 = An+1 + 2.
Так доказывается знаменитая формула Эйлера, которая звучит следующим образом: в любом выпуклом многограннике выполняется соотношение
С + V = A + 2.
Этот
* * *
РАЗУМЕЕТСЯ, А = С + V — 2. МОЖНО ЛИ ВЫБРАТЬ С И V ПРОИЗВОЛЬНО?
В выпуклом многограннике С + V = А + 2, следовательно,
А = C + V — 2. (1)
Какие значения могут принимать С и V? Существуют ли какие-то ограничения? Может ли быть так, что С = 1000, а V = 2? Рассмотрим, каковы же ограничения на С и V.
Очевидно, что V > 4, так как многогранника, у которого меньше четырех вершин, не существует. В каждой вершине сходятся минимум три ребра, следовательно, 3V =< 2А, так как каждое ребро связывает две вершины. Следовательно, 3V =< 2С + 2V — 4, откуда следует
4 =< V =< 2С — 4. (2)
Также С > 4, так как чтобы ограничить часть пространства, требуется минимум четыре грани. Каждая грань должна иметь минимум три ребра, то есть 3С =< 2А = 2С + 2V — 4, откуда
4 =< С =< 2V — 4. (3)
Отношения (1), (2) и (3) соответствуют выпуклым многогранникам в пространстве. Простейшие примеры многогранников, у которых число граней С >= 4, — это пирамиды и бипирамиды. Многоугольник, число ребер которого равно 2К, и точка вне его образуют пирамиду, где С = 2К + 1. Для бипирамиды, которая получается, если совместить две такие пирамиды основаниями, С = 4К.
* * *
С помощью формулы Эйлера для выпуклых многогранников можно вычислить так называемую характеристику Эйлера — Пуанкаре:
Для сферы
называется число отверстий в ней. Для сферы g = 0, следовательно, в тороидальных многогранниках g = 1. Итак,
Теперь мы знаем ограничения на число граней С и число вершин V выпуклого многогранника. Число ребер А полностью зависит от С и V. Попробуем исключить А из формулы Эйлера.
Чтобы полностью исключить А, нужно «более явно» выразить формулу Эйлера через С и V, уточнив, что скрывается за этими числами.
В выпуклом многограннике Р с числом граней С и числом вершин V обозначим за Сn число граней, имеющих n ребер, Vn — число вершин, в которых сходятся n ребер. Можно записать следующую сумму ряда (конечного!):
С = С3 + С4 + С5 + С6 + … (1)
Также
V = V3 + V4 + V5 + V6 + … (2)
Так как одно ребро принадлежит двум граням одновременно, то
3С3 + 4С4 + 5С5 + 6С6 + … = 2A. (3)
Так как каждое ребро соединяет две вершины, получим
3V3 + 4V4 + 5V3 + 6V6 + … = 2A. (4)
Используя формулу Эйлера, где обе части умножены на 2, то есть 2С + 2V = 4 + 2A, учитывая (1), (2) и (3), получим:
2С3 + 2С4 + 2С5 + 2С6 + … + 2V3 + 2V4 + 2V5 + 2V6 + … = 4 + 3С3 + 4C4 + 5C5 + 6C6 + …
Иными словами,
2V3 + 2V4 + 2V5 + 2V6 + … = 4 + C3 + 2C4 + 3C5 + 4C6 + … (5)
Аналогично на основе (1), (2) и (4) получим:
2С3 + 2С4 + 2С5 + 2С6 + … + 2V3 + 2V4 + 2V5 + 2V6 + … = 4 + 3V3 + 4V4 + 5V5 + 6V6 + …