Фундаментальные циклы

Пусть G = (M,R) — неорграф, имеющий n вершин, m ребер и с компонент связности, Т — остов графа G.

Оставшиеся m - n + с ребер будем называть хордами остова Т, n - с — ветвями остова Т.

Если к лесу (дереву) добавить произвольную хорду, то в полученном графе будет ровно один цикл, и называется фундаментальным циклом относительно данной хорды.

Множество фундаментальных циклов называется фундаментальным множеством циклов графа G относительно остова графа.

Мощность фундаментального множества циклов равна цикломатическому числу v(G) = m - n + с.

Каждому фундаментальному циклу соответствует вектор а = (a_i1,…,a_im) определенный по следующему правилу:

Поэтому, фундаментальное множество циклов можно задать с помощью матрицы, строками которой являются рассмотренные векторы.

Пример: Найдем матрицу фундаментальных циклов графа G, изображенного на рисунке.

Так как v(G)) = 8-6+1 = 3, то для получения остова удаляем из графа три ребра. Сопоставим этим ребрам номера 1, 2, 3.

Ребрам, входящим в остов, поставим в соответствие номера 4, 5, 6, 7, 8.

Легко видеть, что фундаментальный цикл С1, соответствующий хорде 1, состоит ребер 1,4,6, цикл С2 – из ребер 2,6,7, С3 – из ребер 3,6,7,8 (1,4,2,7 – не подходит, т.к. хорда должна быть одна).

[подсказка: нумеруем сначала хорды, потом ветви; сколько хорд – столько циклов]