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

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

Рис. 17.3. Граф G

Решение: из рис. 17.3видно, что исходный граф состоит из двух компонент связности, причем ½X½ = 8; ½U½ = 11, т.е. граф G имеет 8 вершин и 11 ребер. Подставив эти числа в формулу (3.1), получим g(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 ₄: P₁ = { x ₄}.

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

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

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

.

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

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

8. Выбираем вершину x ₃: P₂ = { x _8, x _1, x ₃}.

9. Выбираем вершину x ₆: P₂ = { x _8, x _1, x ₃, x ₆}.

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

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

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

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

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

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