Елементи теорії графів.
Граф - сукупність точок і ліній, в якій кожна лінія з'єднує дваточки. Точки називаються вершинами, або вузлами, графа, лінії - ребрамиграфа. Якщо ребро з'єднають дві вершини, то говорять, що воно їм інцідентно;вершини, з'єднані ребром називаються суміжними. Дві вершини, з'єднаніребром, можуть збігатися; таке ребро називається петлею. Число ребер,інцідентних вершині, називається ступенем вершини. Якщо два ребраінцідентни одній і тій же парі вершин, вони називаються кратними; граф,що містить кратні ребра, називається мультіграфом.
Ребро, що з'єднує дві вершини, може мати направлення від однієї вершинидо іншої; в цьому випадку воно називається спрямованим, або орієнтованим,і зображується стрілкою. Граф, у якому всі ребра орієнтовані,називається орієнтованим графом (Орграф); ребра Орграф часто називаютьдугами. Дуги іменуються кратними, якщо вони не тільки мають спільні вершини, але й збігаються за напрямком. Іноді потрібно розглядати не весь граф, айого частина (частина вершин і частина ребер). Частина вершин і всі інцідентние їмребра називаються подграфом; всі вершини і частина інцідентних їм реберназиваються суграфом. Циклом називається замкнута ланцюг вершин. Деревомназивається граф без циклів. Остовне деревом називається пов'язаний суграфграфа, що не має циклів.
Граф однозначно заданий, якщо задані безліч його вершин, безлічребер і вказані всі інцідентності (тобто вказано, які вершини якимиребрами з'єднані). Найбільш наочно граф задається малюнком, а проте невсі деталі малюнка однаково важливі; зокрема, несуттєвігеометричні властивості ребер (довжина, кривизна і т.д.) і взаємнерозташування вершин на площині.
Для неорієнтованого ребра порядок, в якому вказані що з'єднуються з нимвершини, не важливий. Для орієнтованого ребра важливо: перше вказуєтьсявершина, з якої виходить ребро.
Маршрут, або шлях - це послідовність ребер в неорієнтованіграфі, в якому кінець кожного ребра співпадає з початком наступногоребра. Число ребер маршруту називається його довжиною.
Графи широко використовуються як у самій математиці, так і в їїдодатках. Вони застосовуються при побудові різних математичнихмоделей: ліній електропередачі, мереж автодоріг, ліній повітряних сполученьі пр.
Завдання полягає в тому, знайти шлях з вершини 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; < p> 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
