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

Цикломатическим числом графа G=(V,E) называется с k связными компонентами называется число (G)=|E|-|V|+k.

Фундаментальным циклом графа G=(V,E) с остовным деревом T=(V,E') называется простой цикл, получаемый в результате добавления в T одного из ребер G, не принадлежащего E'.

Утверждение 1. Количество фундаментальных циклов графа G=(V,E) при любом фиксированном остовном дереве T=(V,E') равно цикломатическому числу G.

Доказательство: согласно лемме 3 п.2, k=|V|-|E'|, следовательно, <количество ребер G, не принадлежащих E'> = |E|-|E'| = |E|-(|V|-k) = (G). При добавлении любого из этих ребер в T появляется ровно один простой цикл в силу теоремы 3 п.6; все получаемые при этом простые циклы различны, т.к. каждый из них содержит по крайней мере одно уникальное ребро - то самое ребро G, не принадлежащее E', которое было добавлено в дерево.

~