10.1.3. Циклический и коциклический ранг

Максимальное независимое множество циклов (или минимальное множество ци­клов, от которых зависят все остальные) называется фундаментальной системой циклов. Циклы фундаментальной системы называются фундаментальными, а ко­личество циклов в (данной) фундаментальной системе называется циклическим рангом, или цикломатическим числом, графа G и обозначается m(G). Максималь­ное независимое множество коциклов (разрезов) (или минимальное множество коциклов, от которых зависят все остальные) называется фундаментальной си­стемой коциклов (разрезов). Коциклы (разрезы) фундаментальной системы назы­ваются фундаментальными, а количество коциклов в (данной) фундаментальной системе называется коциклическим рангом, или коцикломатическим числом, графа G и обозначается m*(G).

Пусть T(V, Е_Т) - остов графа G(V, Т). Кодеревом T*(V, E$) остова Т называется остовный подграф, такой что Е^ = Е \ ет- (Кодерево не является деревом!) Ребра кодерева называются хордами остова.

ТЕОРЕМА Если G — связный граф, то m(G) =g-

m*(G)=p-l.

доказательство

Рассмотрим некоторый остов Т графа G. По теореме 9.1.2 об основных свойствах деревьев каждая хорда е е Т* остова Т порождает ровно один простой цикл г_е. Эти циклы независимы, так как каждый из них содержит свое индивидуальное ребро (хорду е).

Покажем, что любой цикл графа G зависит от {Z_e}_e^T* • Заметим, что любой эле­мент фундаментальной системы зависит от фундаментальной системы, поэтому далее элементы фундаментальной системы не рассматриваем, то есть Z ^ Z_e.

Пусть теперь некоторый цикл Z содержит ребра е_г,... ,e_k е Т*. Такие ребра в Z обязательно есть, в противном случае Z с Т, что невозможно, так как Т — дерево. Докажем индукцией по k, что Z = Z_ei ф • • • ф Z_ek.

База: пусть k = I, тогда ei £ Т, Z\{ei} с Т и Z = Z_ei, так как если бы Z ф Z_ei, то концы е\ были бы соединены в Т двумя цепями, что невозможно по теореме 9.1.2.

Пусть (индукционное предположение) Z = Z_ei ф • • • ® Z_Ern для всех циклов Z с числом хорд т < k. Рассмотрим цикл Z с k хордами е\,... ,ek 6 Т*. Рассмо­трим Z_ek. Имеем Z': =(Z\{e_k})(J(Z_Ek\{e_k}) — тоже цикл (возможно, не простой). Но Z' содержит только k - 1 хорду ei,..., e_k-i. По индукционному предположе­нию Z¹ = Z_ei Ф • • • ®-Z_£k__J. Добавим к этому циклу Z_ek. Имеем:

.Z' © Z_ek = (Z\{e_k}) U ((Z_ek\{e_k}) ® Z_eJ = (Z\{e_k}) U {e_k} = Z.

Таким образом, {Z_e}_e&T' является фундаментальной системой циклов. Посколь­ку все фундаментальные системы содержат одинаковое количество элементов (как базисы векторного пространства), достаточно ограничиться рассмотрением любой, например, той, которая определяется остовом Т. Пусть теперь е 6 Т. Определим разрез S_e следующим образом. Ребро е — мост в дереве Т. Следова­тельно, удаление ребра е разбивает множество вершин V на два подмножества Vi и V₂, так что V_l CV, V₂C V, V_l U V₂ = V, Vi П V₂ = 0. Включим в разрез S_e ребро е и все ребра графа G, которые соединяют вершины множества Vi с вершинами множества V₂. Тогда S_e — это разрез, потому что правильные подграфы, определяемые Vi и V₂, являются компонентами связности G — S_e. Разрез S_e — простой, потому что, если есть ребро, соединяющее Vi и V₂, то граф связен.

Аналогично можно показать, что {8_е}_еет является фундаментальной системой разрезов. Действительно, любой разрез 5 содержит хотя бы одно ребро из Т, так как Т — связный остовной подграф. Разрезы {З_е}_е&т независимы, так как каждый содержит уникальное ребро е. Любой разрез 5 зависит от {S_e}_eeT> S = 0 S_e. Далее имеем m*(G) = \{S_e}_e&T\ = \Е_Т\ = р-1и

m(G) = \{S_e}_eeT-\ =