Примеры решения задач

Пример 1. Определить цикломатическое число графа G = (X, U), изображенного на рис. 17.3.

Рис. 17.3. Граф G

Решение: из рис. 17.3 видно, что исходный граф состоит из двух компонент связности, причем X = 8; U = 11, т.е. граф G имеет 8 вершин и 11 ребер. Подставив эти числа в формулу (3.1), получим (G) = 11 - 8 + 2 = 5. Следовательно, из исходного графа G необходимо удалить пять ребер для того, чтобы получилось дерево. Теперь необходимо определить, какие именно ребра мы должны удалить.

Как уже было сказано выше, на каждом шаге удаляется ребро, образующее хотя бы один цикл. В заданном графе присутствуют две компоненты связности. Проанализировав каждое ребро первой компоненты, мы приходим к выводу, что в данном случае удаление любого ребра приведет к разрыву одного из имеющихся циклов поэтому можно удалить любое ребро. Пусть это будет ребро (x₁ – x₂). Удалим шаг за шагом, например, ребра (x₂ – x₃); (x₃ – x₄). Как видно, в первой компоненте не осталось больше ни одного цикла. Теперь рассмотрим вторую компоненту. Здесь мы можем удалить, к примеру, ребра (x₅ – x₆); (x₆ – x₇). Мы удалили из исходного графа пять ребер. В результате получили лес, состоящий из двух деревьев, изображенных на рис. 17.4.

Рис. 17.4. Лес, состоящий из двух покрывающих деревьев на основе графа G

Пример 2. Определить хроматическое число и раскраску графа, изображенного на рис. 17.5.

Рис. 17.5. Граф G

Решение: для решения поставленной задачи воспользуемся последовательным алгоритмом раскраски графа.

1. Подсчитываем локальные степени вершин графа G и составляем список вершин в порядке не возрастания их локальных степеней:

^.

2. Выбираем из списка вершину x₄: ₁ = {x₄}.

3. Просматриваем список на предмет нахождения несмежных вершин. Выбираем ближайшую несмежную вершину. Это вершина x₇: ₁ = {x₄, x₇}.

4. Продолжаем процесс просмотра. Выбираем вершину x₂ - несмежную вершинам x₄ и x₇, включенным в подмножество ₁. Теперь ₁ = {x₄, x₇, x₂}.

5. Просматриваем список дальше, и так как в списке больше нет вершин, несмежных вершинам подмножества ₁, окрашиваем вершины этого подмножества в первый цвет и удаляем их из списка. После удаления список примет вид

^.

6. Выбираем вершину x₈: ₂ = {x₈}.

7. Выбираем вершину x₁: ₂ = {x_8, x₁}.

8. Выбираем вершину x₃: ₂ = {x_8, x_1, x₃}.

9. Выбираем вершину x₆: ₂ = {x_8, x_1, x₃, x₆}.

10. В списке нет больше вершин, несмежных вершинам подмножества ₂. Окрашиваем вершины этого подмножества во второй цвет и удаляем их из списка.

11. В списке остается только одна вершина – x₅. Эта вершина окрашивается в третий цвет.

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

Пример 3. Привести пример полного двудольного графа G = (X₁, X₂, U), при условии, что X₁ = 3; а X₂ = 4.

Ответ: пример полного двудольного графа соответствующего исходным условиям показан на рис. 17.6.

Рис. 17.6. Полный двудольный граф

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

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

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

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

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

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

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

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

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

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

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