1	2	1
5		3
4	3	5	2
а) кольцо		б) звезда
	1	1
5		2
		2
4	3	5	4
в) звезда		г) звезда
(другая нумерация)		(неправильная
	5	подстановка)
	1	2

5 3

д) результат подстановки к графу г)

4

3

Рис. 6.53

В более сложных случаях, когда заданная подстановка имеет вид, например (v1,v2,v3,v4)(v5), перебор необходимо производить по двум параметрам: изменять степень четырех вершин (v1,v2,v3,v4) от 0 до 4 и для каждого случая подбирать возможные значения степени вершины v5.

6.9. Планарность

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

Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их

206

кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины.

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

Таким образом, планарный граф можно изобразить на плоскости как плоский. На (рис. 6.54) изображены 2 изоморфных (одинаковых) графа, причем первый из них плоский, а второй является планарным.

2	4	2	3
	3
			5
1	5	1	4
	а		б

Рис. 6.54

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

Плоские графы – это в том числе простые циклы, деревья (рис. 6.55), лес, а также граф, содержащий цикл, из вершин которого «выходят» деревья.

Рис. 6.55

207

Примером неплоского графа может служить полный граф с пятью вершинами (у него должно быть 10 ребер). Любые попытки начертить его плоское представление обернутся неудачей. Рассмотрим плоский граф G (рис. 6.56).

2

2

1

3

1

3

	4	5
4	5
Рис. 6.56		Рис. 6.57

Если добавить к графу на рис. 6.56 ребра (1,3) и (1,5), то полученный новый граф G тоже будет плоским (рис. 6.57).

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

6.9.2. Критерии непланарности

Можно ввести два условия, определяющие непланарность графа:

•достаточное условие – если граф содержит двудольный подграф K3,3 или полный подграф K5, то он является не планарным;

•необходимое условие – если граф не планарный, то он должен содержать больше четырех вершин, степень которых больше 3, или больше пяти вершин степени больше 2.

Введение понятия гомеоморфности графов позволяет установить следующий важный результат, известный как теорема Куратовского (точнее, как теорема Понтрягина – Куратовского, так как Л.С. Понтрягин доказал, но не опубликовал, эту теорему еще в

208

1927 году), которая дает необходимое и достаточное условие планарности графа.

Теорема 6.17 (Понтрягина–Куратовского). Для того чтобы граф G был планарным, необходимо и достаточно, чтобы он не содержал ни одного подграфа, гомеоморфного графам K5 или

K3,3.

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

Элементарным стягиванием называется следующая процедура: берем ребро е (вместе с инцидентными ему вершинами, например, v1 и v2) и «стягиваем» его, то есть удаляем е и отождествляем v1 и v2. Полученная при этом вершина инцидентна тем ребрам (отличным от е), которым первоначально были инцидентны v1 или v2

(рис. 6.58).

v1	e	v2
		Граф G

v1 v2

Граф H

Рис. 6.58

Граф G называется стягиваемым к графу H, если H можно получить из G с помощью некоторой последовательности элементарных стягиваний (см. рис. 6.58).

Теперь теорема Понтрягина–Куратовского может быть сформулирована иначе.

Теорема 6.18. Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K5 или K3,3.

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

209

окружающий нас мир, как минимум, имеет три измерения, существуют разные геометрии, так что ограничиваться при построении теорий плоскостью довольно неосмотрительно.

Введем более общее определение.

Пусть задан неориентированный граф G=(V,U). Пусть каждой вершине vi из V сопоставлена точка ai в некотором евклидовом пространстве, причем ai ≠ aj при i ≠ j. Пусть каждому ребру u = (vi, vj) из U сопоставлена непрерывная кривая L, соединяющая точки ai и aj и не проходящая через другие точки ak. Тогда если все кривые, сопоставленные ребрам графа, не имеют общих точек, кроме концевых, то это множество точек и кривых называется геометриче-

ской реализацией графа G.

Теорема 6.19. Каждый конечный граф G можно реализовать в трехмерном евклидовом пространстве (без пересечения ребер).

Таким образом, можно иначе сформулировать определение планарности. Граф называется планарным, если существует его планарная реализация, то есть геометрическая реализация на плоскости (без пересечения ребер).

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

внешней гранью).

Так, граф K4 имеет четыре грани (три внутренних и одну внешнюю) (рис 6.59). В свою очередь, граф куба (рис. 6.60) имеет шесть граней (пять внутренних и одну внешнюю).

Рис. 6.59

210

Классическая реализация				Плоская реализация
		Рис. 6.60

Внешнюю грань имеет всякий планарный граф, даже если в нем нет циклов.

Теорема 6.20 (формула Эйлера). Для любой планарной реализации связного планарного графа G = (V,U) с n вершинами, m ребрами и r гранями выполняется равенство: n – m + r = 2.

Следствие 1. Формула Эйлера справедлива и для геометрической реализации связных графов на сфере.

Следствие 2. Для любого выпуклого многогранника справедливо равенство n – m + r = 2, где n – число вершин, m – число ребер, r – число граней.

Соотношение:

n – m + r = 2

(6.5)

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

Теорема 6.21. Если в связном планарном графе нет циклов длины меньше k (k ≥ 3), то m ≤ k (n – 2)/(k – 2), где n = |V|, m = |U|.

Теорема 6.22. Для любого связного планарного графа без петель и кратных ребер выполняется неравенство: m ≤ 3(n – 2),

где n=|V|, m=|U|.

211