Учебное пособие: Дискрет.матем_Ч.2_УП
91
5
РАСКРАСКА
ГРАФОВ
5.1
Раскраска
вершин
графа
Говорят
,
что
дано
гомоморфное
отображение
(
гомомор
-
физм
)
Ψ
графа
L=(X,U,P)
в
граф
L’=(X’,U’,P’)
,
если
каждой
вер
-
шине
X
x
∈
и
каждому
ребру
U
u
∈
графа
L
однозначно
отнесены
их
образы
X
x
′
∈
Ψ )
(
и
U
u
′
∈
Ψ )
(
в
L’
с
сохранением
инцидентно
-
сти
,
т
.
е
.
)]
(
),
(
),
(
(
)
(
[
,
y
u
x
P
xuy
P
U
u
X
y
x
Ψ
Ψ
Ψ
′
→
∨
∈
∀
.
Из
определения
гомоморфизма
ясно
,
что
он
не
обязательно
сохраняет
тип
рёбер
,
так
,
если
две
различные
вершины
X
y
x
∈
,
имеют
один
образ
,
X
y
x
′
=
Ψ
=
Ψ
)
(
)
(
переходят
в
петли
.
Вообще
при
гомоморфизме
дуга
может
перейти
в
дугу
,
звено
или
петлю
,
а
петля
−
только
в
петлю
.
Поэтому
есть
частный
случай
гомомор
-
физма
:
отображение
Ψ
тождественно
как
на Х, так
и
на
U,
а
обра
-
зом
графа
L=(X,U,P)
служит
соответствующий
неограф
)
,
,
(
~
P
U
X
L
=
.
Важную
роль
в
теории
графов
играют
некоторые
обобщения
гомоморфных
отображений
,
которые
будем
называть
частичными
гомоморфизмами
,
не
пытаясь
дать
самое
общее
определение
это
-
го
понятия
.
К
первому
типу
отнесём
отображения
,
отличающиеся
от
го
-
моморфизмов
только
тем
,
что
не
все
вершины
и
не
все
рёбра
обя
-
зательно
имеют
образы
.
Таковы
,
например
,
операции
образова
-
ния
любой
части
данного
графа
(
выбрасывание
некоторых
рёбер
и
некоторых
вершин
вместе
с
инцидентными
рёбрами
),
с
воз
-
можным
последующим
добавлением
новых
элементов
;
операция
образования
скелета
графа
и
т
.
д
.
Особый
интерес
представляют
два
частичных
гомоморфиз
-
ма
первого
типа
:
раскраска
и
стягивание
.
Раскраской
вершин
графа
L
называется
такой
частичный
го
-
моморфизм
первого
типа
,
который
отображает L
в
полный
обык
-
новеннй
граф
F
и
при
котором
каждое
ребро
имеет
образ
,
если
только
две
инцидентные
ему
вершины
обладают
образами
.
92
Наглядное
истолкование
отображения
состоит
в
следующем
:
граф
F
−
это
палитра
,
в
вершинах
которой
находятся
различные
краски
;
некоторые
вершины
окрашиваются
,
притом
с
соблюдени
-
ем
условия
:
чтобы
никакие
две
смежные
вершины
не
оказались
окрашены
в
один
цвет
.
В
число
не
окрашенных
вершин
,
очевид
-
но
,
попадут
все
те
,
при
которых
есть
петли
.
Другое
представление
раскраски
вершин
заключается
в
том
,
что
вершине
X
графа
L=(X,U,P)
относится
целое
неотрицатель
-
ное
число
q(x)
с
соблюдением
условия
.
],
0
)
(
0
)
(
)
(
)
(
)
,
(
[
)
,
(
=
∨
=
∨
≠
−
∈
∀
y
q
x
q
y
q
x
q
y
x
J
X
y
x
при
этом
q(x) = 0
означает
,
что
вершина х
не
окрашена
,
а
при
q(x)=i>0
число i
можно
рассматривать
как
номер
той
вершины
графа
F
,
в
которую
отображена
х
.
Наконец
,
раскраска
вершин
равносильна
выделению L
неко
-
торой
системы
попарно
непересекающихся
пустых
подграфов
.
Если
раскраска
графа
L
является
отображением
на
F
,
то
имеем
раскраску
n(F)
цветами
.
Раскраска
называется
полной
,
ес
-
ли
окрашены
все
те
вершины
,
при
которых
нет
петель
.
Наимень
-
шее
количество
цветов
,
достаточное
для
полной
раскраски
вер
-
шин
графа
,
называется
хроматическим
числом
и
обозначается
)
(
L
γ
.
Заметим
,
что
всевозможные
раскраски
вершин
произвольно
-
го
графа
находятся
во
взаимно
однозначном
соответствии
со
все
-
возможными
раскрасками
вершин
скелета
графа
,
следовательно
,
при
изучении
раскрасок
вершин
можно
ограничится
только
обыкновенными
графами
.
Очевидно
,
что
если
L
1
,L
2
,...,L
x
–
компоненты
графа
L
,
то
)}
(
),...,
(
),
(
max{
)
(
2
1
χ
γ
γ
γ
γ
L
L
L
L
=
.
Известны
следующие
оценки
хроматического
числа
графа
:
1.
)
(
)
(
1
L
n
L
≤
≤
γ
−
тривиальная
оценка
через
число
вершин
;
2.
)
(
)
(
L
L
ϕ
γ
≥
−
где
)
(
L
ϕ
плотность
графа
;
3.
Оценка
Брукса
:
1
)
(
)
(
≥
≥
L
L
δ
γ
,
где
)
(
L
δ
степень
графа
:
( )
( )
{
}
X
x
x
S
L
∈
=
/
max
δ
.
Полную
раскраску
вершин
графа
L=(X,U)
в
)
(
L
γ
цветов
бу
-
дем
называть
минимальной
.
93
Рассмотрим
ряд
примеров
.
Пример 5.1.1.
Пусть
Х
множество
стран
и
U
y
x
∈
)
,
(
,
если
страны
x
и
y
граничат
между
собой
.
Требуется
раскрасить
карту
так
,
чтобы
никакие
две
соседние
страны
не
были
окрашены
в
один
цвет
.
Пример 5.1.2. Проводится
монтаж
аппаратуры
,
например
,
телефонной
станции
.
Чтобы
не
перепутать
проводники
,
необхо
-
димо
провести
их
окраску
таким
образом
,
чтобы
два
проводника
,
идущие
к
одной
плате
,
имели
разный
цвет
.
5.1.1 Нахождение минимальной раскраски путём
использования соцветных вершин
Рассматривается
алгоритм
для
нахождения
минимальной
раскраски
графа
.
Две
вершины
x
и
y
графа
L=(X,U)
называют
со
-
цветными
,
если
существует
такая
минимальная
раскраска
q(x)
его
вершин
,
при
которой
q(y)=q(z).
Отношение
соцветности
симмет
-
рично
и
рефлексивно
,
но
не
тран
-
зитивно
(
так
,
например
,
вершины
a
и
f
графа
на
рис
. 5.1.1
соцветны
,
вершины
f
и
d
тоже
соцветны
,
а
a
и
d
–
не
соцветны
.
Смежные
вершины
всегда
несоцветны
,
но
обратное
утвер
-
ждение
неверно
(
см
.,
например
,
вершины
a
и
d
).
Показано
,
что
неполный
связный
граф L=(X,U)
всегда
обла
-
дает
хотя
бы
парой
соцветных
различных
вершин
.
Отождествле
-
ние
двух
таких
вершин
превращает
L
в
связный
граф
L’
c
преж
-
ним
хроматическим
числом
.
Если
L’
неполный
,
то
в
нём
опять
имеется
пара
различных
соцветных
вершин
и
т
.
д
.
Продолжая
процесс
отождествления
,
в
конечном
итоге
получим
полный
граф
F
( )
L
γ
,
а
одна
из
минимальных
раскрасок
вершин
исходного
гра
-
фа
находится
следующим
образом
:
окрасим
вершины
F
( )
L
γ
в
цвета
1,2,3...,
( )
L
γ
и
придадим
вершине
X
x
∈
графа
L
цвет
той
вершины
графа
F
( )
L
γ
,
в
которую
она
перешла
после
всех
ото
-
ждествлений
.
a
c
d
b
e
f
Рис. 5.1.1
94
Описанный
алгоритм
был
бы
весьма
удобен
при
наличии
хорошего
критерия
соцветности
вершин
,
однако
такого
универ
-
сального
критерия
пока
нет
.
Одним
из
локальных
критериев
соцветности
является
сле
-
дующий
:
Если
x
и
y
две
несмежные
вершины
,
и
y
x
Γ
∈
Γ
,
то
x
и
y
со
-
цветны
.
Пример 5.1.3.
5.1.2 Алгоритм Витавера нахождения минимальной
раскраски вершин
Алгоритм
основан
на
нахождении
некоторой
специальной
ориентации
рёбер
.
Пусть
L=(X,U)
−
данный
обыкновенный
граф
.
Через
( )
L
τ
обозначим
наибольшее
из
таких
целых
чисел
К
,
что
при
любой
ориентации
всех
рёбер
графа
полученный
орграф
(
)
U
X
L
,
=
содержит
по
крайней
мере
один
ормаршрут
длины
К
.
Теорема Витавера:
( ) ( )
1
+
=
L
L
τ
γ
.
Доказательство: Пусть
( )
L
γ
=
и
пусть
q(x)
−
одна
из
ми
-
нимальных
раскрасок
графа
L
.
Полагая
⎭⎬
⎫
⎩⎨
⎧
>
∈
=
)
(
)
(
&
~
|
y
q
x
q
U
y
x
xy
U
,
получим
орграф
(
)
U
X
L
,
=
,
не
содержащий
ормаршрутов
длины
,
а
значит
,
и
подавно
,
ормаршрутов
ещё
большей
длины
.
y
Гу
Гх
Рис. 5.1.2
95
Следовательно
,
1
)
(
−
≤
L
τ
,
т
.
е
.
( ) ( )
1
+
≥ L
L
τ
γ
(*)
Пусть
теперь
,
наоборот
,
данный
граф
L=(X,U) превращён
некоторой
ориентацией
рёбер
в
орграф
( )
Γ
=
=
⎟
⎠
⎞
⎜
⎝
⎛
,
,
X
U
X
L
,
не
со
-
держащий
ни
одного
маршрута
длины
более
( )
L
τ
.
Определим
по
-
следовательность
X
1
,
X
2
,…
множеств
вершин
,
полагая
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
−
=
⊆
Γ
−
=
∈
=
j
X
i
j
U
x
j
x
i
j
U
X
x
x
i
X
1
1
&
1
1
\
|
При
этом
считаем
=
=
j
j
X
U
0
1
∅,
т
.
е
.
{
}
∅
=
Γ
∈
=
x
X
x
x
X
&
|
1
Из
определения
множеств
X
i
непосредственно
следует
,
что
j
i
≠
⇒
∅
=
∩
i
j
X
X
; (5.1)
в
каждом
X
i
никакие
две
вершины
не
смежны
. (5.2)
Кроме
того
,
j
i
j
X
U
X
i
X
1
1
−
=
=
⇒
∅
=
при
1
≥
i
(5.3)
В
самом
деле
,
равенство
∅
=
i
X
означает
(
согласно
опреде
-
лению
i
X
),
что
⎟
⎠
⎞
⎜
⎝
⎛
⊄
Γ
∨
∉
∈
∀
−
=
−
=
j
i
j
x
j
i
j
X
U
X
U
X
x
X
x
1
1
1
1
\
или
]
)
\
(
\
[
1
1
1
1
∅
≠
∩
Γ
⇒
∈
∀
−
=
−
=
∪
∪
i
j
j
i
j
j
X
X
x
X
X
x
x
,
иначе
говоря
,
(
)
x
y
j
X
i
j
U
X
y
j
X
i
j
U
X
x
Γ
∈
−
=
∈
∃
−
=
∈
∀
1
1
\
1
1
\
,
откуда
сразу
видно
,
что
в
случае
∅
≠
−
=
j
i
j
X
U
X
1
1
\
орграф
L
обладал
бы
сколь
угодно
длинными
ормаршрутами
.