Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Алгоритм решения задачи о раскраске вершин графа




 

    Шаг 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
    Задача 2. Найти хроматическое число и хроматический индекс графа.

 

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 кодом Харари не является.

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...