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 (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 <=> вершина 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 ('<=', 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
Зауважимо,
що, поки ми не повернулися в А, ми завжди можемо продовжити шлях з поточного вузла
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, i: 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, i] 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 раз вибирати найкоротший ребро з ще не вибране ребро
за умови, що воно не утворює циклу з вже обраними.
А
як стежити, щоб нове ребро не утворювали циклу зі старими? Зробити це
просто. До побудови дерева забарвленням кожну вершину i у відмінний від інших колір
i. При виборі чергового ребра, наприклад (i, j), де i і j мають різні кольори,
вершина j і все, пофарбовані в її колір (тобто раніше з нею з'єднані)
перефарбовуються в колір i. Таким чином, вибір вершин різного кольору
забезпечує відсутність циклів. Після вибору 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, 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]
