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

• Название: Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
• Анкор: Дискретная Математика
• Дата: 15.09.2022
• Размер: 6.37 Mb.
• Имя файла: S_D_Shaporev_-_Diskretnaya_matematika_-_2004.pdf
• Тип: Учебное пособие; #679116
• страница: 20 из 26

3.22. Хроматические графы. Раскраски графов
Пусть


U
S
G
,

- неориентированный граф. Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета. Таким образом, множество вершин одного цвета является независимым множеством. Хроматическим числом
 
G
χ
графа G называется минимальное число цветов, требующееся для раскраски G . Если
 
k
G

χ
, то граф называется k -хроматическим.
Задачи раскраски вершин и ребер графа занимают важное место в истории развития теории и в самой теории графов. К построению раскрасок сводится целый ряд практических задач, например, задачи составления расписаний, распределения оборудования, проектирования некоторых технических изделий.
В теории хроматических графов существует так называемая гипотеза четырех красок, которую некоторые авторы с полным основанием называют «болезнью четырех красок».
Попытки обосновать эту гипотезу привели к ряду интересных результатов не только по раскраске графов, но и в ряде других разделов теории графов.
Легко найти хроматические числа некоторых известных графов, например,
 
n
K
n

χ
,
 
1
χ

n
K
,


2
χ
,

m
n
K
,
 
2
χ

T
, где
K
- дополнительный граф, а T - дерево. Однако эффективные методы определения хроматического числа произвольных графов до сих пор не найдены. В такой ситуации актуальны оценки хроматического числа, выражаемые в терминах более или менее просто вычислимых параметров графа.
Обозначим через
 
G
P
наибольшую из степеней вершин графа G .
Теорема 3.24. Для любого неориентированного графа G выполняется
неравенство
   
1
χ


G
P
G
(3.22.1)
Следующая теорема связывает хроматическое число графа с количеством его вершин и ребер.
Теорема 3.25. Для любого связного
 
m
n,
- графа G верны неравенства
 










































































2 8
9 3
χ
2 1
2 1
2 2
2 2
n
m
G
n
m
n
n
m
n
n
m
n
n
, (3.22.2)
где
 
... - целая часть, а
 
... - дробная часть числа.
Наконец, теорема 3.26 оценивает хроматическое число в терминах числа независимости
 
G
0
α
графа G .
Теорема 3.26. Для любого n - вершинного графа G верно неравенство
   
 
1
α
χ
α
0 0




G
n
G
G
n
. (3.22.3)

95
Проблема раскраски планарных графов является одной из самых знаменитых проблем теории графов. Она возникла из задачи раскраски географической карты, при которой любые две соседние страны должны быть окрашены в различные цвета. Эта задача легко сводится к задаче раскраски планарного графа.
В 1879 году английский математик Кэли четко сформулировал гипотезу четырех красок.
Гипотеза четырех красок. Всякий планарный граф 4-раскрашиваем.
Попытки доказать эту гипотезу привели в 1890 году к появлению теоремы Хивуда

Теорема 3.27. Всякий планарный граф 5-раскрашиваем.
Доказательство. Воспользуемся методом математической индукции по числу вершин графа. Совершенно очевидно, что если у графа не более пяти вершин, то теорема справедлива. Предположим, что она верна для графов порядка
5
,

n
n
Рассмотрим планарный граф G с
1

n
вершиной и докажем сначала несколько вспомогательных соотношений. Во-первых, из теоремы 3.21 вытекает, что если в связном плоском
 
m
n,
- графе граница каждой грани является
r
-циклом,
3

r
, то

 

2 2



n
r
r
m
Действительно, так как каждая грань графа ограничена
r
-циклом, то каждое ребро принадлежит дум граням, т. е.
m
r
f
2


, где
f
- число граней, но
m
n
f



2
из теоремы
3.21, тогда


m
r
m
n
2 2




и

 

2 2



n
r
r
m
. При
3

r
получим
6 3


n
m
Далее убедимся в том, что если число вершин у максимального плоского графа не ме-
2
x нее четырех, то степень каждой вершины не менее трех (см. рис.
3.59). Рассмотрим вершину
1
x . Пусть
3
x - смежная с ней верши-
3
x на. Ребро


3 1
, x
x
принадлежит дум граням - треугольникам
1
x


2 3
1
,
,
x
x
x
и


4 3
1
,
,
x
x
x
, причем
4 2
x
x

, так как число вершин не менее четырех. Таким образом,
1
x смежна по крайней мере с тре-
4
x мя вершинами
3 2
, x
x
и
4
x (см. рис. 3.59).
Рис. 3.59.
Итак, для максимального плоского графа с учетом двух предыдущих замечаний и лемме о рукопожатиях (см.задачу 3.9.1) будем иметь
6 3


n
m
,
















6 5
4 3
5 4
3 6
3 5
4 3
6 3
2 2
i
i
n
n
n
n
n
n
n
n
m
, где
i
n - число вершин степени
i
у максимального плоского графа. Но









3 6
5 4
3
i
i
i
i
n
n
n
n
n
n
, тогда


12 6n

















