19) Разрезы в графе. Фундаментальные разрезы, их связь с фундаментальными циклами.

Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что

1. , где V — множество вершин графа
2. , где s — исток, t — сток.

Величиной разреза называется сумма пропускных способностей таких рёбер (i,j), что .

Другие определения разреза (сечения) графа

• Разрез графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть отдельным узлом.
• Разрез графа — линия, делящая граф на две несвязанные части.

Характеристики

• Линии сечения могут пересекать произвольное число ребер и хорд.
• Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она пересекала только одну ветвь графа при произвольном пересечении хорд.

Разрезы графа. Фундаментальная система циклов и фундаментальная система разрезов.

2. Пусть теперь  — некоторый цикл графа . Предположим, что он не имеет общих ребер с . Тогда  целиком содержится в остове . Но это невозможно, поскольку остов есть лес, то есть граф без циклов. Теорема доказана.

 Пусть дан граф . Зафиксируем некоторый его остов . Как известно (критерии дерева), если добавить к   некоторое ребро графа  (удаленное при получении остова), то появится ровно один цикл. Множество циклов, полученных таким способом, называется фундаментальной системой циклов, ассоциированной с остовом . Ясно, что все циклы, полученные таким способом, различны и их количество равно циклическому рангу .

Так, например, если  — граф на предыдущем рисунке и  — его остов на рисунке справа, то фундаментальная система циклов , ассоциированная с остовом , следующая:

Согласно теореме о критериях дерева (пункт d)) удаление любого ребра из остова  разбивает  на две компоненты связности. Пусть  — вершины одной компоненты, а  — другой. Если добавить к такому ребру остова  другие ребра графа , соединяющие вершины  с вершинами , то получим некоторый разрез графа . Множество разрезов, полученных таким способом. Называется фундаментальной системой разрезов графа , ассоциированной с остовом . Понятно, что количество разрезов в фундаментальной системе равно числу ребер в остове, которое совпадает с рангом разрезов графа .

Для рассматриваемого графа  и его остова , получаем следующую фундаментальную систему разрезов: