Алгоритми на графах

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

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

Граф — сукупність крапок і ліній, де кожна лінія з'єднує дві точки. Крапки називаються вершинами, чи вузлами, графа, лінії - ребрами графа. Якщо ребро з'єднають дві вершини, то кажуть, що його їм инцидентно; вершини, з'єднані руба називаються суміжними. Дві вершини, з'єднані руба, можуть збігатися; таке ребро називається петлею. Кількість ребер, инцидентных вершині, називається ступенем вершини. Якщо два ребра инцидентны одному й тому ж парі вершин, вони називаються кратними; граф, у якому кратні ребра, називається мультиграфом.

Ребро, з'єднуюче дві вершини, може мати напрям від однієї вершини в іншу; в цьому випадку воно називається спрямованим, чи орієнтованим, і змальовується стрілкою. Граф, де всі ребра орієнтовані, називається орієнтованим графом (орграфом); ребра орграфа часто називають дугами. Дуги іменуються кратними, якщо вони лише мають загальні вершини, а й збігаються в напрямі. Іноді потрібно розглядати не весь граф, яке частина (частина вершин і частина ребер). Частина вершин і всі инцидентные їм ребра називаються подграфом; все вершини і частина инцидентных їм ребер називаються суграфом. Циклом називається замкнута ланцюг вершин. Деревом називається граф без циклів. Остовным деревом називається пов’язаний суграф графа, яка має циклов.

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

Для неориентированного ребра порядок, у якому указанны соединяемые їм вершини, не важливий. Для орієнтованого ребра важливо: першої вказується вершина, з якої виходить ребро.

Маршрут, чи шлях — це послідовність ребер в неориентированном графі, у якому кінець кожного ребра збігаються з початком наступного ребра. Кількість ребер маршруту називається його длинной.

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

Задача у тому, знайти шляхи з вершини A в вершину B. Будемо ставити граф матрицею суміжності, тобто. квадратної таблицею NxN, у якій на перетині i-го рядки — і j-го шпальти значення TRUE, якщо і і 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 <=> вершина і пройдена);

вспомогательный масив 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 (head<=tail) and not f do.

Begin.

v:=C[head];

head:=head+1;

For k:=1 to n do.

if m[v, k] and not Visited[k] then.

Begin.

tail:=tail+1;

C[tail]: =k;

Visited[k]: =True;

Prev[k]: =v;

if k=B then.

Begin.

f:=true;

break.

End.

End.

End;

if f then.

Begin.

k:=B;

Write (B);

While Prev[k]<>0 do.

Begin.

Write («<- «, Prev[k]);

k:=Prev[k].

end.

End.

else.

Write («Шляхи з », A, «в », B, «немає «).

end;

Begin.

Write («A= «); readln (A);

Write («B= «); readln (B);

A_to_B (A, B).

End.

Поиск в глубину..

Идея пошуку глибину проста: вирушаючи від поточної вершини, ми бачимо нову (ще не вивчену) суміжний із нею вершину, яку помечаем як вивчену і оголошуємо поточної. Після цього процес відновлюється. Якщо новій суміжною вершини немає (глухий кут), повертаємося до тієї вершині, з якої потрапили до поточну, і робимо таку спробу. Якщо потрапимо в вершину B, друкуємо шлях. Якщо всі вершини вичерпані - такого шляху нет.

Заметим, побудований в такий спосіб алгоритм здатні отримувати всі дороги з A в B, але перший знайдений необов’язково може бути кратчайшим.

Как зазвичай, алгоритм з поверненнями найлегше оформити з допомогою рекурсивної процедури. Для його реалізації нам понадобятся:

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

вспомогательный масив visited[1.n], який ми у тому, щоб відзначати вже пройдені вершини (visited[i]=TRUE <=> вершина і пройдена);

переменная 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 («<= «, p);

End;

Begin.

For i:=1 to n do Visited[i]: =False;

f:=false;

Depth (A);

If not f then write («Шляхи з », A, «в », B, «немає «).

End;

Begin.

write («A= «); readln (A);

write («B= «); readln (B);

A_to_B (A, B).

End.

Эйлеровы циклы..

Требуется знайти цикл, проходить з кожної дузі рівно одного разу. Це завдання вперше поставив і він вирішив Леонард Эйлер, що навіть заклав підвалини теорії графів, а відповідні цикли тепер називаються эйлеровыми.

Задача виникла із запропонованих Эйлеру головоломки, що отримала назву «проблема кенигсбергских мостів ». Річка Прегель, протека ющая через Калінінград (колись місто називався Кенігсбергом), омиває два острова. Береги річки пов’язані з островами оскільки показано малюнку. У головоломці треба було знайти маршрут, проходить за всі ділянкам суші в такий спосіб, щоб кожен із мостів пройдено рівно одного разу, а початковий і кінцевий пункти маршруту совпадали.

Выберем як вершин графа береги ріки, а ролі ребер — мости, їх що з'єднують. Після цього завдання очевидна: вимога нездійсненне — що його виконати, число дуг, які до кожної вершині, має бути четным. У насправді, оскільки з одному мосту не можна проходити двічі, кожному входу до берега має відповідати выход.

Что необхідно, щоб у графі існував эйлеров цикл? По-перше, граф може бути пов’язаним: для будь-яких двох вершин має існувати шлях, їх який би з'єднав. По-друге, для неориентированных графів число ребер у кожному вершині має бути четным. Насправді цього виявляється достаточно.

Теорема. Щоб на пов’язаному графі існував эйлеров цикл, необхідне й досить, щоб число ребер у кожному вершині було четным.

Доказательство. Необхідність доведено вище. Доказ достатності конструктивно — в результаті отримають необхідний алгоритм.

Доказательство ведеться індукцією за кількістю ребер графа. Нехай твердження доведено всім m<n. Розглянемо граф з n ребрами. Виберемо довільну вершину A й почнемо будувати необхідний шлях, вичерчуючи (стираючи) кожне ребро, яким проходимо, ніж пройти його дважды.

Заметим, що, коли ми повернулися в А, ми можемо продовжити шлях з поточного вузла X по крайнього заходу одне ребро. У насправді, кожен прохід через X залишає четным число ребер у цій вершині. Тому, коли ми входимо в X, залишається парне число невычеркнутых ребер, з її виходять (по крайнього заходу одне ребро). Нехай ми повернулися на A. Тоді, коли всі ребра викреслені, теорема доведено. Інакше решта ребра розпадаються на пов’язані подграфы, кожен із яких містить хоча б одну вершину з вже побудованого циклу (оскільки початковий граф пов’язаний) і має менш n ребер. Нехай, …, — вершини зазначених подграфов, якими проходить побудований шлях.

По припущенню індукції у кожному їх існує эйлеров цикл. Будуємо тепер новий шлях з A так:

— йдемо старому шляху до;

— включаємо до нього новий путь;

— йдемо старому шляху від до;

— повторюємо процес для вершини і т.д.

Для закінчення докази (і побудови алгоритму) зауважимо, що база індукції очевидна: якщо ребро лише те воно — петля.

Хотя доказ проведено для неориентированных графів, він одразу переноситься на орієнтовані, лише вимога парності замінюється тепер у таке: число які входять у кожну вершину ребер має бути одно числу выходящих.

Осталось помітити, що запропонований в доказі алгоритм линеен, тобто. число дій прямо пропорційно кількості ребер.

Program Euler;

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).

);

Type.

list=^node;

node=record.

i: integer;

next: list.

end;

Var stack1, stack2: list;

v, u, x, і: integer;

Procedure Push (x: integer; var stack: list);

Var temp: list;

Begin.

New (temp);

temp^.i:=x;

temp^.next:=stack;

stack:=temp.

End;

Procedure Pop (var x: integer; var stack: list);

Begin.

x:=stack^.i;

stack:=stack^.next.

End;

Function Peek (stack: list): integer;

Begin.

Peek:=stack^.i.

End;

Procedure PrintList (l: list);

Begin.

Writeln;

If l=nil then writeln («NIL »);

While l<>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<=n) and not m[v, і] do inc (i);

If i<=n then.

Begin.

u:=i;

Push (u, stack1);

m[v, u]: =False;

m[u, v]: =False;

End.

else.

Begin.

pop (x, stack1);

push (x, stack2).

End.

End;

PrintList (stack2).

End.

Задача Прима-Краскала.

Дана пласка країна й у ній n міст. Потрібно поєднати всі міста телефонної зв’язком те щоб загальна довга телефонних ліній була минимальной.

Или в термінах теорії графов:

Дан граф з n вершинами; довжини ребер задано матрицею. Знайти остовное дерево мінімальної длины.

Представим собі, що зимівнику залишено певний запас продуктів, та її завданням є складання смачного меню протягом усього зиму. Якщо зимівник почне сіло, що спочатку їстиме саму смачну їжу (наприклад, шоколад), потім — другу по смакоти (наприклад, м’ясо), він ризикує залишити на протягом останнього місяця лише сіль і маргарин. Подібною, якщо оптимальний (для визначеності, мінімальний) об'єкт будується якось по кроків, не можна першою кроці вибирати щось щонайменше, другою кроці - що залишилося щонайменше тощо. За таку політику звичайно припадає розплачуватися під час останніх кроках. Такий алгоритм називається жадным.

Удивительно, але у завданню Прима-Краскала, яка видається особливо простий, жадібний алгоритм дає точне оптимальне решение.

