2. Цикломатическое число и фундаментальные циклы

Пусть неориентированный -граф с вершинами, ребрами и связными компонентами.

Определим число как

дает тогда полное число ребер в остовах каждой из связных компонент графа

Число определяется как

и называется цикломатическим числом (иногда его называют также дефектом или первым числом Бетти), а число называется коцикломатическим числом.

В теории электрических цепей (и на самом деле при представлении любой системы с сосредоточенными параметрами) числа имеют прямой физический смысл.

Рис. 9.1.

Так, цикломатичеческое число равно наибольшему числу независимых контуров в графе электрической цепи, т. е. наибольшему числу независимых круговых токов, которые могут протекать в цепи. Коцикломатическое число равно наибольшему числу независимых разностей потенциалов между узлами электрической цепи.

Рассмотрим, например, электрическую цепь, показанную на рис. 9.2а. Неориентированный граф этой цепи состоит из единственной связной компоненты и изображен на рис. 9.26, где остов показан жирной линией (см. гл. 6).

Добавление любого ребра из не принадлежащего к ребрам дерева приводит к образованию точно одного (простого) цикла, состоящего из ребер остова лежащих на (единственной) цепи из и только что добавленного ребра. Например, добавляя ребро получаем цикл Так как в графе имеется ребер, из которых лежат в то число всех циклов, построенных таким способом, равно что совпадает с цикломатическим числом графа В примере на рис. 9.2 число таких циклов равно они изображены на рисунке пунктирными линиями и обозначены через

(кликните для просмотра скана)

Все эти циклы, очевидно, независимы между

«обой, так как каждый из них имеет по крайней мере одно ребро, не принадлежащее никакому другому циклу. В общем случае циклов, получаемых добавлением какого-либо ребра из не лежащего в к ребрам называются фундаментальными циклами. Если семейство этих циклов обозначить через (в нашем примере то любой другой цикл в графе, не принадлежащий к может быть выражен в виде линейной комбинации циклов из если нринять следующее «оглашение [21].

Пусть каждый фундаментальный цикл представлен -мерным вектором, в котором компонента равна 1 или в зависимости от того, принадлежит ли ребро данному циклу. Тогда, используя как символ сложения по модулю 2, любой цикл можно представить как сумму по модулю 2 фундаментальных циклов. Так, цикл на рис. 9.2(6) может быть представлен в виде

Отметим, что обращение вышеприведенного утверждения неверно, а именно некоторая сумма по модулю 2 фундаментальных циклов не обязательно дает единственный цикл, но может представлять два и более циклов. Например, сумма соответствует двум циклам Таким образом, для порождения всех циклов графа не надо брать все комбинаций фундаментальных циклов и складывать их по модулю 2: некоторые из этих сумм на самом деле не будут циклами Более того, если данная сумма, скажем » не порождает цикла, то нельзя отбросить другие суммы, ее содержащие, так как, складывая по модулю 2 сумму с другой суммой, например (которая сам может не порождать цикла), мы можем получить цикл. Для преодоления этой трудности Уэлч [26] предложил некоторый метод, позволяющий отбрасывать «некорректные» комбинации фундаментальных циклов, как только они появляются. Этот метод основан на упорядочении фундаментальных циклов в соответствии со специальным множеством правил.

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

в графе можно найти множество из независимымх циклов, которые нельзя получить добавлением ребер к дереву, как это делалось выше. О таком множестве не следует говорить, что оно «фундаментальное».

Рис. 9.3. Независимые, но нефундаментальные циклы.

На рис, 9.3 показано множество из независимых циклов графа которое не может быть получено добавлением ребер ни к какому остову графа и которое поэтому не будет фундаментальным множеством.