Связность. Цикломатическое число графа

Во многих задачах интерес представляют характеристики связности графа. Ранее отмечалось, что граф может быть связным или несвязным. Но это бинарная характеристика. Ясно, что связный граф может быть более связен и менее связен.

Как обычно, для иллюстрации тех или иных свойств графа рассмотрим простую задачу. Назовем ее «задача о рисовых полях». Известно, что при выращивании риса небольшие участки земли – чеки – заливают водой, а перед сбором урожая эту воду спускают. Для заполнения чеков нужно в некоторых земляных плотинах, отгораживающих чеки друг от друга, открыть проходы. Вопрос: сколько стенок (земляных плотин) следует разрушить, чтобы заполнить все поле водой?

Решение этой задачи очень простое, если использовать теорию графов. На рисовое поле можно смотреть как на граф, имеющий циклы (каждый чек – цикл). Для заполнения поля водой достаточно в каждом чеке разрушить одну стенку (в каждом цикле удалить одно ребро). Оставшиеся ребра образуют граф–дерево. Число вершин в графе останется без изменения, а число ребер будет равно . Если ранее в графе было ребер, то удалить пришлось ребро. Величина называется цикломатическим числом связного графа.

Цикломатическое число несвязного графа равно сумме цикломатических чисел связных компонент. Очевидно, что для любого графа–дерева это число равно нулю. Для леса – равно сумме цикломатических чисел связных компонент графа, т.е. тоже нулю. Для остальных графов цикломатические числа положительны.

Пример.Сколько и какие ребра следует удалить в графах на рис.3.16, чтобы превратить их в дерево?

Рис. 3.16.

Ответ. Граф а) включает 9 вершин и 11 ребер. Соответственно его цикломатическое число равно 11-9+1=3. Для графа б) эти расчеты дают 9-6+1=4. Вариантов удаления ребер из графа может быть довольно много. На рис. 3.17 показаны графы, полученные удалением ребер из графа а), и ребер из графа б).

Рис. 3.17.