Планарный граф

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины — это точки плоскости, а ребра — линии на ней. Области, на которые граф разбивает поверхность, называются гранями. Плоский граф — граф, уложенный на плоскость. Граф называется планарным, если он изоморфен некоторому плоскому графу.

Простейшие свойства плоских графов[править | править исходный текст]

Формула Эйлера[править | править исходный текст]

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

\ |V(G)|-|E(G)|+|F(G)| = 2.

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

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

3|F(G)| \le 2|E(G)|,

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

|E(G)| \le 3|V(G)|-6,

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

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

|V(G)|-|E(G)|+|F(G)|=1+|C(G)|,

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

Два примера непланарных графов[править | править исходный текст]

Полный граф с пятью вершинами[править | править исходный текст]

K5, полный граф с 5 вершинами

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

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


«Домики и колодцы»[править | править исходный текст]

Граф «домики и колодцы» (K3,3)

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

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

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

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

Теорема Понтрягина-Куратовского[править | править исходный текст]

В общем случае найти K5 или K3,3 довольно сложно. На первый взгляд кажется, что граф Петерсена содержит K5. Оказывается, нет — в нём есть подграф, стягивающийся в K3,3.

Очевидно утверждение: если граф G содержит подграф, гомеоморфный K5 или K3,3, его невозможно разложить на плоскости. Оказывается, верно и обратное.

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу из пяти вершин (K5) или графу «домики и колодцы» (K3,3).

Теорему также можно сформулировать в следующем варианте (иногда его называют «теорема Вагнера»).

Граф планарен тогда и только тогда, когда не содержит подграфов, стягивающихся в K5 или K3,3.

Компьютерная проверка на планарность[править | править исходный текст]

Первый алгоритм, отыскивающий подграф Куратовского за линейное время, разработан в 1974 году Хопкрофтом и Тарьяном.[2]

Признаки непланарных графов[править | править исходный текст]

  • достаточное условие — если граф содержит двудольный подграф K3,3 или полный подграф K5, то он является не планарным;
  • необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.

Планарные графы в задачах[править | править исходный текст]

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

Спрямление графа. Любой плоский граф можно перерисовать так, чтобы он остался плоским, а рёбра стали прямолинейными.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Ф. Харари Теория графов УРСС стр. 126
  2. Hopcroft, John & Tarjan, Robert E. (1974), "«Efficient planarity testing»", Journal of the Association for Computing Machinery Т. 21 (4): 549–568, DOI 10.1145/321850.321852 .

Ссылки[править | править исходный текст]