Достижимость, связность, компоненты связности, конденсация графа

Типы графов

Орграф , в котором для любой пары существует неориентированное ребро в , называется полным. Неориентированный граф в этом случае тоже будет полным (см. рис.1.11,а, б)

Рис.1.11. Полные графы

Граф называется симметрическим (симметричным), если

а граф, для которого

называется антисимметрическим (антисимметричным). В таком графе нет петель. Примеры симметрического и антисимметрического графов приведены на рис.1.12, а, б

Рис.1.12. Симметричный – а, и антисимметричный – б графы

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

Орграф называется двудольным, если соответствующий неориентированный граф – двудольный. На рис.1.13 представлен двудольный орграф.

Рис.1.13. Двудольный граф

Матричное представление графов

Пусть задан орграф , причем

Тогда матрицей смежности орграфа называется квадратная матрица порядка , у которой:

Матрицей инцидентности (инцдиенций) орграфа называется – матрица , у которой:

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

	Таблица 1.1. Матрица смежностей	Таблица 1.2. Матрица инциденций

Рис.1.14. Орграф

Очевидно, что матрица является симметричной матрицей. По матрице смежности орграфа (графа) всегда можно определить дуги (ребра) графа и восстановить граф полностью (без нумерации дуг). То же можно и сказать о матрице инциденций, стоит только заметить, что невозможно установить вершину, к которой прикреплена петля (см. на рис.1.14 и табл.1.2.).

Можно привести очевидные свойства матриц смежности и инциденций:

1. Сумма элементов матрицы смежности равна числу дуг в графе, т.е.:

для .

2. Суммы элементов матрицы по строкам и столбцам равны полустепени исхода и захода каждой вершины соответственно, т.е.:

и .

3. В матрице инциденций для каждого столбца сумма элементов равна нулю, т.е.:

4. Любая строка матрицы является линейной комбинацией остальных строк.

5. Ранг матрицы не превосходит , где .

6. Для любого цикла в сумма столбцов матрицы , соответствующих дугам, входящим в этот цикл, равна нулевому столбцу.

Обозначим через -ю степень матрицы смежности , ; 2,3,4,…

Объединение, пересечение графов, подграфы

В силу задания графа через множества и объединением графов и называется граф

Пересечением графов , , где , называется граф

Подграфом графа называется граф такой, что и причем подграф называется остовным, если .

Порожденным подграфом называется такой подграф графа , что и.

Достижимость, связность, компоненты связности, конденсация графа

Говорят, что для орграфа вершина достижима из , если либо , либо существует путь из в (для неориентированного графа маршрут, соединяющий и ).

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

, (1.1)

где, очевидно, , и определить матрицу достижимости :

(1.2)

Через множества контрдостижимых вершин (из которых достижима ) :

определяем матрицу контрдостижимости :

(1.3)

Из определения и следует, что .

Действительно, если в матрице достижимости элемент равен 1, то это значит, что существует путь из вершины в . Но одновременно это же означает, что вершина достижима из , а это определяет в матрице равенство для элемента =1.

Если же в матрице достижимости =0, т.е. из вершины невозможно достичь , то одновременно можно утверждать, что вершина недостижима из , а это значит, что =0 для матрицы контрдостижимости.

Таким образом, мы доказали, что , а это и доказывает наше утверждение.

Для примера рассмотрим орграф на рис.1.17,а и составим для него часть множеств (рис.1.17,б) и матрицу достижимостей (рис.1.17,в).

Рис.1.17. Орграф (а) и соответствующие ему множества достижимости, контрдостижимости (б), матрица достижимости (в)

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

Граф (орграф) называется связным (сильно связным), если для любых , существует маршрут (путь) из в .

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

Орграф называется слабо связным, если связным является ассоциированный с ним неориентированный граф. Если граф (орграф) не является связным (слабо связным), то он называется несвязным.

Если в исходном графе можно выделить подграф G=(x,v), такой, что для вершин выполняется условие: достижима из и (т.е. все вершины взаимодостижимы), то такой подграф называется сильной (связной) компонентой (СК).

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

Рис.1.18. Построение конденсации графа

Если положить, что для графа построена матрица достижимости , то можно предложить эффективный метод выделения всех СК и построения конденсации.

Для этого введем матрицу, где символ обозначает прямое произведение матриц, при котором элементы матрицы () определяются соотношением . Тогда для элементов матрицы справедливо: .

Поскольку все вершины достижимы и контрдостижимы для себя же (), то . Если же для , это значит, что и , а следовательно вершина достижима из , а вершина достижима из , а следовательно, они взаимодостижимы и входят в одну СК.

Так, для графа на рис.1.18 матрицы и имеют вид:

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

Шаг 1. Установка начальных значений: .

Шаг 2. Контроль для выхода. Если идти в конец, (шаг 4), иначе к шагу 3.

Шаг 3. Выделение СК. Полагаем . Для , , формируем , , . Переходим к шагу 2.

Шаг 4. Окончание.

, .

Для графа на рис. 1.18,а в результате работы алгоритма получим таблицу пошаговых преобразований:


	Ø	Ø	Ø


Ø

Для матрицы смежности размером 3х3 получим отличные от нуля элементы:

, т.к. существует дуга, например , такая, что и ;

,т.к. существует дуга, например , такая, что и ;

,т.к. существует дуга, например , такая, что и .

Остальные элементы равны нулю. Тогда

что и отражено на рисунке 1.18,б и 1.18,в.

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

Алгоритм построения иерархической структуры графа может иметь вид:

Начальное состояние: , , , .

Шаг 1. Контроль непустоты графа. Если Æ идти в конец (шаг 4), иначе к шагу 2.

Шаг 2. Построение уровня. Для , .

Шаг 3. Формирование рабочих множеств. Удаление выделенных вершин и дуг, исходящих из них:

, , и идти к шагу 1.

Шаг 4. Вывод глубины иерархической структуры , и состава уровней , .

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

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

Рис.1.19. Компоненты сильной связности (б), (в), (г) орграфа (а)

Исходя из определения компонент сильной связности, можно утверждать, что:

Базы и антибазы

База графа определена как множество вершин таких, что:

и , (1.4)

где

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

а) ,

б) .

Антибаза графа есть множество вершин таких, что:

и . (1.5)

обладает свойством минимальности в том смысле, что удаление любой вершины из лишает ее основного свойства.

Рис.1.20. Базы и антибазы

Для графа на рис.1.20,а приведены списки баз и антибаз (рис.1.20, б, в), определяющих минимальные множества: множества – из которых достижимы остальные вершины графа, антибазы – вершины которых достижимы из какой-нибудь вершины вне антибазы .

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

Если теперь для той же организации построен граф каналов связи (с направлением передачи информации) , то очевидно, что , но . Тогда можно утверждать, что эффективная для управления этой организации «коалиция» будет являться множеством , где одна из баз графа и одна из антибаз графа , выбранные так, чтобы было минимальным.

Чтобы избежать влияния на извне (если и ), можно определить сильную базу , такую что , и , для (т.е. включить в B все вершины СК) и использовать это понятие для формирования структур управления.