1.3. Фундаментальные циклы графа
Основными понятиями теории графов являются цикломатическое число графа и остов графа. Понятие цикломатического числа широко используется при проектировании средств вычислительной техники в таких задачах, как выделение схем с обратными связями на платах, обеспечение устойчивой работы цифровых автоматов за счет многофазной синхронизации и т.п.
Остовной подграф графа - это подграф, содержащий все вершины графа.
Остовом называется остовной подграф, являющийся деревом.
Хордой остова D в связном графе G называется всякое ребро графа, не принадлежащее D.
Любой подграф, состоящий из хорды и остова, имеет точно один цикл.
Рис.3
На рис.3 показан граф и его остовные подграфы, являющиеся деревом. Остов не содержит циклов. Чтобы построить остов графа, нужно в графе ликвидировать все циклы (выбрасывая из графа соответствующие ребра). Ребра остова обеспечивают его минимальную связность, т.е., если из остова удалить любое ребро, он распадается на две связные компоненты графа. Если граф имеет n вершин, то его остов всегда имеет (п-1) ребро.
Отличительной особенностью остова является следующая: добавление к остову графа хотя бы одного ребра, не принадлежащего остову, образует цикл, который называется фундаментальным (базисным) циклом графа. Число фундаментальных циклов графа всегда постоянно, не зависит от выбранного остова и равно числу хорд, не входящих в остов. Это число называется цикломатическим числом графа. Цикломатическое число графа можно определить по формуле
V(G)=R-(N-1), где R - число ребер графа; N - число вершин графа.
Цикломатическое число V{G} определяет связность графа.
Фундаментальные циклы позволяют получить любой цикл, имеющиеся в графе, используя линейную операцию над фундаментальными циклами, для чего составляют матрицу фундаментальных циклов.
Матрица строится следующим образом. На графе выбирают остов и ребра, не входящие в него, нумеруют натуральными числами, начиная с 1. Затем нумеруют ребра остова. Матрица фундаментальных циклов содержит столько столбцов, сколько ребер имеется в графе, и столько строк, сколько ребер не входит в остов (т.е. равно числу фундаментальных циклов).
На пересечении i-ой строки и j-ro столбца ставится единица, если ребро j входит в фундаментальный цикл, образованный добавлением к остову ребра i, и ставится нуль - в противном случае. Каждая строка матрицы есть фундаментальный цикл, представленный в виде двоичного вектора. Любой не фундаментальный цикл графа может быть получен суммированием по модулю 2 некоторого числа фундаментальных циклов.
Матрица фундаментальных циклов для графа на Рис.3 а) имеет вид:
Сф (G) =
|
с m d a b e f g h |
|
||||||||
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
||
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
||
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
остов D
хорды
ис.4