Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf

107 9. Как определяется эксцентриситет вершины?
10. Какой эксцентриситет называется радиусом, а какой – диаметром графа?
11. Какая вершина графа называется центром, а какая – периферийной вершиной?
12. Что определяет передаточное число вершины?
13. Что такое медиана графа?
14. Какая вершина графа называется точкой сочленения?
15. Какое ребро графа называется мостом?
16. Как определяются понятия вершинной связности и реберной связности графа?
17. Какое соотношение имеется между числом вершинной связности и числом ребер- ной связности графа?

108
Тема 3.3. Специальные виды графов и раскраска графа
3.3.1. Эйлеров граф
Начало теории графов как раздела математики связывают с задачей о кенигсбергских мостах. Семь мостов г. Кенигсберга были расположены на р. Прегель следующим образом
(рис. 3.20):
Рисунок 3.20 – Общая схема расположения мостов на реке Прегель
(изображение с сайта http://www.pvti.ru)
Задача Эйлера состояла в том, чтобы определить, можно ли выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту?
Город разделен на 4 участка суши: A, B, C, D. Если их изобразить в виде вершин, а соединяющие их мосты – в виде ребер, то получим план города в виде графа, изображен- ного на рисунке 3.21.
Рисунок 3.21 – Мультиграф, соответствующий схеме расположения мостов
Тогда задача Эйлера переформулируется следующим образом: есть ли в мультиграфе цикл, содержащий все его ребра?
Эйлер доказал неразрешимость данной задачи, но при этом установил, когда связный граф может иметь цикл, проходящий через каждое его ребро.
A
B
C
D
a
b
c
d
g
e
f

109
Определение 3.51. Цепь, проходящая через каждое ребро графа, называется эйлеровой
цепью.
Определение 3.52. Цикл, проходящий через каждое ребро графа, называется эйлеро-
вым циклом.
Определение 3.52. Связный граф, содержащий эйлеров цикл, называется эйлеровым
графом.
Определение 3.53. Связный граф, содержащий эйлерову цепь, называется полуэйлеро-
вым графом.
Задача была решена Леонардом Эйлером в 1736 г. в виде общей проблемы теории графов и сформулирована следующей теоремой.
Теорема Эйлера
Граф является эйлеровым тогда и только тогда, когда он связен, и все его степени вер- шин четны.
Следствие 1
Для связного эйлерова графа множество его ребер можно разбить на простые циклы.
Следствие 2
Для того чтобы связный граф покрывался единственной эйлеровой цепью, необхо- димо и достаточно, чтобы он содержал ровно 2 вершины с нечетной степенью. Тогда цепь начинается в одной из этих вершин и заканчивается в другой.
Заметим, что эйлеров (полуэйлеров) граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.
Пример
На рисунке 3.22 приведены эйлеров (а), полуэйлеров графы (б) и граф, не являющийся эйлеровым (в).
(а)
(б)
(в)
Рисунок 3.22 – (а) Эйлеров граф, (б) полуэйлеров граф, (в) не эйлеров граф
Рассмотрим алгоритм Флери, который предназначен для построения эйлерова цикла в эйлеровом графе. Он позволяет пронумеровать ребра исходного графа так, чтобы номер ребра указывал, каким по счету это ребро войдет в эйлеров цикл.
Алгоритм Флери:
1) начиная с любой вершины
????, присваиваем ребру (????, ???? ) номер 1. Вычеркиваем это ребро из списка ребер и переходим к вершине u;
2) пусть
???? – вершина, в которую мы пришли в результате выполнения 1 шага алго- ритма и ????– номер, присвоенный очередному ребру на этом шаге;

