Разрезы

Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи возникают, например, при изучении потоков в сетях (сетью называется связный орграф G= потоком в сети G называется функция , которая ставит в соответствие дуги некоторое число- вес дуги). В этих задачах фундаментальную роль играют изучение поперечных сечений сети (т.е. множеств дуг, которые соединяют вершины двух непересекающихся множеств вершин) и нахождение ограниченного поперечного сечения, которое является самым узким местом. Эти узкие места определяют пропускную способность системы в целом.

Пусть G= - неорграф = разбиение множества M. Разрезом графа G (по разбиению ) называется множество всех ребер, соединяющих вершины из M₁ с вершинами из M₂ (рис. 4.46). Отметим, что в связном графе любой разрез непуст.

Непустой разрез K неорграфа G называется простым разрезом или коциклом, если любое непустое собственное подмножество K̕ K не является разрезом ни по какому разбиению. Другими словами, из K нельзя удалить ни одно ребро с тем,чтобы множество было непустым разрезом.

M₁ Разрез M₂

рис. 4.46

Теорема 4.12.1. В конечном неорграфе G= , имеющем с компонент связности, множество ребер K тогда и только тогда является коциклом, когда граф имеет (c+1) компонент связности.

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

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

Теорема 4.12.2. В связном неорграфе остовное дерево имеет по крайней мере одно общее ребро с любым из разрезов графа.

Теорема 4.12.3. В связном неорграфе любой цикл имеет с любым разрезом четное число общих ребер.

В условиях, указанных в предыдущем параграфе, рассмотрим неорграф G с остовом T. Снова пусть ветви остова T. Удаляя из остова T произвольную ветвь , получаем лес c(c+1) компонентами связности, т.е. каждое ребро является разрезом остова T по некоторому разбиению (рис. 4.47).

M₁ M₂

рис. 4.47

В графе G могут найтись еще какие-то ребра (являющиеся хордами T), которые соединяют вершины из и . Множество образует простой разрез, который называется фундаментальным разрезом графа G относительно ветви остова T. Множество всех фундаментальных разрезов графа G называется фундаментальным множеством коциклов графа G относительно остова T. Отметим, что мощность фундаментального множества коциклов не зависит от выбора остова T и равна корангу * .

Аналогично фундаментальным циклам каждому фундаментальному разрезу ставится в соответствие вектор _i , определяемый по правилу

Фундаментальное множество коциклов задается матрицей фундаментальных разрезов , строки которой являются векторами _{1, 2}, …, _v*(G):

.

Поскольку каждый фундаментальный разрез содержит ровно одну ветвь, а именно , матрица имеет вид

.

Таким образом, K= , где единичная матрица порядка . Отметим, что если C= соответствующая матрица фундаментальных циклов, то =C^T₂.

П р и м е р 4.12.1. Найдем матрицу фундаментальных разрезов графа G= , изображенного на рис. 4.45. Поскольку фундаментальных разрезов. Ребру 4 соответствует коцикл , так как при удалении ребра 4 из остова T множество вершин M разбивается на две части∶ и M\ , а ребра 1 и 4 образуют разрез по разбиению . Аналогично ребру 5 соответствует коцикл , ребру 6-коцикл , ребру 7-коцикл , ребру 8-коцикл . Следовательно, матрица фундаментальных разрезов имеет вид

.

§ 4.13. Векторные пространства,