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

m ≤ 3n – 6.

(6.6)

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

6.10. Построение графов

6.10.1. Преобразование прилагательных в числительные

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

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

В табл. 6.6 приведены такие соответствия, чаще всего встречающиеся в формулировке задач.

		Таблица 6.6
Соответствие между описанием графа и свойствами
Прилагатель-	Числительное	Что это значит
ное
Связный	k = 1	В графе ровно одна компонента связ-
		ности
Несвязный	k ≥ 2	В графе более одной компоненты, его
		диаметр точно равен бесконечности
Регулярный	St(vi) = const	Степени всех вершин равны
Регулярный	St(vi) = y	Степени всех вершин равны y. Если
степени y		известно n (число вершин), то можно

212

Прилагатель-		Числительное	Что это значит
ное
			сразу рассчитать m (число ребер): m =
			n·y/2 (n или y должно быть числом
			четным)
Ациклический		γ = m – n + k = 0	Цикломатическое число равно 0, в
			графе нет циклов, это – дерево или
			лес (в зависимости от связности), та-
			кие графы всегда можно раскрасить в
			два цвета. Если известны две пере-
			менные из трех (n,m,k), то с помощью
			формулы можно найти третью
Дерево	(или	γ = m – n + 1 =	Цикломатическое число равно 0, в
ациклический		0,	графе нет циклов, это – дерево, такие
связный граф)		откуда	графы всегда можно раскрасить в два
		m = n – 1	цвета. Если известна одна переменная
			из двух (n или m), то с помощью фор-
			мулы можно найти вторую
Бихроматиче-		h = 2	Хроматическое число графа равно 2,
ский			такие графы всегда можно раскрасить
			в два цвета, это – двудольные графы,
			графически это или ациклические
			графы, или графы у которых все цик-
			лы имеют четную длину

6.10.2. Оценка количества ребер на основе степеней вершин

Отметим, что в задачах на построение решение необходимо искать среди простых неориентированных графов (т.е. графов без кратных ребер и без петель).

Имея даже общие представления о графе, иногда можно судить

остепенях его вершин.

1.В графе G сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный еще двести лет назад Эйлеру, часто называют леммой о рукопожатиях.

213

Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях).

2.Число вершин с нечетной степенью у любого графа четно (это прямое следствие из п.1).

3.Во всяком графе с n вершинами, где n ≥ 2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями (попробуйте самостоятельно доказать это совсем несложное утверждение).

4.Если в графе с вершинами n > 2 в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени (n – 1) (немного сложнее, но тоже вполне по силу для самостоятельного доказательства в самом начале ознакомления с теорией графов).

Теперь, когда получены все необходимые числительные, надо попробовать рассчитать недостающие характеристики графа. Иногда в условии приводятся степени всех или нескольких вершин. В этом случае на основе того факта, что каждое ребро графа добавляет к его суммарной степени вершин ровно 2, можно воспользовать-

ся формулой ∑St(vi) = 2·m, где m – количество вершин, а суммирование ведется по всем вершинам от 1 до n. Отсюда следует уже упоминаемый факт, что суммарная степень вершин должна быть числом четным.

Задача 6.17. Построить регулярный граф степени 5 на 11 вершинах или доказать невозможность такого построения.

Решение. Суммарная степень вершин равна 11·5 = 55, это нечетное число (количество ребер должно быть 55/2, а это число нецелое). Граф с указанными характеристиками построить нельзя.

Задача 6.18. Построить или доказать невозможность построения графа на 8 вершинах, у которого степень одной из вершин равна 5,

удвух других равна 4, у двух равна 3, у одной равна 2 и у двух равна 1.

Решение. Суммарная степень вершин равна 1·5+2·4+2·3+2+2·1 = =5+8+6+2+2 = 23, это число нечетное (количество ребер должно

214

быть 23/2, а это число нецелое). Граф с указанными характеристиками построить нельзя.

Задача 6.19. Построить или доказать невозможность построения графа на 9 вершинах, у которого степень одной из вершин равна 6, еще у одной 5, у двух равна 4, у одной 3, у двух равна 2 и у одной равна 1.

Решение. Суммарная степень вершин равна 6+5+2·4+3+ +2·2+1=27, это число нечетное. Но в условии указана информация только о 8 вершинах, тогда как в графе их 9. Значит, у 9-й вершины должна быть обязательно нечетная степень. Можно построить графы, в которых степень 9-й вершины равна 1,3,5,7 (больше она быть не может, так как в графе на 9 вершинах максимальная степень вершины равна 8). Четыре графа с различными степенями 9-й вершины представлены на рис. 6.61 (вместо номеров вершин указаны их степени).

2		St(v9)=3	2
St(v9)=1
1			3
4		5	4	6	2	1
5	6	1
4			4
2			3

	3
	1	St(v9)=7	3
St(v9)=5	2	2	5
	6	7		6
		1	4
5	4	5
			4
	4
			2
	3
Рис. 6.61			2

215