6 6
5 4
3 5
4 3
6 3
12 6
6
i
i
i
i
n
n
n
n
n
n
n
n
. Отсюда
4 5
4 3



n
n
n
, т. е. всякий планарный граф с
4

n
вершинами имеет, по крайней мере, четыре вершины со степенями, не превосходящими пяти.
Максимальный плоский граф
/
G
отличается от исходного графа G лишь наличием дополнительных ребер, соединяющих не смежные вершины без пересечения с прочими ребрами. Если в графе
/
G
имеется по крайней мере четыре вершины со степенями не больше пяти, то в исходном графе G такие вершины и подавно имеются.
Вернемся теперь к основному доказательству. В графе порядка
1

n
содержится вер-
:
G
3
x
:

G
3
x шина
0
x
, степень которой не превосходит пяти. Пусть
 
0
x
S
S

- окружение верши- ны
0
x в графе G (см. рис. 3.60). Возмож-
1
x
2
x ны два случая.
0
x x 1)
4

S
. В этом случае граф
 
0
\ x
G
5-раскрашиваем по индуктивному

Перси Джон Хивуд (1861 - 1955) – английский математик.

96 предположению. Раскрасим вершины гра-
4
x
5
x
4
x
5
x фа
 
0
\ x
G
пятью цветами, а вершину
0
x
Рис. 3.60.
окрасим в тот цвет, который не был испо- льзован при раскраске вершин из S .
2)
5

S
. В множестве S существуют две не смежные вершины
1
x и
2
x , иначе
 
5
K
S
G

и граф G не будет планарным (см. рис. 3.60). Граф G
, полученный из
 
0
\ x
G
слиянием вершин
1
x и
2
x в вершину
x , плоский и 5-раскрашиваемый по индуктивному предположению.
Рассмотрим какую-либо из его 5-раскрасок. В графе G окрасим вершины
1
x и
2
x в цвет вершины x , а остальные отличные от x вершины – в те же цвета, что и соответствующие вершины графа G
. Затем припишем вершине
0
x цвет, не используемый при раскраске вершин из S . Таким образом, получится правильная 5-раскраска графа G .
Трудность проблемы четырех красок привела к появлению большого числа равносильных ей формулировок. В конце 60-х годов прошлого века эта проблема была сведена к исследованию большого, но конечного множества так называемых неустранимых конфигураций, число которых оказалось равно 1482.
В 1976 году научному коллективу под руководством К. Аппеля

и В. Хейкена

удалось с использованием ЭВМ правильно раскрасить все графы из множества неустранимых конфигураций, затратив на это около 2000 часов машинного времени. Таким образом, хотя такое доказательство очень сложно повторить, можно считать, что формально гипотеза четырех красок доказана.
В заключение рассмотрим очень простой алгоритм последовательной раскраски графа. Этот алгоритм в общем случае не приводит к минимальной раскраске. Только для некоторых классов графов, например, полных k -дольных последовательная раскраска является минимальной.

Кеннет Аппель (???? - ????) – математик.

В. Хейкен (???? - ????) – математик.

96
Алгоритм последовательной раскраски содержит два правила.
1) Произвольной вершине x графа G присваивается цвет 1.
2) Если вершины
i
x
x
x
,...,
,
2 1
раскрашены k цветами
i
k
k

,
,...,
3
,
1
, то новой произвольно взятой вершине
1

i
x
приписывается минимальный цвет, не использованный при раскраске вершин из ее окружения.
Пример 1. Оценить и найти хроматическое число графа, изображенного на рисунке
3.61 б) и раскрасить его вершины по алгоритму последовательной раскраски. Является ли полученная раскраска минимальной? а)
3
x
4
x б) Плоская укладка этого графа,
:
G
:

G
7
x 1 полученная по описанному в
2
x
5
x
3
x 1 4
x 2 подразд. 3.21 алгоритму, изобра-
2
x 2 1 5
x жена на рис. 3.61 б). Исходный
1
x
6
x граф G - планарный.
1
x 1 2 6
x Оценим его хроматическое чис-
7
x
Рис. 3.61.
ло. Формула (3.22.1) дает
7

n
,
9

m
,
 
3

G
P
,
 
4 1
3
χ



G
Аналогично, по
(3.22.2) получим
 











































2 2
8 9
3
χ
7 18 49 1
7 18 49 1
7 18 49 7
G
, т. е.
 
4
χ
0


G
. Наконец, так как
 
4
α
0

G
, по формуле (3.22.3) будем иметь
 
1 4
7
χ
4 7




G
, т. е.
 
4
χ
75 1


G
На самом деле
 
2
χ

G
. Раскрасим вершины этого графа по алгоритму последовательной раскраски. Выберем в качестве начальной вершину
7
x и присвоим ей цвет
1.
  

4 2
7
, x
x
x
S

, поэтому обеим вершинам присваиваем цвет 2. Далее выберем, например, вершину
3
x
. Ее окружение
  

6 4
2 3
,
,
x
x
x
x
S

