Укладка графа на плоскости

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

Определение:

Граф обладает укладкой в пространстве [math]L[/math], если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами — жордановы кривые , соединяющие соответствующие вершины, причем 1) Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет; 2) Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам. Соответствующий граф, составленный из точек пространства и жордановых кривых из [math]L[/math], называют укладкой исходного графа.

Определение:

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

TODO: здесь картинка

Определение:

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

TODO: здесь картинка с ребрами внутри грани и показывающие внещнюю грань

Для плоских графов есть простое соотношение, называемое формулой Эйлера: [math]V - E + F = 2[/math], где [math]V[/math] — вершины(vertex), [math]E[/math] — ребра(edges), [math]F[/math] — грани(faces).

Это свойство позволяет в некоторых случаях просто доказывать непланарность некоторых графов, например непланарность [math]K_5[/math] и [math]K_{3,3}[/math].

Понятно, что любой граф, содержащий подграф [math]K_5[/math] или [math]K_{3,3}[/math] непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение:

Определение:

Введем отношение [math]R[/math] следующим образом: два графа на находятся в отношении [math]R[/math], если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежных ей, или наоборот, добавлением вершины степени два на ребро (см. картинку). TODO: картинка Отношением гомеоморфизма (или топологической эквивалентности) назовем транзитивное замыкание отношения [math]R[/math]: [math]R[/math]*.

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math]K_5[/math] и [math]K_{3,3}[/math]: теорема Понтрягина-Куратовского.

Литература

• Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
• Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 126. — ISBN 978­-5­-397­-00622­-4.