110 3) выбираем произвольное ребро инцидентное вершине
w, причем мост выбираем только в крайнем случае, если других возможностей выбора ребра не существует. Присва- иваем ребру номер ???? + 1 и вычеркиваем его;
4) процесс длится до тех пор, пока все ребра не вычеркнуты.
3.3.2. Гамильтонов граф
Ирландский математик Уильям Гамильтон в 1859 г. предложил игру «Кругосветное путешествие», которая заключалась в следующем. Каждой из 20 вершин додекаэдра было приписано название крупного города мира. Нужно было, переходя из одного города в дру- гой по ребрам додекаэдра, посетить каждый город в точности один раз и вернуться в исход- ный город.
Эта задача сводится к отысканию в графе простого цикла, проходящего через каждую вершину графа.
Определение 3.55. Простой цикл, проходящий через все вершины графа, называется
гамильтоновым циклом, а простая цепь, обладающая этим свойством – гамильтоновой це-
пью.
Определение 3.56. Граф называется гамильтоновым, если он обладает гамильтоновым циклом, либо гамильтоновой цепью.
Пример
Каждый полный граф – гамильтонов, потому что в нем проведены всевозможные ре- бра и, в частности, те, благодаря которым возможен обход по всем вершинам.
В отличие от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Однако имеются достаточные условия на га- мильтоновость, которые проверяются легко. Недостаток здесь состоит в том, что даже если ни одно из этих условий не выполняется, граф может оказаться гамильтоновым.
Большинство известных фактов имеет вид: «Если граф имеет достаточное количество ребер, то граф является гамильтоновым». Приведем несколько таких теорем.
Теорема Дирака:
Если в графе ???? = (????, ????)
,
|????| = ????, ???? ≥ 3, для любого ???? ∈ ???? выполняется условие:
????(????) ≥
????
2
, то граф ???? является гамильтоновым.
Теорема Оре:
Если в графе ???? = (????, ????)
,
|????| = ????, ???? ≥ 3, для любых двух несмежных вершин ????и ????:
????(????) + ????(????) ≥ ????, то ???? – гамильтонов граф.
Кроме теорем Дирака и Оре, существует еще несколько достаточных условий гамиль- тоновости графа, которые приведены ниже.

111
3.3.3.
Планарный
граф
Определение 3.57. Граф называется плоским, если он изображен на плоскости так, что его ребра не пересекаются.
Определение 3.58. Граф ???? = (????, ????)
называется планарным, если он изоморфен плос- кому графу.
Изображение планарного графа ???? на плоскости в виде плоского графа называется
картой графа ????.
Карта делит действительную плоскость ????
????
на области. Множество областей карты графа обозначим через ????.
Теорема Эйлера
Для произвольной связной карты:
|????| + |????| − |????| = 2.
Пример
На рисунке 3.23 приведены планарный граф и его карта:

112
Рисунок 3.23 – Планарный граф и его карта
Из изображения карты видим, что множество областей ???? = {????
1
, ????
2
, ????
3
, ????
4
}. Области
????
1
, ????
2
, ????
3
– ограниченные области, область ????
4
– неограниченная.
Проверим теорему Эйлера для данного графа:
|????| + |????| + |????| = 4 + 4 − 6 = 2.
Определение 3.59. Для карты планарного графа???? = (????, ????) степенью области ????
????
называется длина замкнутого маршрута, ограниченного областью ???? .
Пример
На рисунке 3.24 изображена карта:
Рассмотрим два предложения для планарных графов.
f
1
f
2
f
3
f
4
f
1
f
2
Рисунок
3.24
–
Карта графа
v
1
v
2
v
3
v
4
f
3

113
Рисунок 3.25 – Полные непланарные графы
Графы K
5
и K
3,3
интересны тем, что они являются существенно «единственными» не- планарными графами. Все другие непланарные графы имеют подграфы, изоморфные этим графам. Чтобы уточнить это утверждение введем два определения.
Определение 3.60. Элементарное стягивание образуется путем слияния двух смеж- ных вершин после удаления ребра между ними и обозначения новой составной вершины.
Определение 3.61. Граф ???? называется стягиваемым к графу ????′, если ????′ может быть получен из ???? путем последовательности элементарных стягиваний.
Теорема Куратовского
Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых к графам K
5
или K
3,3
Алгоритмы, основанные на этой теореме, используются для определения, является ли данный граф планарным.

114
3.3.4.
Раскраска
графа
При решении практических задач с применением графов возникает необходимость в разбиении множества вершин графа на классы попарно несмежных между вершин. До- вольно часто дополнительно требуется, чтобы таких классов было наименьшее число. В теории графов подобные задачи формулируются в терминах раскраски вершин графа.
Определение 3.62. Раскраской графа ???? = (????, ????) называется функция вида:
????: ???? ⟶ ????
????
, где ???? – число красок раскраски ????.
Определение 3.62. Раскраска называется правильной, если для любых смежных вер- шин ????, ???? ∈ ???? справедливо неравенство????(????) ≠ ????(????).
Определение 3.63. Наименьшее число красок, необходимое для правильной раскраски графа ????, называется хроматическим числом графа ???? и обозначается ????(????). Правильную рас- краску таким числом красок будем называть оптимальной.
Пример
Графы G
1
и G
2
(рис.3.26) содержат трехэлементный полный подграф К
3
, поэтому для правильной раскраски необходимо, по крайней мере, три краски.
Для графа G
1
этого достаточно.
Граф G
2
имеет цикл длины 5, для правильной раскраски которого необходимы три краски. Но центральная вершина смежна всем вершина цикла, поэтому для правильной рас- краски понадобится четвертая краска
3
G
1 3
G
2
Рисунок 3.26 – Раскрашенные графы
Таким образом, ????(????
1
) = 3 и ????(????
2
) = 4.
На рисунке метки вершин графа означают номера красок.
1 2
2 2
1 1
2 2
3 4