. Вершины
2
x и x уже окрашены, вершина
6
x еще нет. Минимальным цветом, не использованным при раскраске вершин из окружения вершины
3
x является цвет 1, поэтому вершине
3
x присвоим этот цвет.
После нескольких этапов работы алгоритма получится раскраска, показанная на рис.
3.61 б). Эта раскраска минимальна, так как граф G двуцветен и представляет собой непол-
7
x
3
x
5
x
1
x ный двудольный граф (см. рис. 3.62). Двуцветные графы удовлетворяют следующей теореме.
Теорема 3.28 (теорема Кенига

) Граф
двуцветен тогда и только тогда, когда он не со-
2
x
4
x
6
x держит нечетных простых циклов.
Рис. 3.62.
Это условие выполняется для графа G

(см. рис.
3.61 б).
3.23. Практическое занятие № 9. Планарные и хроматические графы
3.23.1. Определим графы
n
G следующим образом. Пусть
n
G - граф, множество вершин которого совпадает с отрезком натурального ряда


10
,...,
2
,
1
, а множество ребер определяется следующим условием: не совпадающие вершины x и
y
смежны тогда, когда

Денез Кëниг (1884 - 1944) – венгерский математик.

97 числа x и
y
взаимно просты. При каких значения n графы
n
G планарны?
3.23.2. Доказать, что любой граф можно уложить в трехмерном пространстве
3
R .
3.23.3. Какие из графов, изображенных на рисунке 3.63 являются планарными? а) б) в)
Рис. 3.63.
3.23.4. При каких n графы порядка n
2 , изображенные на рисунке 3.64, являются планарными? а) б)
… …
… …
Рис. 3.64.
3.23.5. С помощью алгоритма укладки графа на плоскость построить плоские укладки или установить не планарность графов, изображенных на рисунке 3.65.
3
x
3
x
2
x
2
x
4
x
4
x
5
x
6
x
1
x
5
x
6
x
1
x
7
x
Рис.3.65.
3.23.6. Найти число планарности и толщину графов а)
5
K ; б)
3
,
3
K
и в) графа
Петерсена.
3.23.7. Уложить графы а)
5
K и б)
3
,
3
K
на торе.
3.23.8. Определить хроматические числа графов, изображенных на рисунке 3.66. а) б) в)
Рис. 3.66.
3.23.9. Граф называется критическим, если удаление любой из его вершин приводит к графу с меньшим хроматическим числом. Показать, что
n
K является критическим графом при
1

n
, а
n
C - тогда и только тогда, когда n - нечетно.
n
C - простой цикл, содержащий n вершин.
3.23.10. Приведите пример графа, последовательная раскраска вершин которого не является минимальной.

98
3.24. Потоки в сетях
Функциональное назначение большинства физически реализованных сетей состоит в том, что они служат носителями систем потоков, то есть систем, в которых некоторые объекты текут, движутся или транспортируются по системе каналов (дуг сети) ограниченной пропускной способности. Примерами могут служить поток автомобильного транспорта по сети автодорог, поток грузов по участку железнодорожной сети, поток воды в городской сети водоснабжения, поток электрического тока в электросети, поток телефонных или телеграфных сообщений по каналам связи, поток программ в вычислительной сети.
Ограниченная пропускная способность означает, что интенсивность перемещения соответствующих предметов по каналу ограничена сверху определенной величиной.
Наиболее часто в сети решается задача о максимальном потоке и минимальном разрезе. При этом граф


U
S
G
,

должен удовлетворять следующим условиям:
1) G - связный граф без петель;
2) существует ровно одна вершина, не имеющая предшествующих; эта вершина называется источником и обозначается s ;
3) существует ровно одна вершина, не имеющая последующих; эта вершина называется стоком и обозначается t ;
4) каждой дуге


U
x
x
j
i

,
поставлено в соответствие неотрицательное число


j
i
x
x
c
,
,




j
i
x
x
c
,
, называемое пропускной способностью дуги.
Функция


j
i
x
x ,

, определенная на множестве дуг сети




,
,U
S
G
, называется потоком, если

 
 

U
x
x
x
x
c
x
x
j
i
j
i
j
i




,
,
,
0

и




 
 





j
пр
i
i
сл
j
x
S
x
x
S
x
j
i
j
i
x
x
x
x
,
,


для любой вершины
 
t
s
x
S
x
i
i
,
и


. Последнее условие называется условием сохранения потока, в промежуточных вершинах потоки не создаются и не исчезают.
Величина

 
 

j
i
j
i
j
i
x
x
x
x
c
x
x
,
,
,




называется остаточной пропускной способностью дуги


j
i
x
x ,
. Если

 

j
i
j
i
x
x
c
x
x
,
,


, то дуга называется насыщенной.
Максимальный поток определяется с помощью одного из основных понятий теории сетей – разреза. Разрез может быть определен как множество дуг, исключение которых из сети отделило бы некоторое множество узлов от остальной сети. Предположим, что множество вершин сети S разбито на два непустых непересекающихся подмножества




//
/
//
/
и
S
S
S
S
S
Ø. Множество дуг, начала которых лежат в
/
S
, а концы в
//
S
, называется ориентированным разрезом и обозначается


//
/
S
S

. Следовательно,

 











//
/
//
/
,
,
S
x
S
x
x
x
S
S
j
i
j
i