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

Плана́рный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. Какое-либо конкретное изображение планарного графа на плоскости без пересечения рёбер не по вершинам называется плоским графом. Иначе говоря, планарный граф изоморфен некоторому плоскому графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на плоскости, которые если и пересекаются между собой, то только по вершинам. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, называемая внешней гранью. Любой плоский граф может быть спрямлён, то есть перерисован на плоскости так, что все его рёбра будут отрезками прямых.

Свойства

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

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

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

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

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

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

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

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

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

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

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

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

Два примера непланарных графов

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

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

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

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

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

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

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

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

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

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

Теорема Понтрягина — Куратовского

В общем случае найти K₅ или K_3,3 довольно сложно. Граф Петерсена несложно стянуть в K₅, но в нём есть и K_3,3.

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

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

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

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

Компьютерная проверка на планарность

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

Признаки непланарных графов

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

Планарные графы в задачах

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

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

Обобщения

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

Число пересечений графа G — наименьшее число пересечений рёбер плоского рисунка графа G. Таким образом, граф является планарным тогда и только тогда, когда его число пересечений равно нулю.

Тороидальный граф — граф, который можно уложить на тор.

См. также

Словарь терминов теории графов
Теория графов
Клетка (теория графов)
Теорема Фари
Гамма-алгоритм — алгоритм проверки графа на планарность и его плоской укладки

Примечания

Харари Ф. Теория графов УРСС стр. 126
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.

Ссылки

Видеолекция, посвящённая планарным графам
А. Ю. Ольшанский. Плоские графы (недоступная ссылка), СОЖ, 1996, No 11, с. 117—122.
Харари Ф.. Теория графов. М.: «Мир». 1973
Дискретная математика: Алгоритмы, визуализация графов, апплеты

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Harary_126-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.