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

 В качестве характеристики плоского представления графа вводится понятие грани.

 Определение. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

Рис.2. 5

На рис. 2.5 имеем плоское представление графа с четырьмя гранями: (1,7,4,1), (1,2,3,1), (1,3,2,4,1), (2,6,5,4,2). Часть плоскости, ограниченная простым циклом (1,2,4,1), гранью не является, так как содержит внутри себя цикл (1,2,3,1).

Определение. Простой цикл, ограничивающий грань, назовём границей грани. Две грани будем называть соседними, если их границы имеют хотя бы одно общее ребро.

Бесконечная грань.  В качестве грани можно рассматривать и часть плоскости, расположенную "вне" плоского представления графа; она ограничена "изнутри" простым циклом и не содержит в себе других циклов. Эту часть плоскости называют "бесконечной" гранью.

Определение. Всякое плоское представление графа либо не имеет бесконечной грани, либо имеет в точности одну бесконечную грань.

 В плоском представлении дерева и леса за грань принимают всю плоскость (рис.1. 6).

Рис.2. 6

Плоские графы образуют на плоскости многоугольные сети.

Для плоских многогранников существует одно интересное соотношение, впервые доказанное Эйлером и известное под названием формулы Эйлера для многогранников. Она справедлива для всякого связного плоского графа.

 Обозначим через в, р, г соответственно число вершин, рёбер и граней такого графа Г. Теорема Эйлера утверждает, что всегда

в – р + г = 2.

Доказательство. Формула Эйлера очевидна в том простейшем случае, когда рассматривается только один многоугольник, имеющий n рёбер. В этом случав в = р = n, г = 2, и формула Эйлера действительно имеет место. Для доказательства справедливости этой формулы в общем случае мы воспользуемся методом математической индукции, а именно покажем, что если она справедлива для графов, имеющих г граней, то она также будет верна и для графов с (г+1) гранями.

Многоугольные графы можно строить, последовательно добавляя по одной грани "извне”. Предположим, что Г произвольный граф, имеющий в вершин, р рёбер и г граней, и что для чисел в , р , г справедлива формула Эйлера.

Добавим новую грань, проводя по грани Г∞ некоторую элементарную цепь, соединяющую 2 вершины максимального цикла графа Г.

Если эта элементарная цепь имеет m рёбер, то нам придётся добавить (m –1) новых вершин и одну новую грань.

Но тогда ясно, что формула Эйлера останется справедливой и для нового графа, так как в’ – р’ + г’ = (в + m –1) – (р + m) + (г + 1) = в – р + г .

Пример. Проверьте формулу Эйлера для графа, изображённого на рис. 2.7.

Рис. 2.7

в =7;   р =11;   г = 6 (включая Г∞). Значит в – р + г = 2.

Графы – деревья. Лес.

Определение. Деревом называется связный граф, не содержащий циклов. В частности, дерево не имеет петель и кратных рёбер (поскольку кратные рёбра образуют цикл).

Определение. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф называется лесом.

Любая цепь в графе без циклов является элементарной; любая часть такого графа также будет графом без циклов. Здесь элементарная цепь, как уже определялось ранее, – это цепь, при обходе которой, каждая вершина встречается только один раз.

Теорема. В дереве любые две вершины связаны единственной цепью.

Доказательство. Если бы было две связывающие цепи, то был бы и цикл.

Условие этой теоремы является также достаточным для того, чтобы граф был деревом.

 Наглядное представление для дерева можно получить при помощи следующей конструкции:

Рис. 2.8

Выберем произвольную вершину А₀ . От А₀ проведём все рёбра к вершинам, находящимся на расстоянии 1. От этих вершин проведём рёбра к вершинам, находящимся на расстоянии 2 от А₀ , и т.д. Из вершины А₂ , расположенной на расстоянии 1 от А₀ , выходит одно ребро к единственной последующей вершине А₂₁ , находящейся от А₀ на расстоянии 2, а также некоторое семейство рёбер к вершинам А₂₂₁ и А₂₂₂ , находящимся на расстоянии 1 от А₂₂ .

Определение. Исходная вершина дерева называется его корнем. Заметим, что корнем может служить любая вершина дерева.

Для подсчёта числа элементов дерева служит теорема.

Теорема. Дерево с N вершинами имеет N – 1 рёбер.

Для доказательства заметим, что простейшее дерево имеет только одно ребро, т.е. оно состоит из двух вершин и одного ребра; каждый раз, когда мы добавляем ещё одно ребро в конце ветви, прибавляется также и вершина.

Применение деревьев.