115
Если нет формулы, позволяющей (точно) вычислить хроматическое число, то можно попытаться найти приемлемые оценки для этого числа.
Рассмотрим нижние оценки для хроматического числа ????(????). Рассмотрим оценку, свя- занную с плотностью графа.
Определение 3.65. Плотностью графа ????(????) называется наибольшее число вершин полного подграфа графа ????.
Пример
Для графов, изображенных на рисунке 3.26: ????(????
1
) = 3 и ????(????
2
) = 3.
Предложение 1:
Для любого графа ???? = (????, ????) справедливо неравенство:
????(????) ≤ ????(????).
Вторая оценка использует число независимости графа.
Определение 3.66. Множество попарно несмежных вершин графа называется незави-
симым множеством.
Определение 3.67. Числом независимости ????(????) графа ???? называется мощность наибольшего независимого множества.
Пример
Для графов, изображенных на рисунке 3.26: ????(????
1
) = 3 и ????(????
2
) = 2.
Предложение 2
Для любого графа ???? = (????, ????)
,
|????| = ????, справедливо неравенство:
Нижние оценки хроматического числа в предложениях 1 и 2 обладают следующим недостатком: задача вычисления чисел ????(????) и ????(????) столь же сложна, как и задача вычис- ления хроматического числа.
Известны нижние оценки хроматического числа, использующие «легко вычисляе- мые» величины. Одна из этих оценок приведена в следующем предложении.
Предложение 3

116
Для любого графа ???? = (????, ????)
,
|????| = ????, |????| = ????, выполняется неравенство:
Из верхних оценок укажем одну, приведенную в теореме Брукса, которая доказана
Бруксом в 1941 г.
Через ????(????) обозначим наибольшую степень вершин графа ???? = (????, ????).
Теорема Брукса:
Исторически понятие хроматического числа возникло с проблемой четырех красок, которая возникла в математике в середине XIX в.
Первоначально вопрос формулировался так: сколько нужно красок для раскраски лю- бой географической карты, при которой соседние страны раскрашены в разные цвета? По- скольку очевидно, что четырех красок недостаточно, то вопрос формулировался обычно в более конкретном виде: достаточно ли четырех красок для раскраски любой географиче- ской карты? В терминах теории графов вопрос имеет вид: достаточно ли четырех красок для правильной раскраски планарного графа? Положительный ответ на вопрос называется гипотезой четырех красок.
Гипотеза четырех красок:
Для любого планарного графа ????:
Теорема о раскраске пятью красками
Любой планарный граф ???? можно раскрасить пятью красками.
Контрольные вопросы
1. В чем состояла задача Эйлера, и как она была переформулирована в терминах тео- рии графов, и была ли она решена?

117 2. Что такое эйлерова цепь и эйлеров цикл?
3. Какой граф называется эйлеровым, полуэйлеровым?
4. Какое условие должно выполняться для того, чтобы граф был эйлеровым?
5. Что такое гамильтонова цепь и гамильтонов цикл?
6. Какой граф называется гамильтоновым?
7. Какие имеются достаточные условия для того, чтобы граф был гамильтоновым?
8. Какой граф называется плоским, какой – планарным?
9. Как называется изображение планарного графа в виде плоского графа?
10. Какие существуют соотношения между количествами вершин, ребер, областей планарного графа?
11. Какие графы являются существенно «единственными» непланарными графами?
12. Что такое элементарное стягивание в графе, и как это понятие связано с планар- ными графами?
13. Что называется раскраской графа, что такое правильная раскраска, оптимальная раскраска?
14. Как называется наименьшее число красок, необходимое для правильной рас- краски графа?
15. Какие понятия используются для оценки хроматического числа?

118