 |
Алгоритм решения задачи о раскраске вершин графа
|
|
|
|
Шаг 1. Вычислить степени всех вершин. Расположить вершины в порядке убывания степеней. Присвоить n=1.
Шаг 2. Окрасить первую неокрашенную вершину в цвет №n.
Шаг 3. Окрасить в цвет № n все вершины, которые не смежны вершинам, уже окрашенным в цвет № n.
Шаг 4. Если все вершины окрашены, то hB=n – искомое хроматическое число.
Иначе n:n+1 и переходим к шагу 2.
Правильная раскраска ребер графа – такая, что никакие два инцидентных ребра графа (имеющих общую вершину) не окрашены в одинаковые цвета.
Минимальное число цветов, необходимое для правильной раскраски ребер графа, называется хроматическим индексом графа hр.
Алгоритм решения задачи о раскраске ребер графа
Шаг 1. Вычислить степени всех вершин. Расположить вершины в порядке убывания степеней. Выбрать вершину с максимальной степенью n.
Шаг 2. Окрасить все ребра, инцидентные этой вершине в n различных цветов.
Шаг 3. Переходим к следующей вершине по списку. Окрашиваем ее ребра.
И так далее.
Процесс продолжается до тех пор, пока не окрасим ребра, инцидентные последней вершине в списке. Если все ребра окрашены, то hр (количество красок) – хроматический индекс.
Справедлива следующая теорема.
Теорема Брукса. Если максимальная степень вершины в графе d, то хроматическое число hB£d+1.
Теорема Визинга. Если максимальная степень вершин в графе d, то хроматический индекс d£ hр£d+1.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1. Чему равно хроматическое число графа?
| v6 |
| v5 |
| v4 |
| v3 |
| v2 |
| v1 |
Решение. Воспользуемся алгоритмом раскраски вершин графа.
1. degv1=4; degv2=4; degv3=3; degv4=2; degv5=5; degv6=2, где degvi – степень i-й вершины. И начнем раскраску с вершины с наибольшей степенью.
|
|
|
2. Окрасим вершину v5 в цвет № 1.
3. Окрасим в цвет №1 все вершины, не смежные с вершиной v5. Таких вершин нет.
4. Выберем следующую вершину с наибольшей степенью из оставшихся. Это или вершина v1 или v2. Возьмем, например, вершину v1 и окрасим ее в цвет №2.
5. Окрасим вершины, не смежные вершине v1 и уже окрашенные в цвет №2. Это вершина v3 или v4. Возьмем, например, вершину v3 и окрасим в цвет №2.
6. Выберем следующую вершину с наибольшей степенью из оставшихся. Такой вершиной является вершина v2. Окрасим ее в цвет №3.
7. Окрасим в цвет №3 вершины, не смежные с вершиной v2 и уже окрашенные в цвет №3. Это вершины v4 и v6.
8. Больше вершин не осталось, а значит, хроматическое число графа hВ=3.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задача 1. Найти хроматическое число и хроматический индекс графа.
| v7 |
| v6 |
| v5 |
| v4 |
| v3 |
| v2 |
| v1 |
| v2 |
| v3 |
| v9 |
| v4 |
| v8 |
| v7 |
| v6 |
| v5 |
| v1 |
Задача 3. Правильно выполнить раскраску вершин и ребер графа.
| v3 |
| v2 |
| v7 |
| v2 |
| v8 |
| v6 |
| v5 |
| v4 |
| v3 |
| v1 |
| v7 |
| v6 |
| v5 |
| v4 |
| v1 |
Представление графов в памяти компьютера. Код Харари
Пусть дан граф с n вершинами. Пронумеруем вершины произвольно и составим матрицу смежности А. Так как граф неориентированный, то она будет симметрична относительно главной диагонали, поэтому достаточно взять ее верхний треугольник А'.
| A' |
Расположим А' в виде двоичной строки (слева направо и сверху вниз). Меняя нумерацию вершин, мы получим другие двоичные строки. Сравним их между собой как двоичные числа. Наибольшее из двоичных чисел называется кодом Харари, а возникшую при этом нумерацию вершин – канонической. Код Харари определяет граф однозначно, но не всякое число может быть кодом Харари.
|
|
|
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1. Найти код Харари графа.
Решение. Занумеруем вершины графа, выпишем матрицу смежности и ее верхний треугольник.
| 2 |
| 3 |
| 1 |
| 4 |
, верхний треугольник = 1111 011 0002=98410.
Легко увидеть, что данная нумерация вершин является канонической, так как, сменив нумерацию вершин, получим числа меньше числа 984. Следовательно, кодом Харари данного графа является число 984.
Задача 2. Восстановить и нарисовать граф по числу 698 как по ходу Харари. Проверить, действительно ли нумерация вершин каноническая (т.е. является ли число кодом Харари).
Решение. Переведем число 698 в двоичную форму, для чего будем делить его на 2, записывая справа от черты остатки от деления, а слева на следующей строке частные.
698|0
349|1
174|0
87|1
43|1
21|1
10|0
5|1
2|0
1|
Записываем число, начиная с последнего частного и далее все остатки снизу вверх: 1010111010. Код Харари должен быть треугольным числом, т.е. иметь длину 1,3,6,10,15,21 и т.д., если длина не совпадает ни с одним из этих чисел, то добавляем слева необходимое количество нулей. Для числа 698 этого делать не нужно, так как треугольное число равно 10.
Разбиваем число на разряды: 1010-111-01-0, выписываем эти числа в верхний треугольник матрицы, затем восстанавливаем всю матрицу, записывая ее строки по столбцам:
Восстановим по этой матрице граф с четырьмя вершинами
| 3 |
| 2 |
| 1 |
| 4 |
Заметим, что нумерация вершин не является канонической. Перенумеруем вершины.
| 3 |
| 2 |
| 1 |
| 4 |
Запишем матрицу смежности для получившегося графа
верхний треугольник = 11100110012=92110. 921>698, значит, число 698 кодом Харари не является.
|
|
|
