Определение. Фундаментальная система циклов

Фундаментальная система циклов

Дан граф G=(V, E). Пусть T=(V, E_T) – некоторое остовное дерево графа G. Если G – связный граф, то остовное дерево всегда существует. Если же G - несвязный граф, то можно построить остовные деревья для каждой компоненты связности.

Определение

Кодеревом остова Т называется подграф графа G - T*=(V*, E*), такой что V*=V, E*=E\ E_T

Пример

1 2 1 2 1 2

3 4 3 4 3 4

Граф Остовное дерерво Кодерево

Определение

Ребра кодерева называются хордами

Очевидно, что добавление в остовное дерево хорды e E* будет порождать ровно один простой цикл, обозначим его Ze.

Определение

Фундаментальной системой циклов

Z={Ze} _{e E*}

называется система простых циклов, определенных выбранным остовным деревом.

Определение

Число фундаментальных циклов называется циклическим рангом или цикломатическим числом графа G=(V, E):

m(G)=q-p+k, где q=|E|, p=|V|, k- число компонент связности графа.

Пример

1 1 1

(1) (5)

2 (6) 3 2 3 2. 3

(2) (7) (3) (4)

4 (8) 5 (9) 6 4 5 6 4 5 6

Граф остовное дерево кодерево

Система фундаментальных циклов

1 2 2 3 2 3

2 3 4 5 5 5 6

1. Z_{(1, 2)} 2. Z_{(2, 4)} 3. Z_{(3, 5)} 4. Z_{(3, 6)}

Определим такое понятие как матрица фундаментальных циклов

С=[cij], в которой

Построим фундаментальную матрицу циклов для нашего примера. Для этого пронумеруем все ребра исходного графа. Сначала нумеруем хорды кодерева, а затем ребра остовного дерева.

С=

Число строк матрицы равно m(G), а число столбцов – q. Первая часть матрицы представляет собой единичную матрицу размером m(G)x m(G), т.е. С=(С₁ |С₂), где С₁- единичную матрица.

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