Представление графа. Транзитивное замыкание

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

Для представления графа чаще всего используют матрицу смежности, состоящей из нулей и единиц. Пусть имеется граф из n вершин V₁, V₂, …, V_n. Элемент a_ij матрицы смежности A равен 1, если имеется дуга из вершины V_i в вершину V_j, и 0 в противоположном случае. Для неориентированных графов матрица смежности симметрическая. Вместо нулей и единиц иногда задают другую информацию. Например, для дорог элемент a_ij может задавать расстояние между пунктами или время проезда.

Главная диагональ матрицы смежности обычно не представляет интереса. Она может состоять как из 0, так и из 1. В некоторых алгоритмах это имеет значение и должно оговариваться.

Для каждой вершины V_i строка с номером i определяет возможных последователей, а i-й столбец – предшественников.

Проставим нули на главной диагонали матрицы смежности. Количество путей между вершинами V_i и V_j, состоящих ровно из двух звеньев, определяется выражением

,

где суммирование ведется по всем промежуточным вершинам, для которых есть дуги из V_i и в V_j . Приведенное выражение определяет элементы матрицы A². Аналогично, число путей, состоящих ровно из трех звеньев, определяет матрица A³, а число путей, не превышающих трех звеньев, можно задает матрица

B₃= A + A² + A³.

Можно доказать по индукции, что общее число путей между всеми парами вершин длины не более m звеньев определяется матрицей

B₃= A + A² + …+A^m.

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

Матрицей достижимости P называют матрицу из нулей и единиц, элемент p_ij которой равен 1, если имеется какой-либо путь из вершины V_i в вершину V_j, и 0 в противоположном случае. Если считать каждую вершину достижимой из самой себя, то ненулевые элементы матрицы B_n-1 определяют единицы матрицы достижимости. Иными словами, мы получим матрицу достижимости, если при вычислении B_n-1 считать, что единица кодирует истину, а ноль – ложь, и использовать логические операции AND и OR вместо умножения и сложения.

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

Пусть элемент p_ij^(k) матрицы P^(k) равен 1, если существует путь из вершины V_i в вершину V_j с номерами промежуточных вершин, не превосходящими k, и 0 в противоположном случае. Тогда выполняется рекуррентное соотношение

где в качестве сложения и умножения фигурируют логические операции OR и AND.

Действительно, если имеется путь из V_i в V_j с номерами промежуточных вершин, не превосходящими k, то оба элемента p_ij^(k) и p_ij^(k+1) равны 1. Если же такого пути нет, но он появляется при добавлении вершины V_k+1 , то этот путь обязательно проходит через V_k+1 .

В качестве P⁽⁰⁾ выбирается исходная матрица смежности. Матрица P⁽ⁿ⁾ будет транзитивным замыканием, так как в ней не остается никаких ограничений на промежуточные вершины возможных путей.

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

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

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

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

Пусть имеется граф

Приведенный способ представления приводит к следующей структуре:

Nil

Nil

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

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

Program Graph;

{ создание и распечатка графа }

Uses Crt;

Type

ukaz=^uzel;

point=^duga;

uzel=record { список вершин графа }

Nom: integer;

Next: ukaz;

Sv: point

end;

duga=record { структура дуги графа }

Next: point;

Sv: ukaz

end;

Var

A, B: integer;

L: boolean;

Top, Kon, Ua, Ub: ukaz;

P, Q: point;

Ch: char;

Begin

L:=True; Top:=Nil;

While L do

Begin

Write('Введите связи в виде пары вершин (-1 - конец) ');

Read(A);

if A=-1 then

begin

WriteLn('Ввод закончен !');

WriteLn;

L:=False

end

else

begin

Read(B);

Kon:=Top;

Ua:=Nil; Ub:=Nil;

While Kon<>Nil do

begin

if Kon^.Nom=A then Ua:=Kon;

if Kon^.Nom=B then Ub:=Kon;

if (Ua<>Nil) and (Ub<>Nil) then Kon:=Nil;

if Kon<>Nil then Kon:=Kon^.Next

end;

if Ua=Nil then { A-новая вершина }

begin

New(ua);

Ua^.Nom:=A;

Ua^.Next:=Top;

Top:=Ua;

Ua^.Sv:=Nil

end;

if Ub=Nil then { B-новая вершина }

begin

New(Ub);

Ub^.Nom:=B;

Ub^.Next:=Top;

Top:=Ub;

Ub^.Sv:=Nil

end;

if Ua^.Sv=Nil then { нет дуг у вершины A }

begin

New(p);

Ua^.Sv:=P;

P^.Next:=Nil;

P^.Sv:=Ub

end

else { есть дуги }

begin

Q:=Ua^.Sv; { первая дуга }

New(p);

P^.Next:=Q^.Next;

Q^.Next:=P;

P^.Sv:=Ub { вставка после первой дуги }

end

end

end; { конец While }

Ua:=Top;

While Ua<>Nil do

begin

WriteLn('Вершина ', Ua^.Nom);

P:=Ua^.Sv;

if P<>Nil then Write('Последователи: ')

else Write('Последователей нет !');

While P<>Nil do

begin

Kon:=P^.Sv;

B:=Kon^.Nom;

Write(B,' ');

P:=P^.Next

end;

WriteLn;

Ua:=Ua^.Next

end;

Ch:=ReadKey { пауза }

End.

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