Цикломатическое число графа

Рассмотрим -граф , имеющий компонентов связности. Величина

называется коцикломатическим числом графа. Оно равно общему числу ребер в остовах каждой из связных компонент графа . Цикломатическим числом (дефектом или первым числом Бетти) называется величина

.

Теорема.

Доказательство. Будем удалять из графа по одному ребру и следить за изменением величины . Параметры исходного графа обозначим , а после удаления ребра – . В процессе удаления ребер возможны две ситуации:

1°. Удаляемое ребро цикловое. Тогда

, , ; .

2°. Удаляемое ребро – перешеек. В этом случае

, , ; .

Итак, при удалении ребра величина либо не изменяется, либо уменьшается на единицу. После удаления всех ребер получим пустой граф, для которого , , , то есть . Следовательно, в исходном графе .

Из теоремы следует, что при в графе имеется, по крайней мере, один цикл.