1.9. Разделяющие множества и разрезы

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

Перед тем, как дать формальное определение разреза, введем более общее понятие. Пусть связный граф и подмножество множества его ребер. При этом называется разделяющим множеством тогда и только тогда, когда подграф несвязен. Здесь через обозначено множество ребер, которые принадлежат но не принадлежат Разделяющие множества всегда существуют (если граф имеет, по крайней мере, две вершины), так как всегда можно положить В дальнейшем без ограничения общности будем считать, что рассматриваемые графы не имеют петель, так как петли не влияют на связность графа.

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

которые соединяют множество вершин с вершинами Эти ребра изображены пунктиром на рис.

Рис. 1.9.

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

Особый интерес для изучения представляют минимальные разделяющие множества, т. е. такие разделяющие множества, которые не содержат собственного подмножества, разделяющего граф. Минимальные разделяющие множества называются простыми разрезами. Из предыдущих определений ясно, что простой разрез обязательно является разрезом, однако не каждый разрез является простым. Например, разрез, изображенный на рис. не является простым. В общем случае, если удаление ребер, принадлежащих разрезу делит граф на три или более компоненты, то разрез не может быть простым. В самом деле, возвращение любого одного ребра из может соединить не более двух компонент, и граф, полученный в результате, будет содержать все же, по крайней мере; две компоненты, что и означает

существование собственного подмножества разреза рассекающего граф.

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

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

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

Рис. 1.10.

Двигаясь по цепи мы все время остаемся в или переходим из множества и обратно четное число раз. Отсюда следует

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

Упражнения

(см. скан)

(см. скан)