Карты метро и нейронные сети. Теория графов

Клауди Альсина

C + V_n+1 = n + 1 + V_n + K = (n + V_n) + (K + 1) = (A_n + 2) + (K + 1) = (A_n + K + 1) + 2 = A_n+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К.

* * *

С помощью формулы Эйлера для выпуклых многогранников можно вычислить так называемую характеристику Эйлера — Пуанкаре:

Для сферы 

= 2. Если мы рассмотрим тор (поверхность вращения, получаемая вращением окружности вокруг оси, лежащей вне этой окружности), то получим 

= 0. Следовательно, в тороидальных многогранниках 0 = С + V — А. Родом поверхности

называется число отверстий в ней. Для сферы g = 0, следовательно, в тороидальных многогранниках g = 1. Итак, 

и g являются характеристиками поверхности, то есть число 2 в формуле С + V = А + 2 указывает на сферическую природу выпуклых многогранников. Для невыпуклых многогранников формула Эйлера не выполняется. В следующих разделах, где рассматриваются только выпуклые многогранники, мы подробно расскажем о следствиях формулы С + V = А + 2.

Формула Эйлера для граней и вершин

Теперь мы

знаем ограничения на число граней С и число вершин V выпуклого многогранника. Число ребер А полностью зависит от С и V. Попробуем исключить А из формулы Эйлера.

Чтобы полностью исключить А, нужно «более явно» выразить формулу Эйлера через С и V, уточнив, что скрывается за этими числами.

В выпуклом многограннике Р с числом граней С и числом вершин V обозначим за С_n число граней, имеющих n ребер, V_n — число вершин, в которых сходятся n ребер. Можно записать следующую сумму ряда (конечного!):

С = С₃ + С₄ + С₅  + С₆ + … (1)

Также

V = V₃ + V₄ + V₅ + V₆ + … (2)

Так как одно ребро принадлежит двум граням одновременно, то

3С₃ + 4С₄ + 5С₅ + 6С₆ + … = 2A. (3)

Так как каждое ребро соединяет две вершины, получим

3V₃ + 4V₄ + 5V₃ + 6V₆ + … = 2A. (4)

Используя формулу Эйлера, где обе части умножены на 2, то есть 2С + 2V = 4 + 2A, учитывая (1), (2) и (3), получим:

2С₃ + 2С₄ + 2С₅ + 2С₆  + … + 2V₃ + 2V₄ + 2V₅ + 2V₆ + … = 4 + 3С₃ + 4C₄ + 5C₅ + 6C₆ + …

Иными словами,

2V₃ + 2V₄ + 2V₅ + 2V₆ + … = 4 + C₃ + 2C₄ + 3C₅ + 4C₆ + … (5)

Аналогично на основе (1), (2) и (4) получим:

2С₃ + 2С₄ + 2С₅ + 2С₆ + … + 2V₃ + 2V₄  + 2V₅  + 2V₆ + … = 4 + 3V₃ + 4V₄ + 5V₅ + 6V₆  + …