На этом шаге мы рассмотрим цикломатическое число и фундаментальные циклы графа.
Цикломатическим числом графа G=(V,E) с k связными компонентами называется число n(G)=|E|-|V|+k.
Фундаментальным циклом графа G=(V,E) с остовным деревом T=(V,E') называется простой цикл, получаемый в результате добавления в T одного из ребер G, не принадлежащего E'.
- Утверждение 1.
- Количество фундаментальных циклов графа G=(V,E) при любом фиксированном остовном дереве T=(V,E') равно цикломатическому числу G.
- Доказательство.
- Согласно лемме 3, k=|V|-|E'|, следовательно, <количество ребер G, не принадлежащих E'> = |E|-|E'| = |E|-(|V|-k) = n(G). При добавлении любого из этих ребер в T появляется ровно один простой цикл в силу теоремы 3; все получаемые при этом простые циклы различны, т.к. каждый из них содержит по крайней мере одно уникальное ребро - то самое ребро G, не принадлежащее E', которое было добавлено в дерево.
На следующем шаге мы рассмотрим планарные графы.
