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. Этот подграф состоит из трех компонент и не связен. Поэтому ребра, инцидентные точке сочленения не образуют разрезающего множества графа