Просмотр кода страницы Планарный граф

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

== Свойства ==

=== Формула Эйлера ===
Для связного плоского графа справедливо следующее соотношение между количеством вершин <math>|V(G)|</math>, рёбер <math>|E(G)|</math> и граней <math>|F(G)|</math> (включая внешнюю грань):
: <math>\ |V(G)|-|E(G)|+|F(G)| = 2.</math>
Оно было найдено [[Эйлер, Леонард|Эйлером]] в 1736 г.<ref name="Harary 126">''Харари Ф.'' Теория графов УРСС стр. 126</ref> при изучении свойств выпуклых [[многогранник]]ов. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого [[Эйлерова характеристика|эйлеровой характеристикой]]. Это [[инвариант (математика)|инвариант]] поверхности, для плоскости или сферы он равен двум, а, например, для поверхности [[тор (поверхность)|тора]] — нулю.

Формула имеет множество полезных следствий. Во-первых, все плоские укладки одного графа имеют одинаковое количество граней. Во-вторых, если '''каждая грань ограничена не менее чем тремя рёбрами''' (при условии, что в графе больше двух рёбер), а '''каждое ребро разделяет две грани''', то
: <math>3|F(G)| \le 2|E(G)|,</math>
следовательно,
: <math>|E(G)| \le 3|V(G)|-6,</math>
то есть при большем числе рёбер такой граф заведомо непланарен. Обратное утверждение неверно: в качестве контрпримера можно взять [[граф Петерсена]]. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.

Общая формула также легко обобщается на случай несвязного графа:
: <math>|V(G)|-|E(G)|+|F(G)|=1+|C(G)|,</math>
где <math>|C(G)|</math> — количество компонент связности в графе.

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

=== Полный граф с пятью вершинами ===
[[Файл:Complete graph K5.svg|100px|thumb|right|K<sub>5</sub>, полный граф с пятью вершинами]]
'''Лемма.''' [[Полный граф]] с пятью вершинами (K<sub>5</sub>) нельзя уложить на плоскость.

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

{{clear}}

=== «Домики и колодцы» ===
[[Файл:Complete bipartite graph K3,3.svg|100px|thumb|right|Граф «домики и колодцы» (K<sub>3,3</sub>)]]
{{main|Домики и колодцы}}

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

'''Лемма.''' Полный [[двудольный граф]] с тремя вершинами в каждой из долей (K<sub>3,3</sub>) нельзя уложить на плоскость.

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

У двудольного графа любая грань (включая внешнюю) содержит чётное число рёбер — а значит, не менее 4. Поскольку каждое ребро включается в ровно две грани, получается соотношение <math>4F \leqslant 2E</math>, {{mvar|F}} — количество граней, {{mvar|E}} — количество рёбер. Подставляем в это неравенство {{math|1=''F'' = 5}} и {{math|1=''E'' = 9}} и видим, что оно не выполняется.
{{clear}}

== Теорема Понтрягина — Куратовского ==
[[Файл:Kuratowski.gif|thumb|300px|В общем случае найти K<sub>5</sub> или K<sub>3,3</sub> довольно сложно. [[Граф Петерсена]] несложно стянуть в K<sub>5</sub>, но в нём есть и K<sub>3,3</sub>.]]

{{Основная статья|Теорема Понтрягина — Куратовского}}

Очевидно утверждение: если граф {{mvar|G}} содержит подграф, [[гомеоморфизм графов|гомеоморфный]] K<sub>5</sub> или K<sub>3,3</sub>, то его невозможно уложить на плоскости. Оказывается, верно и обратное.

{{теорема|Граф планарен ''тогда и только тогда, когда'' он не содержит подграфов, [[гомеоморфизм графов|гомеоморфных]] полному графу из пяти вершин (K<sub>5</sub>) или графу «домики и колодцы» (K<sub>3,3</sub>).}}

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

{{теорема|Граф планарен ''тогда и только тогда, когда'' не содержит подграфов, [[стягивание ребра|стягивающихся]] в K<sub>5</sub> или K<sub>3,3</sub>.}}

== Компьютерная проверка на планарность ==
{{main|Проверка планарности}}
Первый алгоритм, отыскивающий подграф Куратовского за линейное время, разработан в 1974 году [[Хопкрофт, Джон|Хопкрофтом]] и [[Тарьян, Роберт|Тарьяном]]<ref>{{citation
 | last1 = Hopcroft | first1 = John | author1-link = John Hopcroft
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | doi = 10.1145/321850.321852
 | issue = 4
 | journal = [[Journal of the ACM|Journal of the Association for Computing Machinery]]
 | pages = 549–568
 | title = Efficient planarity testing
 | volume = 21
 | year = 1974}}.</ref>.

== Признаки непланарных графов ==
* '''достаточное условие''' — если граф содержит полный [[двудольный граф|двудольный подграф]] K<sub>3,3</sub> или [[полный граф|полный подграф]] K<sub>5</sub>, то он является непланарным;
* '''необходимое условие''' — если граф непланарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.

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

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

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

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

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

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

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://web.archive.org/web/20130923213145/http://compscicenter.ru/program/lecture/6702 Видеолекция, посвящённая планарным графам]
* ''[[Ольшанский, Александр Юрьевич|А. Ю. Ольшанский]]''. ''[http://window.edu.ru/window_catalog/redir?id=20742&file=9611_117.pdf Плоские графы]{{Недоступная ссылка|date=Ноябрь 2018 |bot=InternetArchiveBot }}'', [[Соросовский образовательный журнал|СОЖ]], [[1996]], No 11, с. 117—122.
* ''[[Харари|Харари Ф.]]''. [[Теория графов]]. [[Москва|М.]]: «[[Мир (издательство)|Мир]]». [[1973]]
* [https://web.archive.org/web/20140111172402/http://rain.ifmo.ru/cat/view.php/theory/list Дискретная математика: Алгоритмы, визуализация графов, апплеты]
{{Планарные графы}}
[[Категория:Теория графов]]
[[Категория:Семейства графов]]
[[Категория:Планарные графы|*]]