3.9.Планарность графов

Плоский граф – граф, который укладывается на плоскости так, что никакие два его ребра не пересекаются нигде, кроме как в инцидентной им обоим вершине. Граф, изоморфный плоскому, называется планарным. Любой граф, содержащий в качестве подграфа непланарный граф, является непланарным.

Количество граней можно найти для плоского связного графа. Грань – область плоскости, ограниченная ребрами и не содержащая внутри себя ни вершин, ни ребер. При подсчете числа граней плоского графа учитывается и плоская грань.

Рис. 3.8. Планарные графы

На рис. 3.8. оба графа планарны, но только второй из них плоский.

Теорема Эйлера о плоском графе. Для любой геометрической реализации плоского связного графа G=(X,E) верно: n-r+f=2, где n=|X|, r=|E|, f - число граней.

Из данной формулы вытекает ряд следствий.

Следствие 1. Если G – связный планарный граф и n≥3, то r≤3n-6.

Доказательство. Пусть G – плоский граф и для него справедлива формула Эйлера. Поскольку каждая грань может быть ограничена по крайней мере тремя ребрами, а каждое ребро соответствует двум граням, то 2r≥3f, следовательно, 3(2-n+r)≤2r или r≤3n-6.

Следствие 2. Графы К₅ и К_3,3 непланарны.

Доказательство. Пусть К₅ планарен. Тогда неравенство r≤3n-6 проводит к противоречию: 10≤9. Следовательно, К₅ непланарен.

Пусть К_3,3 планарен. Поскольку в двудольном графе нет циклов нечетной длины, то любая его грань ограничена по крайней мере 4 ребрами, т.е. имеет место неравенство 2r≥4f. Подставляя в это неравенство значение f из формулы Эйлера, приходим к противоречию: 20≤18. Следовательно, К_3,3 непланарен.

Следствие 3. Для плоского несвязного графа с n вершинами, r ребрами и k компонентами связности имеет место соотношение n-r+f=k+1.

Следствие 4. Сформулируем критерий планарности графа: граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых к графам К₅ и К_3,3. В любом простом планарном графе существует вершина, степень которой не больше пяти.

Назовем толщиной графа t(G) наименьшее число планарных графов, наложение которых дает граф G. Толщина графа является мерой его непланарности, в частности, толщина графов К₅ и К_3,3 равна 2, а толщина планарного графа равна 1.

Используя формулу Эйлера, нетрудно получить нижнюю оценку для толщины графа G с n≥3:

t(G)≥[r/(3n-6)], t(G)≥{(r+3n-7)/(3n-6)},

где символы [u] и {u} обозначают наибольшее целое число, не превосходящее u, и наименьшее целлон число, которое не меньше u.