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

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

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

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



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий