Определение. Фундаментальной системой разрезов

Фундаментальной системой разрезов

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

Очевидно, что число разрезов в фундаментальной системе равно |V|-1.

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

Пример

Рассмотрим ранее приведенный граф

1 1

1. К_{(1, 2)} 2. К_{(2, 3)}

V₁={1} V₁={1, 3} 2 3

V₂={2, 3, 4, 5, 6} 2 3 V₂={2, 4, 5, 6}

5 6

2 3

3. К_{(2, 5)}

V₁={1, 2, 3}

V₂={4, 5, 6} 4 5 6

4. К_{(4, 5)} 2 5. К_{(5, 6)} 3

V₁={1, 2, 3, 5, 6} V₁={1, 2, 3, 4, 5} 6

V₂={4} 4 V₂={6}

5 5

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

К=[кij], в которой

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

К=

Число строк матрицы равно |V|-1, а число столбцов – q. Вторая часть матрицы представляет собой единичную матрицу размером (|V|-1)х(|V|-1), т.е. К=(К₁ |К₂), где К₂- единичную матрица.

Между матрицей фундаментальных циклов и матрицей фундаментальных разрезов существует следующая связь:

К₁ =С₂^Т

То есть получив одну матрицу, вторую получаем автоматом.