Как відомо (це легко довести по індукції), дерево з n вершинами має n-1 ребер. Виявляється, кожне ребро потрібно вибирати жадібно (аби тільки виникали цикли). Тобто n-1 раз вибирати найкоротший ребро із ще не обраний ребро за умови, що його не утворює циклу з роботи вже выбранными.

А як стежити, щоб нове ребро не утворювало циклу з колишніми? Зробити це просто. До побудови дерева офарбимо кожну вершину і на чудовий з інших колір і. При виборі чергового ребра, наприклад (і, j), де і і j мають різні кольору, вершина j і всі, забарвлені у її колір (тобто. раніше із нею з'єднані) перефарбовуються в колір і. Отже, вибір вершин різного кольору забезпечує відсутність циклів. Після вибору n-1 ребер все вершини отримують один цвет.

Докажем, що описаний алгоритм одержує у точності мінімальне рішення. Для докази нам знадобиться дуже просте утверждение:

Если до дерева додати ребро, то дереві з’явиться цикл, у якому це ребро.

Действительно, нехай додано ребро (u, v) — «додано» означає, що ребро — нове, що раніше від нього в дереві був. Оскільки дерево є пов’язаною графом, то існує ланцюг C (u, …, v) з кількох ребер, з'єднує вершини u і v. Додавання ребра (u, v) замикає ланцюг, перетворюючи їх у цикл.

Теорема. Алгоритм Прима-Краскала отримує мінімальне остовное дерево.

Доказательство. Результатом роботи алгоритму є набір з n-1 ребер. Не утворюють циклу, бо кожному з n-1 кроків з'єднувалися вершини різного кольору, тобто. раніше які пов’язані. Цей граф зв’язний, бо після проведення 1-го ребра залишилося n-1 різних кольорів, …, після проведення (n-1)-го ребра залишилася сама колір, тобто. одна компонента связности. Отже, отриманий набір ребер утворює зв’язний граф без циклів, у якому n-1 ребер і n вершин. Отже, граф є остовное дерево.

Для реалізації алгоритму знадобляться:

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, і, 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, і, j: integer;

Begin.

min:=infinity;

For i:=1 to n-1 do.

For j:=i+1 to n do.

If (Matrix[i, j]<min) and (color[i]<>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.

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

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.

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

Дана дорожня мережу, де міста Київ і розвилки будуть вершинами, а дороги — ребрами. Потрібна знайти найкоротшого шляху між двома вершинами.

Можно запропонувати багато процедур вирішення цього завдання, наприклад, фізичне моделювання що така: на пласкою дошці малюється карта місцевості, до міст й у розвилки вбиваются цвяхи, за кожен цвях надягається кільце, дороги вкладаються мотузками, які прив’язуються до відповідним кільцям. Щоб знайти найкоротший відстань між кільцем і і кільцем k, треба взяти і до однієї руку, взяти k до іншої і розтягти. Ті мотузки, які натянутся і дадуть розводити ширше, й утворюють найкоротшого шляху між і і k. Проте, математична процедура, яка промоделирует цю фізичну, має дуже складно. Відомі алгоритми простіше, наприклад, запропонований Дейкстрой ще 1959 р. Цей алгоритм вирішує більш загальну задачу:

В орієнтованої, неориентированной чи змішаної мережі знайти найкоротшого шляху з заданої вершини в інші вершины.

Алгоритм використовує три масиву з n чисел кожен. Перший масив Visited містить мітки з цими двома значеннями: False (вершина ще розглянута) і True (вершина вже розглянута); другий масив Len містить відстані від — поточні найкоротші відстані від початковій до відповідної вершини; третій масив З містить номери вершин — k-ый елемент З є номер передостанній вершини на поточному найкоротшому шляхи виходу з початковій вершини в k-ю. Використовується також Matrix — матриця расстояний.

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

1 (ініціалізація). У циклі від 1 до n заповнити значенням False масив Visited; заповнити числом і масив З (і - номер стартовою вершини); перенести 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).

z:=C[k];

Выдать z.

z:=C[z]. Якщо z =0, то конец, иначе можливість перейти до 3.2.

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

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, і: 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 і: integer;

Begin.

Possible:=True;

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

Possible:=False.

End;

Function Min: Integer;

Var і, minvalue, currentmin: integer;

Begin.

Minvalue:=Infinity;

For i:=1 to n do.

If not Visited[i] then.

If Len[i]<minvalue then.

Begin.

currentmin:=i;

minvalue:=Len[i].

End;

min:=currentmin.

End;

Begin.

ClrScr;

Init;

While Possible do.

Begin.

k:=min;

Visited[k]: =True;

For i:=1 to n do.

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-му буде: 823.

Список литературы

Для підготовки даної праці були використані матеріали із російського сайту internet.