Ориентированные графы

Некоторые специальные классы графов

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

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

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

Примеры двух разделяющих множеств графа G (второе разделяющее множество является подмножеством первого) показаны на рис. 6.9. Разделяющее множество, изображенное на рис. 6.9, а, разбивает граф на три компоненты, одна из которых содержит вершины множества W, обведенного кружком на рисунке. Очевидно, что для разбиения графа достаточно удалить только те ребра, которые соединяют множество вершин W с вершинами W¢=V-W. Эти ребра изображены пунктиром на рис. 6.9, b.

а) б)

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

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

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

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

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

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

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

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

Граф называется полным, если любые две различные вершины являются смежными, т.е. соединяются ребром. Обычно этот термин применяется к обыкновенным графам. Для таких графов существует только один полный граф с фиксированным числом вершин, все остальные будут ему изоморфны. Следовательно, выражение «полный граф с k вершинам» однозначно определяет граф. На рис. 6.3 изображен полный граф с пятью вершинами.

Граф называется двудольным, если его вершины могут быть разбиты на два непересекающихся подмножества V ₁ и V ₂ так, что каждое ребро имеет одну граничную точку в V ₁,а другую в V ₂. В общем случае граф называется k - дольным, если множество его вершин можно разбить на k непересекающихся подмножеств { V ₁, V ₂, …, V_k } так, что не существует ребер, соединяющих вершины одного и того же подмножества. Чтобы подчеркнуть отмеченную особенность двудольного графа, его часто изображают, размещая множества вершин V ₁ и V ₂ в разных столбцах (или строках), как показано на рис. 6.10.

Граф называется k-связным, если любая пара различных вершин v и w соединена, по крайней мере, k цепями, которые не имеют общих вершин, исключая, конечно, v и w. Например, простой цикл (исключая петли) образует 2-связный граф. При k =1 это понятие совпадает с понятием обычной связности.

Если d (v)= k для всех вершин графа, то граф называется однородным графом степени k или просто k - однородным. Например, на рис. 6.11 изображено несколько связных 3-однородных графов. Заметим, что обыкновенный полный граф, имеющий k вершин, является (k -1)-однородным.