WikiSort.ru - Не сортированное

Формула Эйлера

Для связного плоского графа справедливо следующее соотношение между количеством вершин ${\displaystyle |V(G)|}$ , рёбер ${\displaystyle |E(G)|}$ и граней ${\displaystyle |F(G)|}$ (включая внешнюю грань):

${\displaystyle \ |V(G)|-|E(G)|+|F(G)|=2.}$

Оно было найдено Эйлером в 1736 г.^[1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум, а, например, для поверхности тора — нулю.

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

${\displaystyle 3|F(G)|\leq 2|E(G)|,}$

следовательно,

${\displaystyle |E(G)|\leq 3|V(G)|-6,}$

то есть, при большем числе рёбер такой граф заведомо непланарен. Обратное утверждение неверно: в качестве контрпримера можно взять граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.

Общая формула также легко обобщается на случай несвязного графа:

${\displaystyle |V(G)|-|E(G)|+|F(G)|=1+|C(G)|,}$

где ${\displaystyle |C(G)|}$  — количество компонент связности в графе.

Полный граф с пятью вершинами

Лемма. Полный граф с пятью вершинами (К₅) нельзя уложить на плоскость.

Доказательство. Для него не выполняется ${\displaystyle E\leqslant 3V-6}$ .

«Домики и колодцы»

Задача о трёх колодцах. Есть три дома и три колодца. Можно ли так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. Мосты строить нельзя.

Лемма. Полный двудольный граф с тремя вершинами в каждой из долей (К_3,3) нельзя уложить на плоскость.

Доказательство. По формуле Эйлера граф имеет 5 граней.

С другой стороны: любая грань (включая внешнюю) содержит чётное число рёбер — а значит, не менее 4. Поскольку каждое ребро включается в ровно две грани, получается соотношение ${\displaystyle 4F\leqslant 2E}$ , F — количество граней, E — количество рёбер. Подставляем в это неравенство F = 5 и E = 9 и видим, что оно не выполняется.