Также плоские графы называют планарными. Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку тривиально. Задача. Определить, является ли граф планарным, и, если да, то произвести его плоскую укладку. Плоский граф — это граф, нарисованный таким образом, что его ребра не пересекаются. В графе все циклы четные тогда и только тогда, когда граф является двудольным. Неравенства, связывающие число вершин графа, число его независимости и хроматическое число. Точность этих неравенств.

В данной статье будет рассмотрена задача на графах о возможности нарисовать тот или иной граф без самопересечений. Мы коснемся только первой части вопроса и ответим, когда и как можно нарисовать граф без самопересечений. Существуют и непланарные графы. На рис. 2 показаны два таких графа: полный пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K5 и K3,3 соответственно.

В конце 1920-х годов Куратовский в Польше и Л.С. Понтрягин в СССР независимо доказали поразительную теорему, показывающую, что мешает графу быть планарным. Если нарушено свойство (1), то граф нужно укладывать отдельно по компонентам связности. Если в графе есть мостики, то их нужно разрезать, провести отдельно плоскую укладку каждой компоненты связности, а затем соединить их мостиками.

Так как граф связности мостиками компонент связности является деревом, мы сумеем получить плоскую укладку. Те вершины, которые одновременно принадлежат G′ и какому-то сегменту, назовем контактными. Для нашего примера сегменты и вершины изображены на рис. 5. Контактные вершины обведены в квадрат.

Общий шаг алгоритма следующий: обозреваются все сегменты Si и определяются числа Γ(Si) . Если хоть одно из них равно 0, то граф не планарен, конец. Иначе, выбираем сегмент, для которого число Γ(S) минимально, или один из множества, если таких сегментов несколько. Еще раз опишем гамма-алгоритм компактно и займемся его обоснованием.

Корректность гамма-алгоритма

S1 и S2 есть две цепи (между контактными вершинами) L1 и L2 соответственно, такие, что их невозможно уложить в одну грань без пересечения. Рассмотрим двудольный граф. Начнем цикл в верхней доли. Нужно пройти по четному числу ребер, чтобы подняться снова в верхнюю долю. Следовательно, при замыкании цикла число ребер будет четным. Если граф несвязный, то проведем доказательство отдельно для каждой компоненты.

Основные определения

Частичной укладкойG′ планарного графа G называется граф, который можно получить из какой-нибудь укладки графа G на плоскости удалением каких-то ребер и вершин. Пусть A(G′) — не двудольный, тогда по теореме Кенига в нем есть цикл нечетной длины. По Лемме 2 все вершины этого цикла вмещаются ровно двумя гранями.

Это необходимо сделать в каждой частичной укладке, следовательно получена частичная укладка

База индукции очевидна: результат инициализации есть плоская укладка, так как уложенный цикл будет в любой укладке. На текущем шаге к нему присоединится цепь L: G′k = G′k−1 ∪ L. Докажем, что граф G′k — тоже частичная укладка. Среди сегментов на текущем шаге нет такого S, что Γ(S) = 0, иначе G′k−1 не был бы частичной укладкой. Первый случай означает, что укладка S в Γ неизбежна, так что граф G′k после добавления цепи из S останется частичной укладкой.

Возьмем его связную компоненту A′, этот граф тоже двудольный. Фактически, основой последней части доказательства было, что если граф A(G′k−1) — двудольный, то после удаления части ребер и вершин граф A(G′k) тоже двудольный. Таким образом, в результате каждой итерации для планарного графа частичная укладка увеличивается, в конце мы получим плоскую укладку.

Планарный — это граф, который изоморфен плоскому. В планарном графе можно говорить не только о вершинах и ребрах, но и о гранях. Пусть граф G′k−1, полученный на (k−1)-м шаге, является частичной укладкой. В результате повторения общего шага либо будет получена плоская укладка, когда множество сегментов станет пустым, либо будет получено, что граф G не является планарным.