Вопросы для самоконтроля

1. Что такое цикломатическое число графа? Что показывает цикломатическое число графа?

2. Каким образом определяется цикломатическое число графа?

3. Что такое коцикломатическое число графа?

4. Дайте определение фундаментального цикла?

5. Каким образом можно построить матрицу фундаментальных циклов?

6. Что такое хроматическое число графа?

7. Какие оценки хроматического числа вы знаете? Какие методы нахождения хроматического числа обычно используются при решении практических задач?

8. Что такое раскраска вершин графа? Каким образом производится раскраска вершин графа?

9. Какой граф называется двудольным?

10. Дайте определение полного двудольного графа.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Для произвольного G = (X, U) графа определить цикломатическое число.

2. Для произвольного графа G = (X, U) определить цикломатическое число и построить матрицу фундаментальных циклов.

3. Для произвольного G = (X, U) графа определить хроматическое число.

4. Опишите идею последовательного метода раскраски.

5. Для произвольного графа G = (X, U) построить раскраску последовательным методом и определить хроматическое число.

6. Задать произвольный граф G, который являлся бы двудольным.

7. Постройте структурную схему алгоритма раскраски графа.

8. Постройте структурную схему алгоритма определения двудольного графа.

9. Постройте псевдокод алгоритма раскраски графа.

10. Постройте псевдокод алгоритма определения двудольного графа.

Цикломатическое и хроматическое числа – это основные инварианты графа, которые не меняются при изменении топологии графа.