Задание 5.

Произвести реберную и вершинную раскраски графа с определением вершинного и реберного хроматического числа.

Решение:Необходимо исходить из того, что граф называется правильно раскрашенным, если его смежные вершины( связи) раскрашены в разные цвета.

Примечание: Обозначим цвета через числа натурального ряда. Номер рядом с каждой вершиной (связью) обозначает определенный цвет.

Вершинная раскраска:

1 2Хроматическое число равно 3.

2 3 1

Реберная раскраска:

1Хроматическое число равно 4.

2 3 2 3

1 4

Задание 6.

Упорядочить граф матричным способом и построить порядковую функцию, функцию Гранди.

Решение:В основе алгоритма упорядочивания лежит матрица смежности.

L00 3 0 3 1

L1* 1 * 1 0

L2* 1 * 0 *

L3* 0 * * *

Изоморфный упорядоченный граф выглядит следующим образом:

X3

X2 X4 X5

X1

Уровни

Функция Гранди:

0

1 2 1

0

3 2 1 0

Порядковая функция:

3 0

0 2 1