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

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

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

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

Формула Эйлера[править ]

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

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

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

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

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

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

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

Два примера непланарных графов[править ]

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

 

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

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

Доказательство. Для него не выполняется .

«Домики и колодцы»[править ]

 

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

Обобщения [править ]

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

Вау!! 😲 Ты еще не читал? Это зря![править ]

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

Надеюсь, эта статья про планарный граф теорема понтрягина , была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое планарный граф теорема понтрягина , куратовского и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.