Шаг 5.
Основные понятия теории графов.
Цикломатическое число и фундаментальные циклы графа

    На этом шаге мы рассмотрим цикломатическое число и фундаментальные циклы графа.

    Цикломатическим числом графа 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', которое было добавлено в дерево.

    На следующем шаге мы рассмотрим планарные графы.




Предыдущий шаг Содержание Следующий шаг