Задания к выполнению работы

Задание 1. Выполнить разложение орграфа на компоненты сильной связности методом Мальгранжа-Томеску.

Задание 2. Произвести раскраску графа, используя функцию смежности Гранди.

Граф задается матрицей смежности. Вариант задания определяется следующим образом: по номеру ijиз таблиц 1-9 берется таблица с номером i, по j из таблицы 10 выбирается строка и осуществляется замена меток {a, b, c, d, e, f, g, h} столбцов матрицы смежности с номером i на цифры из множества {1, 2, 3, 4, 5, 6, 7, 8} в соответствии с табл. 10, затем производится перестановка столбцов матрицы смежности в порядке возрастания номеров. В результате получается матрица смежности требуемого графа.

При раскраске графа его необходимо задать графически.

Порядок выполнения работы

1) Изучить теоретическую часть.

2) Выполнить задания по п.6 в соответствии с заданным вариантом.

3) Составить отчет.

4) Ответить на контрольные вопросы.

Контрольные вопросы

1) Что называется графом?

2) Как представляются графы?

3) Что такое матрица смежности?

4) Какие графы подразделяются по связности?

5) Что такое транзитивное замыкание вершин?

6) В чем заключается алгоритм Мальгранжа - Томеску?

7) В чем заключается алгоритм заполнения столбца?

8) Как разложить граф на компоненты сильной связности?

9) В чем состоит задача раскраски графа?

10) В чем заключается алгоритм раскраски графа с помощью функции Гранди?

Варианты заданий к выполнению работы