Определение. Цикломатическое число графа , с к компонентами связности

Цикломатическое число графа , с к компонентами связности

Цикломатическое число дерева равно 0. Цикломатическое число леса равно сумме цикломатических чисел деревьев и также равно 0.

Теорема

Цикломатическое число графа всегда больше равно 0.

Доказательство

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

Если - не дерево, то в нем существует хотя бы один цикл. Удалим из графа одно из ребер цикла, которое не является мостом, получим граф . Если в существует цикл, то уберем опять одно из ребер цикла, получим граф . Процесс будем повторять до тех пор, пока не получим граф без циклов. будет деревом и для него будет выполняться соотношения:

Тогда .