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

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

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

Пусть T – остов связного графа G, а g_j – ветвь этого остова. Удаление ветви из остова разбивает остов на 2 компоненты T₁ и T₂. Пусть X₁ и X₂ множества вершин, соответственно, компонент T₁ и T₂, а G₁ и G₂ – подграфы графа G, порожденные множествами вершин X₁ и X₂. Очевидно, что T₁ – остов подграфа G₁, а T₂ – остов подграфа G₂. Следовательно, подграфы G₁ и G₂ связны, а разрез, разделяющий X₁ и X₂, является разрежающим множеством графа G.

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

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

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

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