Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа

По аналогии с графом достижимости определим граф сильной достижимости.

Определение:Пусть– ориентированный граф.Граф сильной достижимостидляимеет тоже множество вершини следующее множество рёберв графевершиныивзаимно достижимы.

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

По матрице можно выделить компоненты сильной связности графаследующим образом:

• поместим в компоненту вершинуи все такие вершины, что;

• пусть уже построены компоненты ,…,и– это вершина с минимальным номером, ещё не попавшая в компоненты; тогда поместим в компонентувершинуи все такие вершины, что;

Повторяем второй шаг до тех пор, пока все вершины не будут распределены по компонентам.

В нашем примере для графа примера 14.1. по матрицеполучаем следующую матрицу графа сильной достижимости

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

Определение:Пустьи– компоненты сильной связности графа. Компонентадостижимаиз компоненты, еслиили существуют такие две вершиныи, чтодостижима из.строго достижима из, еслиидостижима из. Компонентаназывается минимальной, если она не является строго достижимой ни из какой компоненты.

Так как все вершины в одной компоненте взаимно достижимы, то нетрудно понять, что отношения достижимости и строгой достижимости на компонентах не зависят от выбора вершин и.

Из определения легко выводится следующая характеристика строгой достижимости.

Лемма:Отношение строгой достижимости является отношением частичного порядка, т.е. оно антирефлексивно, антисимметрично и транзитивно.

Это отношение можно представлять в виде ориентированного графа, вершинами которого являются компоненты, а ребро означает, чтострого достижима из. Ниже показан граф компонент для графа примера 14.1.

В данном случае имеется одна минимальная компонента .

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

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

Следующая теорема позволяет эффективно находить все базы графа.

Теорема:Пусть - ориентированный граф. Подмножество вершин является базой тогда и только тогда, когда содержит по одной вершине из каждой минимальной компоненты сильной связности и не содержит никаких других вершин.

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

Обратно, если является базой, то оно обязано включать хотя бы по одной вершине из каждой минимальной компоненты, иначе вершины такой минимальной компоненты окажутся недоступны. Никаких других вершинсодержать не может, так как каждая из них достижима из уже включённых вершин.

Из этой теоремы вытекает следующая процедура построения одной или перечисления всех баз графа :

• найти все компоненты сильной связности ;

• определить порядок на них и выделить минимальные относительно этого порядка компоненты;

• породить одну или все базы графа, выбирая по одной вершине из каждой минимальной компоненты.

Пример 14.3:Определим все базы ориентированного графа .

На первом этапе находим компоненты сильной связности :

На втором этапе строим граф строгой достижимости на этих компонентах.

Определяем минимальные компоненты: ,и.

Наконец перечисляем все четыре базы :,,и.