2.6. Разрез
Определим понятие «разрез» которое связано с понятием «разрезающее множество».
Рассмотрим связный граф G с множеством вершин V. Пусть
— два таких непересекающихся подмножества множества V, что
не имеют общих вершин, а вместе содержат все вершины множества V. Тогда множество S всех тех
Рис. 2.6. Определение разреза. а — граф
; б — разрез
графа
.
ребер, которые имеют одну вершину в
а другую — в
называется разрезом графа G. Разрез обычно обозначается через
. В работе [2.2] разрез называется разделителем (множество ребер, разделяющих множество вершин У).
В качестве примера рассмотрим граф G, изображенный на рис. 2.6. Если
, то разрез
— это множество ребер
Отметим, что разрез
графа G является минимальным множеством ребер, удаление которых из графа G разбивает исходный граф на два графа
являющиеся порожденными подграфами на множествах вершин
соответственно. Графы
могут быть несвязными. Если оба эти графа связные, то
по-прежнему минимальное множество ребер, разделяющих граф G точно на две компоненты. Тогда по определению
есть разрезающее множество графа
Предположим, что для разрезающего множества S графа G величины
являются соответственно множествами вершин двух компонент
графа
. Тогда S есть разрез
. Таким образом, имеет место следующая теорема:
Теорема 2.6. 1. Разрез
связного графа G есть разрезающее множество графа G, если соответствующие подграфы G, порожденные на множествах вершин
связные. 2. Если S — разрезающее множество связного графа G, а
— множества вершин двух компонент
то
Любой разрез
в связном графе G содержит разрезающее множество, так как удаление
из графа G переводит последний в несвязный граф. Фактически мы можем доказать, что разрез в графе G является объединением нескольких реберно-непересекающихся разрезающих множеств графа G. Формально мы утверждаем это в следующей теореме:
Теорема 2.7. Разрез в связном графе G есть объединение нескольких реберно-непересекающихся разрезающих множеств графа G. Доказательство этой теоремы несложно, поэтому оставим его в качестве упражнения 2.19.
Рис. 2.7. Иллюстрация теоремы 2.8. а — граф G; б — подграф графа G, порожденный на множестве вершин
рассмотрим вершину
в связном графе G. Множество ребер, инцидентных вершине
образует разрез
-Удаление этих ребер разбивает граф G на два подграфа. Один из них, содержащий только одну вершину
является связным по определению. Другой является порожденным подграфом G графа G на множестве вершин
. Поэтому разрез
является разрезающим множеством тогда и только тогда, когда подграф G является связным. Но подграф G является связным в том и только в том случае, когда
не является точкой сочленения (разд. 1.7). Таким образом, имеем следующую теорему:
Теорема 2.8. Множество ребер, инцидентных вершине v в связном графе G, есть разрезающее множество тогда и только тогда, когда v не является точкой сочленения в графе G. В качестве примера рассмотрим разделимый граф G, представленный на рис.
— точка сочленения графа G. Подграф графа G, порожденный на множестве вершин
изображен на рис. 2.7, 6. Этот подграф состоит из трех компонент и не связен. Поэтому ребра, инцидентные точке сочленения
не образуют разрезающего множества графа