double arrow

Базисные циклы и разрезающие множества


Пусть T- остов графа G, а gi* – хорда кодерева T*. Так как Т – ацикличный граф, то граф Т È gi* содержит точно один цикл Ci. Цикл Ci состоит из хорды gi* и тех ветвей остова Т, которые образуют единственную простую цепь между концевыми вершинами хорды gi*. Цикл Ci, возникающий в графе Т È gi*, называется базисным циклом относительно хорды gi* остова Т. Множество всех таких циклов, число которых равно цикломатическому числу µ(G) графа G, называют базисным множеством циклов графа G относительно остова Т.

Пусть G(X) – связный граф и X = {X1, X2} – некоторое раз­биение множества его вершин: X = X1 È X2 и X1ÇX2 =Æ. Множество ребер графа G, одна концевая вершина каждого из которых принадлежит X1, а другая – X2, называется разрежающим множеством или разрезом графа. Удаление разрежающего множества – разрез графа, разде­ляет граф на две компоненты и делает его несвязным.

Пусть T – остов связного графа G, а gj – ветвь этого остова. Удаление ветви из остова разбивает остов на 2 компоненты T1 и T2. Пусть X1 и X2 множества вершин, соответственно, компонент T1 и T2, а G1 и G2 – подграфы графа G, порожденные множествами вершин X1 и X2. Очевидно, что T1 – остов подграфа G1, а T2 – остов подграфа G2. Следовательно, подграфы G1 и G2 связны, а разрез, разделяющий X1 и X2, является разрежающим множеством графа G.

Разрежающее множество Sj, составленное из ребер, связывающих вершины компонент T1 и T2 остова называется базисным разрежающим множеством графа G. При этом, компоненты T1 и T2 остова образованы удалением ветви gj остова T.

Свойства базисных циклов и разрежающих множеств

1.Базисный цикл Ci относительно хорды gi* кодерева T* связного графа G включает точно те ветви остова T, которым соответствуют базисные разрежающие множества, включающие эту хорду.

2. Базисное разрежающее множество Sj относительно ветви gj остова T связного графа G включает точно те хорды кодерева T*, которым соответствуют базисные циклы, включающие эту ветвь.


Сейчас читают про: