Aлгоритмы на графах

Aлгоритмы на графах

Элементы теории графов.

Граф - совокупность точек и линий, в которой каждая линия соединяет две

точки. Точки называются вершинами, или узлами, графа, линии - ребрами

графа. Если ребро соединят две вершины, то говорят, что оно им инцидентно;

вершины, соединенные ребром называются смежными. Две вершины, соединенные

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

инцидентных вершине, называется степенью вершины. Если два ребра

инцидентны одной и той же паре вершин, они называются кратными; граф,

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

Ребро, соединяющее две вершины, может иметь направление от одной вершины

к другой; в этом случае оно называется направленным, или ориентированным,

и изображается стрелкой. Граф, в котором все ребра ориентированные,

называется ориентированным графом (орграфом); ребра орграфа часто называют

дугами. Дуги именуются кратными, если они не только имеют общие вершины,

но и совпадают по направлению. Иногда нужно рассматривать не весь граф, а

его часть (часть вершин и часть ребер). Часть вершин и все инцидентные им

ребра называются подграфом; все вершины и часть инцидентных им ребер

называются суграфом. Циклом называется замкнутая цепь вершин. Деревом

называется граф без циклов. Остовным деревом называется связанный суграф

графа, не имеющий циклов.

Граф однозначно задан, если заданы множество его вершин, множество

ребер и указаны все инцидентности (т.е. указано, какие вершины какими

ребрами соединены). Наиболее наглядно граф задается рисунком; однако не

все детали рисунка одинаково важны; в частности, несущественны

геометрические свойства ребер (длинна, кривизна и т.д.) и взаимное

расположение вершин на плоскости.

Для неориентированного ребра порядок, в котором указанны соединяемые им

вершины, не важен. Для ориентированного ребра важно: первой указывается

вершина, из которой выходит ребро.

Маршрут, или путь - это последовательность ребер в неориентированном

графе, в котором конец каждого ребра совпадает с началом следующего

ребра. Число ребер маршрута называется его длинной.

Графы широко используются как в самой математике, так и в ее

приложениях. Они применяются при построении различных математических

моделей: линий электропередачи, сетей автодорог, линий воздушных сообщений

и пр.

Задача состоит в том, найти путь из вершины A в вершину B. Будем

задавать граф матрицей смежности, т.е. квадратной таблицей NxN, в

которой на пересечении i-й строки и j-го столбца значение TRUE, если i и j

соединены ребром, и FALSE в противном случае.

Поиск в ширину.

Подобно тому как, согласно принципу Гюйгенса, каждая точка волнового

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

вершины A, посещаем все смежные с ней вершины (т.е. вершины, в которые

ведут стрелки из A). Каждая посещенная вершина становится источником новой

волны и т.д. При этом необходимо позаботиться о том, чтобы не вернутся в

ту вершину, в которой уже были.

Для реализации алгоритма понадобятся:

матрица m[1..n, 1..n] - матрица смежности графа;

вспомогательный массив queue[1..n], в котором будет формироваться

очередь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его

достаточен, так как мы не посещаем вершины дважды. С массивом queue

связаны две переменные - head и tail. В переменной head будет находиться

номер текущей вершины, из которой идет волна, а при помощи переменной

tail новые вершины помещаются в "хвост" очереди queue;

вспомогательный массив visited[1..n], который нужен для того, чтобы

отмечать уже пройденные вершины (visited[i]=TRUE вершина i пройдена);

вспомогательный массив prev[1..n] для хранения пройденных вершин. В

этом массиве и будет сформирован искомый путь;

переменная f, которая примет значение TRUE, когда путь будет найден.

Кроме того, мы введем несколько вспомогательных переменных, которые

понадобятся при организации циклов.

Program breadth_first_search;

Const n=9;

m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False,

False),

(True, False, True, False, False, False, True, True,

False),

(True, True, False, True, True, False, False, False,

False),

(False, False, True, False, True, False, False, False,

False),

(False, False, True, True, False, True, False, True,

False),

(False, False, False, False, True, False, True, True, True

),

(False, True, False, False, False, True, False, True, True

),

(False, True, False, False, True, True, True, False,

False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B: integer;

Procedure A_to_B(A, B: integer);

Var

Visited: array[1..n] of boolean;

Prev: array[1..n] of integer;

c: array[1..n] of integer;

head, tail: integer;

f: boolean;

i, v, k: integer;

Begin

head:=1;

tail:=1;

f:=False;

For i:=1 to n do

Begin

Visited[i]:=False;

Prev[i]:=0

End;

C[tail]:=A;

Visited[A]:=True;

While (head0 do

Begin

Write(' вершина i пройдена);

переменная f, которая примет значение TRUE, когда путь будет найден.

Program depth_first_search;

Const n=9;

m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False,

False),

(True, False, True, False, False, False, True, True,

False),

(True, True, False, True, True, False, False, False,

False),

(False, False, True, False, True, False, False, False,

False),

(False, False, True, True, False, True, False, True,

False),

(False, False, False, False, True, False, True, True, True

),

(False, True, False, False, False, True, False, True, True

),

(False, True, False, False, True, True, True, False,

False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B: integer;

Procedure A_to_b(A, B: integer);

Var

Visited: array[1..n] of boolean;

f: boolean;

i: integer;

Procedure Depth(p: integer);

var k: integer;

Begin

Visited[p]:=True;

For k:=1 to n do

If not f then

If m[p, k] and not Visited[k] then

If k=B then

Begin

f:=True;

Write(B);

Break

End

else Depth(k);

If f then write('nil do

Begin

Write(l^.i:3);

l:=l^.next

End

End;

Begin

stack1:=nil;

stack2:=nil;

Write('Начальная вершина: ');readln(v);

Push(v, stack1);

While stack1<>NIL do

Begin

v:=peek(stack1);

i:=1;

While (i[pic]. Выбросим из полученного графа с одним циклом ребро d; мы снова

получим дерево, но оно будет на d-[pic] короче минимального, что

невозможно. Полученное противоречие доказывает теорему для сети со всеми

разными ребрами.

Для реализации алгоритма понадобятся:

Matrix – матрица расстояний, значение пересечении i-ой строки и j-го

столбца равно расстоянию между i-ой и j-ой вершинами. Если такого ребра

нет то значение равно Infinity – просто большому числу (машинная

бесконечность);

Color – массив цветов вершин;

Ribs – в этом массиве запоминаются найденные ребра;

a, b – вершины, соединяемые очередным минимальным ребром

len – длина дерева.

Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на

первой строке – количество вершин n, а остальные n строк по n чисел в

каждой – матрица расстояний. Если расстояние равно 1000 (Infinity), то

такого ребра нет.

Program Algorithm_PrimaKrascala;

Uses Crt;

Const MaxSize =100;

Infinity =1000;

Var Matrix: array[1..MaxSize, 1..MaxSize] of integer;

Color: array[1..MaxSize] of integer;

Ribs: array[1..MaxSize] of record

a, b: integer;

end;

n, a, b, k, col, i, len: integer;

Procedure Init;

Var f: text;

i, j: integer;

Begin

Assign(f, 'INPUT.MTR');

Reset(f);

Readln(f, n);

For i:=1 to n do

Begin

For j:=1 to n do read(f, matrix[i, j]);

Readln(f)

End;

For i:=1 to n do color[i]:=i;

len:=0

End;

Procedure Findmin(var a, b: integer);

Var min, i, j: integer;

Begin

min:=infinity;

For i:=1 to n-1 do

For j:=i+1 to n do

If (Matrix[i, j]color[j]) then

Begin

min:=Matrix[i, j];

a:=i;

b:=j

End;

len:=len+min

end;

Begin

Clrscr;

Init;

For k:=1 to n-1 do

Begin

Findmin(a, b);

Ribs[k].a:=a;

Ribs[k].b:=b;

col:=Color[b];

For i:=1 to n do

If color[i]=col then color[i]:=color[a];

End;

For i:=1 to n-1 do

Writeln(ribs[i].a, ' –', ribs[i].b);

Writeln('Length= ', len);

Readkey

End.

Для такого входного файла

8

0 23 12 1000 1000 1000 1000 1000

23 0 25 1000 22 1000 1000 35

12 25 0 18 1000 1000 1000 1000

1000 1000 18 0 1000 20 1000 1000

1000 22 1000 1000 0 23 14 1000

1000 1000 1000 20 23 0 24 1000

1000 1000 1000 1000 14 24 0 16

1000 35 1000 1000 1000 1000 16 0

программа напечатает:

1–3

5–7

7–8

3–4

4–6

2–5

1–2

Length= 125.

Алгоритм Дейкстры.

Дана дорожная сеть, где города и развилки будут вершинами, а дороги –

ребрами. Требуется найти кратчайший путь между двумя вершинами.

Можно предложить много процедур решения этой задачи, например, физическое

моделирование такого рода: на плоской доске рисуется карта местности, в

города и в развилки вбиваются гвозди, на каждый гвоздь надевается кольцо,

дороги укладываются веревками, которые привязываются к соответствующим

кольцам. Чтобы найти кратчайшее расстояние между кольцом i и кольцом k,

нужно взять i в одну руку, взять k в другую и растянуть. Те веревки,

которые натянутся и не дадут разводить шире, и образуют кратчайший путь

между i и k. Однако, математическая процедура, которая промоделирует эту

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

предложенный Дейкстрой еще в 1959 г. Этот алгоритм решает более общую

задачу:

В ориентированной, неориентированной или смешанной сети найти кратчайший

путь из заданной вершины во все остальные вершины.

Алгоритм использует три массива из n чисел каждый. Первый массив Visited

содержит метки с двумя значениями: False (вершина еще не рассмотрена) и

True (вершина уже рассмотрена); второй массив Len содержит расстояния от –

текущие кратчайшие расстояния от начальной до соответствующей вершины;

третий массив C содержит номера вершин – k-ый элемент C есть номер

предпоследней вершины на текущем кратчайшем пути из начальной вершины в k-

ю. Используется также Matrix – матрица расстояний.

Опишем алгоритм Дейкстры:

1 (инициализация). В цикле от 1 до n заполнить значением False массив

Visited; заполнить числом i массив C (i – номер стартовой вершины);

перенести i-ю строку матрицы Matrix в массив Len;

Visited[i]:=True; C[i]:=0;

2 (общий шаг). Найти минимум среди неотмеченных (т.е. тех к, для которых

Visitid[k]=False); пусть минимум достигается на индексе j, т.е.

Len[j](Len[k];

Затем выполнять следующие операции:

Visited[i]:=True;

если Len[k]>Len[j]+Matrix[j, k], то (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j)

{Если все Visited[k] отмечены, то длина пути от [pic] до [pic] равна C[k].

Теперь надо перечислить вершины, входящие в кратчайший путь}.

3 (выдача ответа). {Путь от [pic] до [pic] выдается в обратном порядке

следующей процедурой:}

1 z:=C[k];

2 Выдать z

3 z:=C[z]. Если z =0, то конец,

иначе перейти к 3.2.

Теорема. Алгоритм Дейкстры – корректен.

Доказательство. Теорему докажем по индукции. Рассмотрим 1-й шаг, когда

находится min Len[k] (k(i), пусть минимум достигается на вершине j.

Остальные [pic](k(i, j) пока лишь верхние оценки длин путей из [pic] в

[pic](они могут уменьшаться в ходе выполнения алгоритма, но Len[j] –

окончательная длина пути [[pic] … [pic]], совпадающего с дугой [[pic],

[pic]]. Если бы существовал путь короче, он бы выглядел [[pic],

[pic]…[pic]], но уже первая его дуга не меньше, чем весь путь [[pic],

[pic]], а остальные дуги имеют положительную длину).

Мы разбили все вершины на два класса: С – неотмеченных вершин и С’ –

отмеченных вершин. После 1-го общего шага [pic], [pic]( С’, и, очевидно,

все кратчайшие пути (пока “все” – означает “один”) из v’(С’ не содержат v(С

в качестве промежуточной.

Теперь сделаем индуктивный шаг. Уже проделано s общих шагов, уже

С’={[pic], [pic], [pic], …, [pic]}, при этом все кратчайшие пути из [pic] в

v’ не содержат вершин из С в качестве промежуточных.

Найдем минимальное Len[l] в неотмеченных столбцах; пусть минимум

достигается на вершине [pic]. Соответственный элемент [pic], меняясь, мог

принимать только номера отмеченных вершин, значит в вершину [pic] идет

путь, где все вершины, кроме конечной [pic], – штрихованные, т.е.

принадлежащие С’. Любой другой путь [[pic] … [pic]], содержащий хотя бы еще

одну не штрихованную вершину, будет длиннее. Теорема доказана.

Uses Crt;

Const MaxSize=10;

Infinity=1000;

Var Mattr: array [1..MaxSize, 1..MaxSize] of integer;

Visited: array [1..MaxSize] of boolean;

Len,Path: array [1..MaxSize] of integer;

n, Start, Finish, k, i: integer;

Procedure Init;

Var f: text;

i, j: integer;

Begin

Assign(f, INPUT.MTR');

Reset(f);

Readln(f, n);

For i:=1 to n do

Begin

For j:=1 to n do Read(f, mattr[i,j]);

Readln(f)

End;

Write('Начальная вершина: '); Readln(Start);

For i:=1 to n do

Begin

Visited[i]:=False;

Len[i]:=Mattr[Start, i];

Path[i]:=Start

End;

Path[Start]:=0;

Visited[Start]:=True

End;

Function Possible: Boolean;

Var i: integer;

Begin

Possible:=True;

For i:=1 to n do If not Visited[i] then Exit;

Possible:=False

End;

Function Min: Integer;

Var i, minvalue, currentmin: integer;

Begin

Minvalue:=Infinity;

For i:=1 to n do

If not Visited[i] then

If Len[i]Len[k]+Mattr[i, k] then

Begin

Len[i]:=Len[k]+Mattr[i, k];

Path[i]:=k

End

End;

Write('Конечная вершина: '); Readln(Finish);

Write(Finish);

Finish:=Path[Finish];

While Finish<>0 do

Begin

Write('<-', Finish);

Finish:=Path[Finish];

End;

ReadKey

End.

Например, для сети, описанной в предыдущей главе, кратчайший путь из 3-ей

вершины в 8-ю будет: 8(2(3.