Определение

Граф называется плоским, если он имеет геометрическую реализацию на плоскости.

Для плоских графов применяется еще одно наименование  планарные графы.

В се приводившиеся ранее примеры графов являются плоскими графами. Однако не всякий граф является планарным. Например, графы, изображенные на рис. 5.6, не имеют геометрических реализаций на плоскости. a

a b c

K₃,₃ b c A ₅

1 2 3

d e

Рис. 5.6.

ТЕОРЕМА 5.2

Графы K_3,3 и A₅ не являются плоскими.

Доказательство

Покажем, что K_3,3  это непланарный граф.

Предположим противное. Возьмем произвольную геометрическую реализацию этого графа на плоскости.

Рассмотрим последовательное прохождение вершин K₃,₃ в следующем порядке: a  2  b  3  c  1  a. В рассматриваемом геометрическом представлении K₃,₃ на плоскости этому прохождению соответствует перемещение по некоторой замкнутой линии, не имеющей самопересечений.

Эта линия содержит все вершины графа и 6 ребер, а также делит плоскость на две части: внутреннюю, ограниченную замкнутой линией, и внешнюю. В общем виде возникающая ситуация представлена на рис. 5.7:

a 2

1 b

c 3

Рис. 5.7

Во внутренней и внешней областях должны быть изображены 3 ребра (которые обозначены на рисунке пунктирными линиями). Поэтому хотя бы в одной из этих областей необходимо провести не менее двух ребер. Нетрудно проверить, что во внутренней области невозможно провести более одного ребра так, чтобы соответствующие дуги не пересекались. Рассмотрим случай, когда во внутренней области изображается ребро (a, 3). Тогда ребра (b,1) и (c,1) должны изображаться дугами во внешней области. Но при любом изображении ребра (b,1) концы последнего ребра (c,1) невозможно соединить без пересечения уже проведенных линий. Это так поскольку всегда найдется такая замкнутая область на плоскости, образованная линиями, изображающими рёбра, что одна из вершин c и 1 содержится внутри, а другая снаружи этой области.

Поэтому предположение о существовании геометрической реализации графа K₃,₃ является неверным.

Непланарность графа A₅ доказывается аналогично приведенному доказательству непланарности графа K₃,₃.

Доказательство окончено.

В определенном смысле графы K₃,₃ и A₅ являются каноническими непланарными графами. Оказывается, что все другие непланарные графы содержат в себе фрагменты, подобные либо графу K₃,_3, либо графу A₅.

Для того чтобы сформулировать критерий планарности графов, определим дополнительные понятия.

Определение

Граф G₁ = (V₁,U₁) называется подграфом графа G₂ = (V₂, U₂), если V₁ V₂ и U₁ U₂.

Например, граф G₁, приведенный на рис. 5.8., является подграфом графа G₂.

a G ₂ a G ₁

b b

c c

d

Рис. 5.8.

Удаление из графа G некоторой вершины v, степень которой равна 2,  это замена удаляемой вершины и двух выходящих из нее ребер на одно ребро, соединяющее отличные от v концы удаленных ребер.

Процесс последовательного удаления из графа G одной или нескольких вершин степени 2 называется стягиванием этого графа. Обратная операция для удаления вершин степени 2 называется разбиением ребер.

Заметим, что операции удаления из графа вершин степени 2 и разбиения ребер сохраняют свойства графов быть планарными или непланарными.

ОПРЕДЕЛЕНИЕ

Разбиением ребра u = (a, b) графа G называется замена в этом графе ребра u на два ребра u₁ = (a, c) и u₂ = (c, b), где c  это новая вершина, не являющаяся вершиной G.