ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ. Задача 1. Найти хроматическое число и хроматический индекс графа

Задача 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
u cmV2LnhtbEyOy07DMBRE90j8g3Ursalah5SWEOJUqBIbWNDXBzjxJYlqX4fYTd2/x13BcjSjM6dY B6PZiIPrLAl4nCfAkGqrOmoEHA/vswyY85KU1JZQwBUdrMv7u0Lmyl5oh+PeNyxCyOVSQOt9n3Pu 6haNdHPbI8Xu2w5G+hiHhqtBXiLcaJ4myYob2VF8aGWPmxbr0/5sBHx8bafXNKymP8/LahPGTIdP p4V4mIS3V2Aeg/8bw00/qkMZnSp7JuWYjnnxEpcCZktgtzp5WgCrBGRZCrws+H//8hcAAP//AwBQ SwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlw ZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVs cy8ucmVsc1BLAQItABQABgAIAAAAIQCvGOUT9AEAAO0DAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMv ZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQAR92z43AAAAAcBAAAPAAAAAAAAAAAAAAAAAE4EAABk cnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAVwUAAAAA " strokecolor="black [3040]"/>
v7
v6
v5
v4
v1

 


Представление графов в памяти компьютера. Код Харари

 

Пусть дан граф с n вершинами. Пронумеруем вершины произвольно и составим матрицу смежности А. Так как граф неориентированный, то она будет симметрична относительно главной диагонали, поэтому достаточно взять ее верхний треугольник А'.

 

A'

 


 


Расположим А' в виде двоичной строки (слева направо и сверху вниз). Меняя нумерацию вершин, мы получим другие двоичные строки. Сравним их между собой как двоичные числа. Наибольшее из двоичных чисел называется кодом Харари, а возникшую при этом нумерацию вершин – канонической. Код Харари определяет граф однозначно, но не всякое число может быть кодом Харари.

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1.Найти код Харари графа.

 


Решение. Занумеруем вершины графа, выпишем матрицу смежности и ее верхний треугольник.

 


, верхний треугольник = 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, выписываем эти числа в верхний треугольник матрицы, затем восстанавливаем всю матрицу, записывая ее строки по столбцам:

Восстановим по этой матрице граф с четырьмя вершинами

 


Заметим, что нумерация вершин не является канонической. Перенумеруем вершины.

 


 

Запишем матрицу смежности для получившегося графа

 

верхний треугольник = 11100110012=92110. 921>698, значит, число 698 кодом Харари не является.