6.6. Взвешенные графы. Ориентированные графы

Ребрам графа может быть приписан вес, например, в транспортных задачах - длина дороги или пропускная способность ветки трубопровода. Чтобы не тратить дополнительную память, можно поместить веса в матрицу смежности вместо " 1". Это допустимо, если вес не может быть 0, ибо принято использовать именно 0 как признак отсутствия ребра. В нематричном представлении графа мы как элемент списка используем запись, одним из полей кото­рой является вес.

Ориентированный граф или орграф G= (V,E) отличается от графа лишь тем, что Е - это множество у п о р я д о ч е н н ы х пар <v_i, v_j> , называемых дугами. Дуга ведет от узла v_i к v_j и изображается стрелкой. Узел v_j называют преемником, v_i - его предшественником. В орграфах вместо термина цепь используют термин путь. Орграф может быть и взвешенным.

Алгоритмы для графов с небольшими изменениями или без них применимы и к орграфам. Представления - аналогичны. Матрица смежности, представляющая орграф, несимметрична: элемент А_ij =1 пред­ставляет дугу <i, j>, при этом А_ji =0, если нет дуги

<j, i>. Две дуги <i, j>, <j, i> разрешается изображать линией без стрелки.

Узел v. орграфа G достижим от v_i , если существует путь, ведущий от v_i кv_j.Сток - узел, достижимый от всех узлов, исток - узел, от которого достижимы все узлы орграфа. Орграф называют сильносвязным, если все его узлы - истоки. Очевидно, орграф, изображающий систему городских улиц (улица - дуга, перекресток и площадь - узел), сильносвязен.

Если граф не сильносвязен, произвольный выбор отправного узла не гарантирует посещения всех узлов при поиске в глубину. Поиск в глубину, выполненный n раз для каждого узла как отправного, позволяет найти истоки орграфа.

Задание 6.6.

• Составьте блок, находящий истоки орграфа поиском в глубину (вариант "а").

6.7. Нахождение фундаментального множества циклов

Задача сводится к прохождению каркаса и выявлению всех хорд (см. п.6.1). Рассмотрим два варианта из возможных.

Пример 6.5.

В блоке Cikli любой узел j, смежный с текущим, обрабатывается: посещается, если не был посещен, или инициирует вывод цикла. Исключение составляет узел - "отец" текущего узла. Так как каркас не запоминается, для вывода цикла выбирается момент, когда текущим узлом является удаленный от корня каркаса край хорды: вся простая цепь, входящая в цикл, хранится в стеке. Когда возвра­ты приведут к другому краю хорды, этой цепи в стеке нет. Узлы хорды различаются по номеру k позиции в массиве стека. Этот но­мер R[j] создается при посещении узла] (R[j]:= k). Если же узел j не посещен, R[j] = 0. ,

Constn=9; {Значение п не должно превышать 254}

Type matr=Array[1..n,1..n] of byte; vek=Array[1..n] of byte;

Const A: matr = ((0,1,0,1,0,0,0,1,0),

(1,0,1,0,0,1,0,0,0),

(0,1,0,1,1,0,1,0,0),

(1,0,1,0,0,0,1,0,0),

(0,0,1,0,0,0,0,1,1),

(0,1,0,0,0,0,0,0,0),

(0,0,1,1,0,0,0,0,0),

(1,0,0,0,1,0,0,0,0),

(0,0,0,0,1,0,0,0,0) );

Procedure Cikli (Var A:matr; X:byte);

Var R,St:vek; c:Boolean; i,j,k,L:byte;

Begin For j:=1 to n do R[j]:=0;

k:=1; St[k]:= X; R[X]:= k; j:=0;

RepeatL:= St[k]; {Начало главного .цикла поиска в глубину}

с:= false; {Ниже,- Repeat-цикл поиска смежного узла}

Repeat j:=j+1;

If j > n Then c:= true {L-ястрокаисчерпана}

Else If A[L,j]=1 Then c:=true {Смежныйузел (любой) найден}

Until с; Ifj>nThen {Шаг назад, ибо L-я строка исчерпана:}

Beginj:=L; k:=k-1 End ElseIfR[j]=0 Then {Шаг вперед, ибо узел j новый:}

Begin k:=k+1; St[k]:= j; R[j]:= k; j:= 0 End

ElseIfR[j] <k-1 Then {Выводим узлы,входящие в цикл:}

BeginWrite ('Цикл графа: ', L); {Б реальных задачах здесь стоит }

For i:= R[j] to k do Write(', ', St[i]); Writeln {вызовблокаобработкицикла}

End

Until k = 0

End;

BEGIN Cikli(A, 5); Readln;

END.

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

Пример 6.6.

Совокупность найденных циклов запоминается блоком Bazis в виде 2 массивов: массива RB, аналогичного массиву R в примере 5.3, и массива Н, каждая из m-n+1 строк которого хранит узлы - края хорды. При этом 2-й элемент строки хранит дальний от корня кар­каса край хорды.

Constn=9; m=11; {Значение n не должно превышать 254}

Type matr=Array[1..n,1..n] of byte; vek=Array[1..n] of byte;

Const A: matr = ( (0,1,0,1,0,0,0,1,0),

(1,0,1,0,0,1,0,0,0),

(0,1,0,1,1,0,1,0,0),

(1,0,1,0,0,0,1,0,0),

(0,0,1,0,0,0,0,1,1),

(0,1,0,0,0,0,0,0,0),

(0,0,1,1,0,0,0,0,0),

(1,0,0,0,1,0,0,0,0),

(0,0,0,0,1,0,0,0,0));

I

Var H:Array[1..m-n+1,1..2] of byte; RB:vek; i,j:byte;

Procedure Bazis (Var A:matr; X:byte; Var RB:vek; Var HH);

Var R,St:vek; c:Boolean; i,j,k,L:byte; nH:word;

H: Array[1..65520 div 2, 1..2] of byte Absolute HH;

Begin For j:=1 to n do R[j]:=0; nH:=0;

k:=1; St[k]:= X; R[X]:= k; j:=0;

RepeatL:= St[k]; {Начало главного цикла поиска в глубину}

с:= false; {Ниже - Repeat-цикл поиска смежного узла}

Repeat j:=j+1;

If j > n Then c:= true {L-ястрокаисчерпана}

Else If A[L,j]=1 Then c:=true {Смежныйузел (любой) найден}

Until с;

Ifj>nThen {Шаг назад, ибо L-я строка исчерпана: }

Begin j:=L; k:=k-1 End

Else If R[j]=0 Then {Шагвперед, ибоузел] новый:}

Begin k:=k+1; St[k]:= j; R[j]:= k; RB[j]:=L; j:=0 End

Else If R[j] < k-1 Then {Запоминаетсяхорда<j,L>:}

Begin nH:=nH+1; H[nH,1]:=j; H[nH,2]:=L End

Untilk = 0

End;

BEGINBazis(A, 5, RB, H); {"Обработка" циклов - это вывод, записанный ниже:}

For i:=1 to m-n+1 do

Begin j:=H[i,2]; Write(‘Цикл : ’,H[i,1],', ', j);

Repeat j:= RB[j]; Write(', ',j) Until j = H[i,1]; Writeln End; Readln;

END.

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

Задание 6.7.

• Реализуйте пример 5.5, используя как описание графа структуру с оглавлением.