Задачи для самостоятельного решения. Задача 1. Найти хроматическое число и хроматический индекс графа

Задача 1. Найти хроматическое число и хроматический индекс графа.

v₇

v₆

v₅

v₄

v₃

v₂

v₁

v₂

v₃

Задача 2. Найти хроматическое число и хроматический индекс графа.

v₉

v₄

v₈

v₇

v₆

v₅

v₁

Задача 3. Правильно выполнить раскраску вершин и ребер графа.

v₃

v₂

v₇

v₂

а) б)

v₈

v₆

v₅

v₄

v₃

v₁

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]"/>

v₇

v₆

v₅

v₄

v₁

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

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

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

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

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

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

, верхний треугольник = 1111 011 000₂=984₁₀.

Легко увидеть, что данная нумерация вершин является канонической, так как, сменив нумерацию вершин, получим числа меньше числа 984. Следовательно, кодом Харари данного графа является число 984.

Задача 2. Восстановить и нарисовать граф по числу 698 как по ходу Харари. Проверить, действительно ли нумерация вершин каноническая (т.е. является ли число кодом Харари).

Решение. Переведем число 698 в двоичную форму, для чего будем делить его на 2, записывая справа от черты остатки от деления, а слева на следующей строке частные.

698|0

349|1

174|0

87|1

43|1

21|1

10|0

5|1

2|0

Записываем число, начиная с последнего частного и далее все остатки снизу вверх: 1010111010. Код Харари должен быть треугольным числом, т.е. иметь длину 1,3,6,10,15,21 и т.д., если длина не совпадает ни с одним из этих чисел, то добавляем слева необходимое количество нулей. Для числа 698 этого делать не нужно, так как треугольное число равно 10.

Разбиваем число на разряды: 1010-111-01-0, выписываем эти числа в верхний треугольник матрицы, затем восстанавливаем всю матрицу, записывая ее строки по столбцам:

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

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

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

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