Планарный граф | это... Что такое Планарный граф? (original) (raw)

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

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

Содержание

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

Здесь мы пользуемся интуитивным понятием слова «линия», подробнее см. в соответствующей статье.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

  1. ↑ Ф. Харари Теория графов УРСС стр. 126

Ссылки