Цикломатическое число

При рассмотрении произвольного неориентированного графа без петель с и , состоящего из " " компонент связности, величину

(18.1)

называют цикломатическим числом графа.

Иногда вводят понятие ранга графа

(18.2)

В этом случае цикломатическое число

(18.3)

Цикломатическое число графа указывает то наименьшее число рёбер, которое нужно удалить из данного графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа), т.е. добиться отсутствия у графа циклов.

Цикломатическое число всегда неотрицательно.

Основное свойство цикломатического числа формулируется в виде теоремы:

Цикломатическое число мультиграфа равно максимальному числу независимых циклов.

Знание цикломатического числа оказывается полезным при анализе топологии электронных схем, а также для решения целого класса задач конструкторского проектирования РЭС.

Пример. Если рассматривать конструкцию печатной платы, то схему электрических соединений можно интерпретировать графом , где - множество областей контактных площадок, внутри которых проведение проводников запрещено, a - множество трасс.

При этом всё коммутационное пространство разбивается проведёнными соединениями на отдельные, локально замкнутые области

(18.4)

Любые две вершины находящиеся в различных областях , не могут быть соединены ребром без пересечения рёбер (соединений), ограничивающих области и .

В связи с этим возникает необходимость контроля непопадания смежных вершин в различные изолированные области.

Цикломатическое число позволяет определить число таких локально замкнутых областей и перейти к решению задачи рационального перераспределения рёбер графа .

Дата добавления: 2014-01-20