.: Menu :.
Home
Реферати
Книги
Конспекти уроків
Виховні заходи
Зразки документів
Реферати партнерів
Завантаження
Завантажити
Електронні книги


????????...

 
��������...
Орієнтовані графи 


Орієнтовані графи

Орієнтовані графи
У багатьох задачах, що зустрічаються в комп'ютерних науках, математиці, технічних дисциплінах часто виникає необхідність наочного представлення взаємозв’язків між якими-небудь об'єктами. Орієнтовані і неорієнтовані графи — природна модель для таких відношень. В цьому розділі розглянуті основні структури даних, які застосовуються для представлення орієнтованих графів, а також описані деякі основні алгоритми визначення зв'язності орієнтованих графів і знаходження найкоротших шляхів.
6.1. Основні визначення
Орієнтований граф (або скорочено орграф) G = (V, Е) складається з безлічі вершин V і безліч дуг Е. Вершини також називають вузлами, а дуги — орієнтованими ребрами. Дуга представляється у вигляді впорядкованої пари вершин (v,w), де вершина v називається початком, а w — кінцем дуги. Дугу (v, w) часто записують як v → w і зображають у вигляді

Говорять також, що дуга v → w веде від вершини v до вершини w, а вершина w суміжна з вершиною v.
Приклад 1. На мал. 6.1 показаний орграф з чотирма вершинами і п'ятьма дугами.

Мал. 6.2. Орієнтований граф
Вершини орграфа можна використовувати для представлення об'єктів, а дуги — для зв’язків між об'єктами. Наприклад, вершини орграфа можуть представляти міста, а дуги — маршрути рейсових польотів літаків з одного міста в іншій.
Шляхом в орграфі називається послідовність вершин v1 , v2, …-, vn для якої існують дуги v1 → v2,,… vn-1 → vn,  Цей шлях починається у вершині v1 і, проходячи через вершини v2, …, vn-1 закінчується у вершині vn. Довжина шляху — кількість дуг, що становлять шлях, в даному випадку довжина шляху рівна n – 1. Як особливий випадок шляху розглянемо одну вершину v як шлях довжини 0 від вершини v до цієї ж вершини w. На мал. 1 послідовність вершин 1, 2, 4 утворюють шлях довжини 2 від вершини 1 до вершини 4.
Шлях називається простим, якщо всі вершини на ньому, за виключенням, можливо, першої і останньої, різні. Цикл — це простий шлях довжини не менше 1, який починається і закінчується в одній і тій же вершині. На мал. 1 вершини 3, 2, 4, 3 утворюють цикл довжини 3.
У багатьох додатках зручно до вершин і дуг орграфа приєднати будь-яку інформацію. Для цих цілей використовується помічений орграф, тобто орграф, у якого кожна дуга і/або кожна вершина має відповідні мітки. Міткою може бути ім'я, вага або вартість (дуги), або значення даних якого-небудь заданого типу.
Приклад 2. На мал. 6.2 показаний помічений орграф, в якому кожна дуга має буквену мітку. Цей орграф має цікаву властивість: будь-який цикл, що починається у вершині 1, породжує послідовність букв а і b, в якій завжди парна кількість букв а і b.







Мал. 6.2 Помічений орграф
У поміченому орграфі вершина може мати як ім'я, так і мітку. Часто мітки вершин ми використовуватимемо як імена вершин. Так, на мал. 6.2 числа, поміщені у вершини, можна інтерпретувати як імена вершин і як мітки вершин.
6.2. Представлення орієнтованих графів
Для представлення орієнтованих графів можна використовувати різні структури даних. Вибір структури даних залежить від операторів, які застосовуватимуться до вершин і дуг орграфа. Одним з найбільш загальних представлень орграфа G= (V, Е) є матриця суміжності. Припустимо, що безліч вершин V = {1, 2, .... n). Матриця суміжності для орграфа G — це матриця А розміру n х n із значеннями булевого типа, де A[i, f]= true тоді і тільки тоді, коли існує дуга з вершини і у вершину j. Часто в матрицях суміжності значення true замінюється на 1, а значення false — на 0. Час доступу до елементів матриці суміжності залежить від розмірів множини вершин і множини дуг. Представлення орграфа у вигляді матриці суміжності зручно застосовувати в тих алгоритмах, в яких треба часто перевіряти існування даної дуги.
Узагальненням описаного представлення орграфа за допомогою матриці суміжності можна вважати представлення поміченого орграфа також за допомогою матриці суміжності, але у якої елемент A[i, j] рівний мітці дуги і —> j. Якщо дуги від вершини і до вершини j не існує, то значення A[i, j] не може бути значенням будь-якої допустимої мітки, а може розглядатися як "порожній" осередок.
Приклад 3. На мал. 6.3 показана матриця суміжності для поміченого орграфа з мал. 6.2. Тут дуги представлені міткою символьного типа, а пропуск використовується за відсутності дуг.
_Основний недолік матриць суміжності полягає в тому, що вона вимагає Ω(n2) об'єму пам'яті, навіть якщо дуг значно менше, ніж п2. Тому для читання матриці або знаходження в ній необхідного елементу потрібен час близько O(n), що не дозволяє створювати алгоритми з часом O(n) для роботи з орграфами, що мають порядку O(n) дуг.

Мал.6.3. Матриця суміжності для  поміченого орграфа з мал. 6.2.
Тому замість матриць суміжності часто використовується інше представлення для орграфа G = (V, Е),що має назву представлення за допомогою списків суміжності. Списком суміжності для вершини і називається список всіх вершин, суміжних з вершиною і, причому певним чином впорядкований. Таким чином, орграф G можна представити за допомогою масиву HEAD (Заголовок), чий елемент НЕАD[і] є покажчиком на список суміжності вершини і. Представлення орграфа за допомогою списків суміжності вимагає для зберігання об'єм пам'яті, пропорційний сумі кількості вершин і кількості дуг. Якщо кількість дуг має порядок O(n), то і загальний об'єм необхідної пам'яті має такий же порядок. Але і для списків суміжності час пошуку певної дуги може мати порядок O(n), оскільки такий же порядок може мати кількість дуг певної вершини.
Приклад 4. На мал. 6.4 показана структура даних, що представляє орграф з мал. 6.1 за допомогою зв'язаних списків суміжності. Якщо дуги мають мітки, то їх можна зберігати в осередках зв'язаних списків.







Мал. 6.4. Структура списків суміжності для орграфа із 6.1

Для вставки і видалення елементів у списках суміжності необхідно мати масив HEAD, що містить посилання на комірки заголовків списків суміжності, а не на самі суміжні вершини. Але якщо відомо, що граф не піддаватиметься змінам (або вони будуть незначні), то бажано зробити масив HEAD масивом посилань на масив ADJ (від adjacency — суміжність), де комірки ADJ[HEAD[i]] ADJ[HEAD[i\ + 1] і т.д. містять вершини, суміжні з вершиною і, і ця послідовність суміжних вершин закінчується першим нулем, що зустрічається в масиві ADJ. Приклад такого представлення для графа з мал. 6.1 показаний на мал. 6.5.









Мал. 6.5. Інше представлення списків
суміжності для графа із мал.6.1


АТД для орієнтованих графів
За звичною схемою спочатку треба формально визначити абстрактні типи даних, відповідні орієнтованим графам, а потім розглянути оператори, що виконуються над цими АТД. Але ми не будемо неухильно дотримуватися даної схеми, оскільки на цьому шляху нас не будуть чекати несподіванки, а принципові структури даних, використовувані для представлення орграфів, вже були описані раніше. Найбільш загальні оператори, що виконуються над орієнтованими графами, включають оператори читання міток вершин і дуг, вставки і видалення вершин і дуг і оператора переміщення по послідовностях дуг.
Останній оператор вимагає деяких пояснень. Часто в програмах зустрічаються оператори, які неформально можна описати подібно до наступного оператора:
for кожна вершина w, суміжна з вершиною v do
{деякі дії з вершиною w }    (6.1)
Для реалізації такого оператора необхідний індексний тип даних для роботи з безліччю вершин, суміжних із заданою вершиною v. Наприклад, якщо для представлення орграфа використовуються списки суміжності, то індекс — це позиція в списку суміжності вершини v. Якщо застосовується матриця суміжності, тоді індекс — ціле число, відповідне суміжній вершині. Для перегляду множини суміжних вершин необхідні наступні три оператори.
1.    FIRST(v) повертає індекс першої вершини, суміжної з вершиною v. Якщо вершина v не має суміжних вершин, то повертається «нульова» вершина Λ.
2.    NEXT(v, і) повертає індекс вершини, суміжної з вершиною v, який слідує за індексом і. Якщо і — це індекс останньої вершини, суміжної з вершиною v, то повертається Λ.
3.    VERTEX(v, і) повертає вершину з індексом і з множини вершин, суміжних з v.
Приклад 6.5. Якщо для представлення орграфа використовується матриця суміжності, то функція VERTEX(v, і) просто повертає індекс і. Реалізація функцій FIRST(v) і NEXT(v, і) представлена в тексті програми 6.1. В цьому тексті програми матриця суміжності А розміру n х n визначена поза цими функціями оголошується наступним чином:
array [1..n, 1..n] of boolean
У цій матриці 0 означає відсутність дуги. Ці функції дозволяють реалізувати оператор (6.1) так, як показано в тексті програми 6.2. Відзначимо, що функцію FIRST(v) можна реалізувати як NEXT(v, 0).
Текст програми 6.1. Оператори перегляду множини суміжних вершин
function FIRST ( v: integer ): integer;
var
i : integer;
begin
for і:= 1 to n do
if A[v, i] then
return(і);
return(0) {вершина v не має суміжних вершин}
end; {FIRST)
function NEXT(v: integer; i: integer): integer;
var
j: integer;
begin
for j:= і + 1 to n do
if A[v, j] then
return(j);
return(0)
end; {NEXT}
Текст програми 6.2. Послідовний перегляд вершин, суміжних з вершиною v
і:=FIRST(v);
while і <> 0 do begin
w:= VERTEX(v, i);
{дії з вершиною w}
і:=NEXT(v, і)
end

6.3. Задача знаходження найкоротшого шляху
У цьому розділі ми розглянемо задачу знаходження шляхів в орієнтованому графі. Нехай є орієнтований граф G = (V, Е), у якого всі дуги мають невід’ємні мітки (вартості дуг), а одна вершина визначена як джерело. Задача полягає у знаходженні вартості найкоротших шляхів від джерела до всіх інших вершин графа G (тут довжина шляху визначається як сума вартостей дуг, що становлять шлях). Ця задача часто називається задачею знаходження найкоротшого шляху з одним джеоелом). Відзначимо, що ми говоритимемо про довжину шляху навіть тоді, коли вона вимірюється в інших, не лінійних, одиницях вимірювання, наприклад в тимчасових одиницях.
Можна представити орграф G у вигляді карти маршрутів рейсових польотів з одного міста в іншій, де кожна вершина відповідає місту, а дуга v → w — рейсовому маршруту з міста v в місто w. Мітка дуги v → w — це час польоту з міста v в місто w. В цьому випадку розв’язок задачі знаходження найкоротшого шляху з одним джерелом для орієнтованого графа трактується як мінімальний час перельотів між різними містами.
Для вирішення поставленого завдання використовуватимемо "жадібний" алгоритм, який часто називають алгоритмом Дейкстри (Dijkstra). Алгоритм будує множину S вершин, для яких найкоротші шляхи від джерела вже відомі. На кожному кроці до множини S додається та з вершин, відстань до якої від джерела менше, ніж для інших вершин, що залишилися. Якщо вартості всіх дуг додатні, то можна бути упевненим, що найкоротший шлях від джерела до конкретної вершини проходить тільки через вершини множини S. Назвемо такий шлях особливим. На кожному кроці алгоритму використовується також масив D, в який записуються довжини найкоротших особливих шляхів для кожної вершини. Коли множина S міститиме всі вершини орграфа, тобто для всіх вершин будуть знайдені "особливі" шляхи, тоді масив D міститиме довжини найкоротших шляхів від джерела до кожної вершини.
Алгоритм Дейкстри представлений в тексті програми 6.3. Тут передбачається, що в орграфі G вершини пойменовані цілими числами, тобто множина вершин V = {1, 2, .... n}, причому вершина 1 є джерелом. Масив C — це двовимірний масив вартостей, де елемент C[i, j] рівний вартості дуги і → j. Якщо дуги і →j не існує, то C[i,j] стає рівним ∞, тобто більшим будь-якої фактичної вартості дуг. На кожному кроці D[i] містить довжину поточного найкоротшого особливого шляху до вершини і.
Текст програми 6.3. Алгоритм Дейкстри
procedure  Dijkstra;
begin
(1)    S:=   (1);
(2)    for  i:=  2  to  n do
(3)    D[i]:=   C[l, i]; { ініціалізація D  }
(4)    for i:=l   to n-1 do begin
(5)    вибір з множини  V\S такої вершини w
що значення D[w] буде  мінімальним;
(6)    додати   w до множини S;
(7)    for кожна вершина  v з множини   V\S do
(8)    D[v] ; =  min(D[v),   D[w]   +   C[w,   v] ]
еnd
end;   {   Dijkstra  }
Приклад 6.6. Застосуємо алгоритм Дейкстри для орієнтованого графа, показаного на мал. 6.6. Спочатку S = {1}, D[2] = 10, D[3] = ∞, D[4] = 30 і D[5] = 100. На першому кроці циклу (рядки (4) - (8) тексту програми 6.3) w = 2, тобто вершина 2 має мінімальне значення в масиві D. Потім обчислюємо D[3] = min(∞, 10 + 50)= 60. D[4] і D[5] не змінюються, оскільки не існує дуг, що виходять із вершини 2 і закінчуються у вершинах 4 і 5. Послідовність значень елементів масиву D після кожної ітерації циклу показані в табл. 6.1.
Нескладно внести зміни в алгоритм так, щоб можна було визначити найкоротший шлях (тобто послідовність вершин) для будь-якої вершини. Для цього треба ввести ще один масив Р вершин, де P[v] містить вершину, знаходиться безпосередньо перед вершиною v в найкоротшому шляху. Спочатку припустимо P[v] = 1 для всіх v ≠ 1. У тексті програми 6.3 після рядка (3) треба записати умовний оператора з умовою D[w] + C[w, v] < D[v], при виконанні якого елементу P[v] привласнюється значення w. Після виконання алгоритму найкоротший шлях до кожної вершини можна знайти за допомогою зворотного проходження по попередніх вершинах масиву Р.


Мал. 6.6. Орграф із поміченими дугами

Таблиця 6.1 Обчислення за алгоритмом Дейкстри для орграфа з мал. 6.6

Ітерація    S    ω    D[2]    D[3]    D[4]    D[5]
Початок    {1}    –    10    ∞    30    100
1    {1,2}    2    10    60    30    100
2    {1,2,4}    4    10    50    30    90
3    {1,2,4,3}    3    10    50    30    60
4    {1,2,4,3,5}    5    10    50    30    60


Приклад 6.7. Для орграфа з прикладу 6.6 масив Р має наступні значення: Р[2] = 1, Р[3] = 4, P[4] = 1, Р[5] = 3. Для визначення найкоротшого шляху, наприклад від вершини 1 до вершини 5, треба відстежити в зворотному порядку попередні вершини, починаючи з вершини 5. Виходячи із значень масиву Р, визначаємо, що вершині 5 передує вершина 3, вершині 3 — вершина 4, а їй, у свою чергу, — вершина 1. Таким чином, найкоротший шлях з вершини 1 у вершину 5 складає наступна послідовність вершин: 1, 4, 3, 5.
Обгрунтування алгоритму Дейкстри
Алгоритм Дейкстри — приклад алгоритму, де "жадібність" окуповується в тому сенсі, що якщо щось "добре" локально, то воно буде "'добре" і глобально. В даному випадку щось  локально "добре" — це обчислена відстань від джерела до вершини w, яка поки не входить в множину S, але має найкоротший особливий шлях. (Нагадаємо, що особливим ми назвали шлях, який проходить тільки через вершини множини S.) Щоб зрозуміти, чому не може бути іншого найкоротшого, але не особливого, шляху, розглянемо мал. 6.7. Тут показано гіпотетичний найкоротший шлях до вершини w, який спочатку проходить до вершини х через вершини множини S, потім після вершини х шлях, можливо, кілька разів входить до множини S і виходить з неї, поки не досягне вершини w.
Але якщо цей шлях коротше за найкоротший особливий шлях до вершини w, то і початковий сегмент шляху від джерела до вершини х (який теж є особливим шляхом) також коротше, ніж особливий шлях до w. Але у такому разі в рядку (5) тексту програми 6.3 при виборі вершини w ми повинні були вибрати не цю вершину, а вершину х, оскільки D[х] менше за D[w]. Таким чином, ми дійшли суперечності, отже, не може бути іншого найкоротшого шляху до вершини w, окрім особливого. (Відзначимо тут визначальну роль того факту, що всі вартості дуг невідємні, без цієї властивості поміченого орграфа алгоритм Дейкстри не працюватиме правильно.)

Мал.6.7. Гіпотетичний найкоротший шлях до вершини ω
Для завершення обгрунтування алгоритму Дейкстри треба ще довести, що D[v] дійсно показує найкоротшу відстань до вершини v. Розглянемо додавання нової вершини w до множини S (рядок (6) тексту програми 6.3), після чого відбувається перерахунок елементів масиву D в рядках (7), (8) цього тексту програми; при цьому може вийти коротший особливий шлях до деякої вершини і, що проходить через вершину v. Якщо частина цього шляху до вершини w проходить через вершини попередньої множини S і потім безпосередньо до вершини v, то вартість цього шляху, D[w]+ C[w, v], в рядку (8) тексті програми 6.3 порівнюється з D[v] і, якщо новий шлях коротший, змінюється значення D[v].
Існує ще одна гіпотетична можливість найкоротшого особливого шляху до вершини v, яка показана на мал. 6.8. У цьому випадку шлях спочатку йде до вершини w, потім повертається до вершини х, що належить попередній множині S, потім йде до вершини v. Але реально такого найкоротшого шляху не може бути. Оскільки вершина х міститься у множині S раніше вершини w, то всі найкоротші шляхи від джерела до вершини х проходять виключно через вершини попередньої множини S. Тому показаний на мал. 6.8 шлях до вершини х, що проходить через вершину w, не коротше, ніж шлях до вершини х, що проходить через вершини множини S. В результаті і весь шлях до вершини v, що проходить через вершини х і w, не коротше, ніж шлях від джерела до вершини х, що проходить через вершини множини S, і далі безпосередньо до вершини v. Таким чином, доведено, що оператор в рядку (8) тексту програми 6.3 дійсно обчислює довжину найкоротшого шляху.



Мал.6.8. Реально неможливий найкоротший особливий шлях

6.4. Знаходження найкоротших шляхів між парами вершин
Припустимо, що ми маємо помічений орграф, який містить час польоту по маршрутах, що зв'язують певні міста, і ми хочемо побудувати таблицю, де б вказувався мінімальний час перельоту з одного (довільного) міста в будь-яке інше. В цьому випадку ми маємо справу із загальним завданням знаходження найкоротших шляхів, тобто знаходження найкоротших шляхів між всіма парами вершин орграфа. Строгіше формулювання цього завдання наступне: є орієнтований граф G = (V, Е), кожній дузі v→w цього графа відповідає невід’ємна вартість C[v, w]. Загальне завдання знаходження найкоротших шляхів полягає в знаходженні для кожної впорядкованої пари вершин (v, w) деякого шляху від вершини v у вершину w, довжина якого є найменшою серед довжин всіх можливих шляхів від v до w.
Можна вирішити цю задачу, послідовно застосовуючи алгоритм Дейкстри для кожної вершини, що оголошується як джерело. Але існує прямий спосіб розв’язання даної задачі, що використовує алгоритм Флойда (R. W. Floyd). Для визначеності припустимо, що вершини графа послідовно пронумеровані від 1 до п, Алгоритм Флойда використовує матрицю А розміру п х п, в якій обчислюються довжини найкоротших шляхів. Спочатку A[i, j]= C[i, j] для всіх і ≠ j. Якщо дуги і →j немає, то С[i, j] = ∞. Кожен діагональний елемент матриці А рівний 0.
Над матрицею А виконується п ітерацій. Після k-ї ітерації A[i, j] містить значення найменшої довжини шляхів з вершини і у вершину j, які не проходять через вершини з номером, більшим за k. Іншими словами, між кінцевими вершинами шляху і і j можуть знаходитися тільки вершини, номери яких менше або рівні k.
На k-й ітерації для обчислення матриці А застосовується наступна формула:
Аk[і,j] = min(Ak-1[i,j],Ak-1 [i,k] + Ak-1 [k, j]).
Нижній індекс k позначає значення матриці А після k-ї ітерації, але це не означає, що існує п різних матриць, цей індекс використовується для скорочення запису. Графічна інтерпретація цієї формули показана на мал. 6.9.


Мал.6.9. Включення вершини k у шлях від вершини і до вершини j


Мал.6.10. Помічений орієнтований граф

Для обчислення Ak[i,j] проводиться порівняння величини Аk [і, j] (тобто вартість шляху від вершини і до вершини j без участі вершини k або іншої вершини з більшим номером) з величиною Ak-1 [i, k] + Ak-1[k, j[ (вартість шляху від вершини і до вершини k плюс вартість шляху від вершини k до вершини j). Якщо шлях через вершину k дешевше, ніж Ak-1[і, j], то величина Аk [і, j] змінюється.

Приклад 6.8. На мал. 6.10 показаний помічений орграф, а на мал. 6.11 — значення матриці А після трьох ітерацій.

Мал.6.11. Послідовні значення матриці А

Рівності Аk [і, k] = Аk-1 [і, k] і Аk [k, j] = Аk-1 [k, j] означають, що на k-й ітерації елементи матриці А, що стоять в k-му рядку і k-му стовпці, не змінюються. Більш того, всі обчислення можна виконати із застосуванням тільки однієї копії матриці А. Процедура, що реалізує алгоритм Флойда, представлена в наступному тексті програми.
Текст програми 6.4. Реалізація алгоритму Флойда       
procedure Floyd   ( var A: array[1..n,  1..n]   of real;
C: array[l..n, l..n] of real);
var
i,   j,   k:   integer;
begin
for і:= 1 to n do
for j: =1 to n do
A[i, j]:=  C[i,j];
for i: =1 to n do
A[i, i]:= 0;
for k:= 1 to n  do
for і:= 1 to n  do
for j:= 1 to n  do
if A[i, k]  +  А[k, j]   <  A[i, j]   then
A[i, j]:= A[i, k]  +  А[k, j] 
end; { Floyd }
Час виконання цієї програми, очевидно, має порядок 0(n3), оскільки в ній практично немає нічого, окрім вкладених один в одного трьох циклів. Доведення "правильності" роботи цього алгоритму також очевидне і виконується за допомогою математичної індукції по k, показуючи, що на k-й ітерації вершина k  включається в шлях тільки тоді, коли новий шлях коротший за старий.
Порівняння алгоритмів Флойда і Дейкстри
Оскільки версія алгоритму Дейкстри з використанням матриці суміжності знаходить найкоротші шляхи від однієї вершини за час порядку 0(n2), то в цьому випадку застосування алгоритму Дейкстри для знаходження всіх найкоротших шляхів займе часу близько 0(n3), тобто одержимо такий же часовий порядок, як і в алгоритмі Флойда. Константи пропорційності в порядках часу виконання для обох алгоритмів залежать від вживаних компілятора і обчислювальної машини, а також від особливостей реалізації алгоритмів. Обчислювальний експеримент і вимірювання часу виконання — найпростіший шлях підібрати кращий алгоритм для конкретного випадку.
Якщо е, кількість дуг в орграфе, значно менше, ніж n2, тоді, не дивлячись на відносно малу константу у виразі порядку 0(n3) для алгоритму Флойда, ми рекомендуємо застосовувати версію алгоритму Дейкстри із списками суміжності. В цьому випадку час розв’язування загальної задачі знаходження найкоротших шляхів має порядок 0(пе log), що значно краще за алгоритм Флойда, принаймні для великих розріджених графів.
Вивід на друк найкоротших шляхів
У багатьох ситуаціях потрібно роздрукувати найдешевший шлях від однієї вершини до іншої. Щоб відновити при необхідності найкоротші шляхи, можна в алгоритмі Флойда ввести ще одну матрицю Р, в якій елемент P[i, j] містить вершину k, одержану при знаходженні найменшого значення A[i, j]. Якщо P[i, j]= 0, то найкоротший шлях з вершини і у вершину j складається з однієї дуги і→j . Модифікована версія алгоритму Флойда, що дозволяє відновлювати найкоротші шляхи, представлена у тексті програми 6.5.
Текст програми 6.5. Програма знаходження найкоротших шляхів
procedure  Floyd   ( var A:   array[l..n, l..n]   of real;
C: array [1..n, 1..n] of  real;   P: array [1..n, l..n] of integer);
var
i,  j,  k : integer;
begin
for  і:= 1   to  n  do
for  j:= 1  to n do  begin
A[i, j]:= C[i, j;
P[i,  j]:= 0
end;
for   і:= 1  to  n  do
A[i, j] := 0;
for  k:= 1  to  n  do
for  і:= 1 to n do
for  j:= 1  to  n do
if A[i,k]  + А [k,  j]  < A[i,  j]   then begin
A[i,j]:=A[i,k]  + А [k,  j];
P[i,j]:=k
end
end;    {   Floyd  }
Для виведення на друк послідовності вершин, що становлять найкоротший шлях від вершини і до вершини j, викликається процедура path(i, j), опис якої приведений у тексті програми 6.6.
Текст програми 6.6. Процедура друку найкоротшого шляху
procedure path ( і, j: integer );
var
k:  integer;
begin
k: =  P[i, j];
if   k: =  0   then
return;
path(i, k);
writeln(k);
path (k, j)
end;   { path }

Приклад 6.9. На мал. 6.12 показана результуюча матриця Р для орграфа з мал. 6.10.

Мал.6.12. Матриця Р для орграфа із мал.6.10
Транзитивне замикання
У багатьох задачах інтерес становить лише сам факт існування шляху, завдовжки не менше одиниці, від вершини і до вершини j. Алгоритм Флойда можна пристосувати для вирішення таких задач. Але одержаний в результаті алгоритм ще до Флойда розробив Уоршелл (S. Warshall), тому ми називатимемо його алгоритмом Уоршелла.
Припустимо, що матриця вартостей С співпадає з матрицею суміжності для даного орграфа G, тобто C[i, j] =1 тільки в тому випадку, якщо є дуга і→j, і C[i, j] = 0, якщо такої дуги не існує. Ми хочемо побудувати матрицю А таку, що A[i, j]= 1 тоді і тільки тоді, коли існує шлях від вершини і до вершини j завдовжки не менше 1 і A[i, j] = 0 — протилежному випадку. Таку матрицю А часто називають транзитивним замиканням матриці суміжності.
Приклад 6.10. На мал. 6.13 показано транзитивне замикання матриці суміжності орграфа з мал. 6.10.

Мал.6.13. Транзитивне замикання  матриці суміжності
Транзитивне  замикання  можна  обчислити  за допомогою  процедури,  подібної Floyd, застосовуючи до булевої матриці А на k-му кроці наступну формулу:
Аk[і, j] = Ak-1[i, j] or (Ak-1 [i, k] and Ak-1 [k, j]).
Ця формула встановлює, що шлях від вершини і до вершини j, який проходить через вершини з номерами, що не перевищують k, існує тільки в наступних випадках.
1.    Якщо вже існує шлях від вершини і до j, який проходить через вершини з номерами, що не перевищують k - 1.
2.    Існує шлях від вершини i до k, що проходить через вершини з номерами, які не перевищують k - 1, і шлях від вершини k до вершини j, який також проходить через вершини з номерами, що не перевищують k - 1.
Тут, як і в алгоритмі Флойда, Аk [і, k] = Аk-1 [і, k] і Аk [k, j] = Аk-1 [k, j], і обчислення можна виконувати в одній копії матриці А. Реалізація алгоритму Warshall обчислення транзитивного замикання показана в тексті програми 6.7.
Текст програми  6.7. Програма Warshall для обчислення транзитивного замикання
procedure Warshall  ( var A:  array [l..n, l..n]  of  boolean;
C:   array [l..n,   1.. n] of  boolean  );
var
i,   j,   k:   integer;
begin
for і: = 1 to n do.
for  j:= 1  to  n do
A[i,  j]:= C[i, j];   
for  k:= 1  to  n  do
for  i:= 1 to n do
for  j:=1  to  n do
if A[і, j]  =  false  then
A[i, j]:= A[i, k]  and  A[k,  j]
end;    {   Warshall   }
Знаходження центру орієнтованого графа
Припустимо, що необхідно знайти центральну вершину в орграфі. Це завдання вирішується також за допомогою алгоритму Флойда. Але спочатку треба уточнити термін центральна вершина. Нехай v — довільна вершина орграфа G = (V, Е). Ексцентриситет (максимальне віддалення) вершини v визначається як
{ мінімальна довжина шляху від вершини w до вершини v)
Центром орграфа G називається вершина з мінімальним ексцентриситетом. Іншими словами, центром орграфа є вершина, для якої максимальна відстань (довжина шляху) до інших вершин є найменшою.
Приклад 6.11. Розглянемо помічений орграф, показаний на мал. 6.14.
У цьому графі вершини мають наступні ексцентриситети.
Вершина    Ексцентриситет
а    оо
b    6
c    8
d    5
е    7
З цієї таблиці видно, що центром даного орграфа є вершина d.
Знайти центр орграфа порівняно просто. Нехай С — матриця вартостей для орграфа G.
1.    Спочатку застосуємо процедуру Floyd (текст програми 6.4) до матриці С для обчислення матриці А, що містить всі найкоротші шляхи орграфа G.
2.    Знаходимо максимальне значення в кожному стовпці і матриці А. Це значення рівне ексцентриситету вершини і.
3.    Знаходимо вершину з мінімальним ексцентриситетом. Вона і буде центром графа G

Мал.6.14. Помічений орграф

Час виконання цього процесу визначається першим кроком, для якого час має порядок 0(п3). Другий крок займає близько 0(п2) часу, а третій — 0(п).
Приклад 6.12. Матриця всіх найкоротших шляхів для орграфа з мал. 6.14 представлена на мал. 6.15. Максимальні значення в кожному стовпці приведені під матрицею.

Мал.6.15. Матриця найкоротших шляхів
6.5. Обхід орієнтованих графів
При розв’язуванні багатьох задач, що стосуються орієнтованих графів, необхідний ефективний метод систематичного обходу вершин і дуг орграфов. Таким методом є так званий пошук в глибину — узагальнення методу обходу дерева в прямому порядку. Метод пошуку в глибину складає основу багатьох інших ефективних алгоритмів роботи з графами. У останніх двох підпунктах цього розділу представлені різні алгоритми, засновані на методі пошуку в глибину.
Припустимо, що є орієнтований граф G, в якому спочатку всі вершини помічені міткою unvisited (не відвідувалася). Пошук в глибину починається з вибору початкової вершини v графа G, для цієї вершини мітка unvisited змінюється на мітку visited (відвідувалася). Потім для кожної вершини, суміжної з вершиною v і яка не відвідувалася раніше, рекурсивно застосовується пошук в глибину. Коли всі вершини, які можна досягти з вершини v, будуть "відвіданими", пошук закінчується. Якщо деякі вершини залишилися не відвіданими, то вибирається одна з них і пошук повторюється. Цей процес продовжується до тих пір, поки обходом не будуть охоплені всі вершини орграфа G.
Цей метод обходу вершин орграфа називається пошуком в глибину, оскільки пошук не відвіданих вершин йде в напрямі вперед (углиб) до тих пір, поки це можливо. Наприклад, нехай х — остання відвідана вершина. Для продовження процесу вибирається яка-небудь нерозглянута дуга х → у, що виходить з вершини х. Якщо вершина у вже відвідувалася, то шукається інша вершина, суміжна з вершиною х. Якщо вершина у раніше не відвідувалася, то вона позначається міткою visited і пошук починається наново від вершини у. Пройшовши всі шляхи, які починаються у вершині у, повертаємося у вершину х, тобто в ту вершину, з якої вперше була досягнута вершина у. Потім продовжується вибір нерозглянутих дуг, що виходять із вершини х, і так до тих пір, поки не будуть вичерпані всі ці дуги.
Для представлення вершин, суміжних з вершиною v, можна використовувати список суміжності L[v], а для визначення вершин, які раніше відвідувалися, — масив mark (мітка), елементи якого прийматимуть тільки два значення: visited і unvisited. Приклад рекурсивної процедури dfs (від depth-first search — пошук в глибину), що реалізовує метод пошуку в глибину, представлений в тексті програми 6.8.
Щоб застосувати цю процедуру до графа, що складається з п вершин, треба спочатку присвоїти всім елементам масиву mark значення unvisited, потім почати пошук в глибину для кожної вершини, поміченої як unvisited. Це можна реалізувати за допомогою наступної послідовності операторів:
for v:= 1 to  n do
mark[v] :=   unvisited;
for v:= 1 to  n  do
if mark[v]   =  unvisited  then
dfs(v)
Відзначимо, що тексті програми 6.8 є тільки ескізом процедури, який ще слід деталізувати. Відзначимо також, що ця процедура змінює лише значення масиву mark.
Текст програми 6.8. Процедура пошуку в глибину   
procedure dfs ( v: вершина);
var
w:  вершина;
begin
(1)    mark[v]:=  visited;
(2)    for кожна вершина w  із списку L[v]  do
(3)    if mark[w]  =  unvisited  then
(4)        dfs(w)
end; { dfs  }
Аналіз процедури пошуку в глибину
Всі виклики процедури dfs для повного обходу графа з п вершинами і е дугами,    якщо с ≥ n, вимагають загального часу виконання близько 0(e). Щоб показати це, відмітимо, що немає вершини, для якої процедура dfs викликалася б більше одного разу, оскільки дана вершина позначається як visited в рядку (1) (текст програми  6.8) ще до наступного виклику процедури dfs і ніколи не викликається для вершин, помічених цією міткою. Тому загальний час виконання рядків (2) і (3) для перегляду всіх списків суміжності пропорційний сумі довжин цих списків, тобто має порядок 0(e). Таким чином, припускаючи, що е ≥ п, загальний час обходу по всіх вершинах орграфа має порядок 0(e), необхідний для " перегляду " всіх дуг графа.
Приклад 6.13. Нехай процедура dfs застосовується до орієнтованого графа, представленого на мал. 6.16, починаючи з вершини А. Алгоритм позначає цю вершину як visited і вибирає вершину В із списку суміжності вершини А. Оскільки вершина В помічена як unvisited, обхід графа продовжується викликом процедури dfs(B). Тепер процедура позначає вершину В як visited і вибирає першу вершину із списку суміжності вершини В. Залежно від порядку представлення вершин в списку суміжності, наступною розглядуваною вершиною може бути або вершина С, або вершина D.
Припустимо, що в списку суміжності вершина С передує вершині D. Тоді здійснюється виклик dfs(C). У списку суміжності вершини С присутня тільки вершина А, але вона вже відвідувалася раніше. Оскільки всі вершини в списку суміжності вершини С вичерпані, то пошук повертається у вершину В, звідки процес пошуку продовжується викликом процедури dfs(D). Вершини А і С із списку суміжності вершини D вже відвідувалися раніше, тому пошук повертається спочатку у вершину В, а потім у вершину А.
На цьому первинний виклик dfs(A) завершений. Але орграф має вершини, які ще не відвідувалися: Е, F і G. Для продовження обходу вершин графа виконується виклик dfs(E).

Мал.6.15. Орієнтований граф

Глибинний остовний ліс
В процесі обходу орієнтованого графа методом пошуку в глибину тільки певні дуги ведуть до вершин, що раніше не відвідувалися. Дуги, що ведуть до нових вершин, називаються дугами дерева і формують для даного графа остовний ліс, побудований методом пошуку в глибину, або, скорочено, глибинний остовний ліс. На мал. 6.17 показаний глибинний остовний ліс для графа з мал. 6.16. Тут суцільними лініями позначені дуги дерева. Відзначимо, що дуги дерева формують ліс, тобто сукупність дерев, оскільки методом пошуку в глибину до будь-якої вершини, що раніше не відвідувалася, можна прийти тільки по одній дузі, а не по двох різних дугах.
Окрім дуг дерева існують ще три типи дуг, що визначаються в процесі обходу орграфа методом пошуку в глибину. Це зворотні, прямі і поперечні дуги. Зворотні дуги (дуга С→А на мал. 6.17) — такі дуги, які в остовному лісі ведуть від нащадків до предків. Відзначимо, що дуга, яка виходить з вершини і заходить у цю ж вершину також є зворотною дугою. Прямими дугами називаються дуги, що йдуть від предків до дійсних нащадків, але які не є дугами дерева. На мал. 6.17 прямі дуги відсутні.
Дуги, такі як D→ СіG→D на мал. 6.17, що сполучають вершини, які не є ні предками, ні нащадками один одного, називаються поперечними дугами. Якщо при побудові остовного дерева сини однієї вершини розташовуються зліва направо у порядку їх відвідин і якщо нові дерева додаються в ліс також зліва направо, то всі поперечні дуги йдуть справа наліво, що видно на мал. 6.17. Таке взаємне розташування вершин і дерев вибране не випадково, оскільки це допомагає формувати остівний ліс.

Мал.6.17. Глибинний остовний ліс для орграфа із  мал. 6.16
Як можна розрізнити ці чотири типи дуг? Легко визначити дуги дерева, оскільки вони виявляються в процесі обходу графа як дуги, що ведуть до тих вершин, які раніше не відвідувалися. Припустимо, що в процесі обходу орграфа його вершини нумеруються у порядку їх відвідин. Для цього в тексті програми 6.8 після рядка (1) потрібно додати наступні рядки:
Dfnumber[v]:=  count;
count:=  count + 1;
Назвемо таку нумерацію глибинною нумерацією орієнтованого графа. Відзначимо, що ця нумерація узагальнює нумерацію, одержану при прямому обході дерева (див. пункт 3.1).
Всім нащадкам вершини v присвоюються глибинні номери, не менші, ніж номер, присвоєний вершині v. Фактично вершина w буде нащадком вершини v тоді і тільки тоді, коли виконуються нерівності dfnumber{v) ≤ dfnumber(w) ≤ dfnumber{v) + кількість нащадків вершини v. Очевидно, що прямі дуги йдуть від вершин з нижчими номерами до вершин з вищими номерами, а зворотні дуги — від вершин з вищими номерами до вершин з нижчими номерами.
Всі поперечні дуги також йдуть від вершин з вищими номерами до вершин з нижчими номерами. Щоб показати це, припустимо, що є дуга x→у і виконується нерівність dfnumber(x) ≤ dfnumber(y). Звідси слідує, що вершина х пройдена (відвідана) раніше вершини у. Кожна вершина, пройдена в проміжок часу від виклику dfs(x) і до завершення dfs(y), стає нащадком вершини х в глибинному остівному лісі. Якщо при розгляді дуги   х→ у вершина у ще не відвідувалася, то ця дуга стає дугою дерева. У протилежному випадку дуга х→ у буде прямою дугою. Таким чином, якщо для дуги х→ у виконується нерівність dfnumber(x) ≤ dfnumber(y), то вона не може бути поперечною дугою.
У наступних пунктах цього розділу буде розглянено застосування методу пошуку в глибину для вирішення різних задач на графах.

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


Мал. 6.18. Три орієнтованих графа
Ациклічні орграфи зручні для представлення синтаксичних структур арифметичних виразів, що мають підвирази, що повторюються. Наприклад, на мал. 6.19 показаний ациклічний орграф для виразу
((а + b)*c + ((а + b) + е) * (е + f)) * ((а + b)*с).
Підвирази а + b і (а + b)*с зустрічаються у виразі кілька разів, тому вони представлені вершинами, в які входять декілька дуг.


Мал.  6.19. Орієнтований ациклічний  граф для арифметичного виразу

Ациклічні орграфи також корисні для представлення відносин часткових порядків. Відношенням часткового порядку R, визначеним на множині S, називається бінарне відношення, для якого виконуються наступні умови.
1.    Для жодного елементу а з множини S не виконується aR a (властивість антирефлексивності) .
2.    Для будь-яких а, b, c із S, таких, що aR b і bR c, виконується aR c (властивість транзитивності).
Двома природними прикладами відносин часткового порядку можуть слугувати відношення "менше ніж" (позначається знаком "<"), задане на множині цілих чисел, і відношення строгого включення ( ) множин.
Приклад 6.14. Нехай S = {1, 2, 3} і P(S) — множина всіх підмножин множини S, тобто P(S) = { , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, (1, 2, 3}}. Відношення строгого включення ( ) є відношенням часткового порядку на множині P(S). Очевидно, що включення  А  А не виконується для будь-якої множини А з Р (антирефлексивність), і при виконанні А  В і В  С виконується А  С (транзитивність).
Ациклічні орграфи можна використовувати для графічного зображення відношення часткового порядку між будь-якими об'єктами. Спершу можна представити відношення R як однойменну множину пар (дуг) таких, що пара (а, b) належить цій множині тільки тоді, коли виконується aRb. Якщо відношення R визначене на множині елементів S, то орієнтований граф G = (S. R) буде ациклічним. І навпаки, нехай G = (S, R) є ациклічним орграфом, а R+ — відношення, визначене наступним чином: aR+b виконується тоді і тільки тоді, коли існує шлях (завдовжки не менше 1) від вершини а до вершини b. Тоді   R+ — відношення часткового порядку на S. (Відношення R+ є транзитивним замиканням відношення R.)
Приклад 6.15. На мал. 6.20 показаний ациклічний орграф (P(S), R),  де S = {1, 2, 3}. Тут R+ — відношення строгого включення на множині P(S).

Мал. 6.20. Ациклічний  орграф, що репрезентує відношення строгого включення

Перевірка ациклічності орграфа
Припустимо, що є орієнтований граф G = (V, Е) і ми хочемо визначити, чи є він ациклічним, тобто чи має він цикли. Щоб відповісти на це питання, можна використовувати метод пошуку в глибину. Якщо при обході орграфа G методом пошуку в глибину зустрінеться зворотна дуга, то зрозуміло, що граф має цикл. З іншого боку, якщо в орграфе є цикл, тоді зворотна дуга обов'язково зустрінеться при обході цього орграфа методом пошуку в глибину.
Щоб довести це, припустимо, що орграф G має цикл. Нехай при обході даного орграфа методом пошуку в глибину вершина v має найменше глибинне число серед всіх вершин, що становлять цикл. Розглянемо дугу u→ v, що належить цьому циклу. Оскільки вершина и входить в цикл, то вона повинна бути нащадком вершини v в глибинному остовном лісі. Тому дуга u→ v не може бути поперечною дугою. Оскільки глибинний номер вершини и більше глибинного номера вершини v, то звідси слідує, що ця дуга не може бути дугою дерева і прямою дугою. Отже, дуга u→ v є зворотною дугою, як показано на мал. 6.21.

Топологічне сортування
Великі проекти часто розбиваються на сукупність менших задач, які виконуються в певному порядку і забезпечують повне завершення цілого проекту. Наприклад, план учбового закладу вимагає певної послідовності в читанні учбових курсів. Ациклічні орграфи можуть служити природною моделлю для таких ситуацій. Наприклад, ми створимо дугу від учбового курсу С до учбового курсу D тоді, коли читання курсу С передує читанню курсу D.
Приклад 6.16. На мал. 6.22 показаний ациклічний орграф, що показує структуру слідувань п'яти учбових курсів. Читання учбового курсу СЗ, наприклад, вимагає попереднього читання курсів С1 і С2.
Мал. 6.21. Кожний цикл містить зворотну дугу


Мал. 6.22. Ациклічний  орграф, що показує структуру попередніх слідувань

Топологічне сортування — це процес лінійного впорядковування вершин ациклічного орграфа таким чином, що якщо існує дуга від вершини і до вершини j, то у впорядкованому списку вершин орграфа вершина і передує вершині j. Наприклад, для орграфа з мал. 6.22 вершини після топологічного сортування розташуються в наступному порядку: С1, С2, СЗ, С4, С5.
Топологічне сортування легко виконати за допомогою модифікованої процедури тексту програми 6.8,  якщо в ній після рядка (4) додати оператор виведення на друк:
procedure topsort  ( v: вершина);
{друк в зворотному топологічному порядку вершин
досяжних з вершини v}
var
w: вершина;
begin
mark[v]:= visited;
for кожна вершина w із списку L[v]   do
if mark[w] =  unvisited then
topsort(w);
writeln(v)
end;    {   topsort  }
Коли процедура topsort закінчує пошук всіх вершин, що є нащадками вершини v, друкується сама вершина v. Звідси слідує, що процедура topsort роздруковує всі вершини в зворотному топологічному порядку.
Ця процедура працює, оскільки в ациклічному орграфе немає зворотних дуг. Розглянемо, що відбувається, коли пошук в глибину досягає кінцевої вершини х. З будь-якої вершини можуть виходити тільки дуги дерева, прямі і поперечні дуги. Але всі ці дуги напрямлені у вершини, що вже пройдені (відвідувалися до досягнення вершини х), і тому передують вершині х.
6.7. Сильна зв'язність
Сильно зв'язною компонентою орієнтованого графа називається максимальна множина вершин, в якій існують шляхи з будь-якої вершини в будь-яку іншу вершину. Метод пошуку в глибину можна ефективно використовувати для знаходження сильно зв'язних компонентів орієнтованого графа.
Дамо точне формулювання поняття сильної зв'язності. Нехай G = (V, Е) – орієнтований граф. Множина вершин V розбивається на класи еквівалентності Vі, 1 ≤ і ≤ r, так, що вершини v і w будуть еквівалентні тоді і тільки тоді, коли існують шляхи з вершини v у вершину w і з вершини w у вершину v. Нехай Еі, 1 ≤ і ≤ r, — множина дуг, які починаються і закінчуються в множині вершин Vі. Тоді графи Gі = (Vi , Еi) називаються сильно зв'язними компонентами графа G. Орієнтований граф, що складається тільки з однієї сильно зв'язної компоненти, називається сильно зв'язним.
Приклад 6.17. На мал. 6.23 представлений орієнтований граф з двома сильно зв'язними компонентами, які показані на мал. 6.24.
Відзначимо, що кожна вершина орієнтованого графа G належить деякій сильно зв'язаній компоненті, але деякі дуги можуть не належати жодній сильно зв'язаній компоненті. Такі дуги йдуть від вершини однієї компоненти до вершини, що належить іншій компоненті. Можна представити зв'язки між компонентами шляхом створення редукованого (приведеного) графа для графа G. Вершинами приведеного графа є сильно зв'язні компоненти графа G. У приведеному графі дуга від вершини С до вершини D існує тільки тоді, коли в графі G є дуга від якої-небудь вершини, що належить компоненті С, до деякої вершини, що належить компоненті D. Редукований граф завжди є ациклічним орграфом, оскільки якби існував цикл, то всі компоненти, що входять в цей цикл, насправді були б однією зв'язною компонентою. На мал. 6.25 показаний редукований граф для графа з мал. 6.23.



Тепер розглянемо алгоритм знаходження сильно зв'язаних компонент для заданого орієнтованого графа G.
1.    Спочатку виконується пошук в глибину на графі G. Вершини нумеруються у порядку завершення рекурсивно викликаної процедури dfs, тобто присвоєння номерів вершинам відбувається після рядка (4) в тексті програми 6.8.
2.    Конструюється новий орієнтований граф Gr шляхом зміни на протилежний напряму всіх дуг графа G.
3.    Виконується пошук в глибину на графі Gr, починаючи з вершини із найбільшим номером, присвоєним на кроці 1. Якщо проведений пошук не охоплює всіх вершин, то починається новий пошук з вершини, що має найбільший номер серед вершин, що залишилися.
4.    Кожне дерево в одержаному остовном лісі є сильно зв'язною компонентою графа G.
Приклад 6.18. Застосуємо описаний алгоритм до орієнтованого графа, представленого на мал. 6.23. Проходження вершин графа почнемо з вершини а і потім перейдемо на вершину b. Присвоєні після завершення кроку 1 номера вершин показані на мал. 6.26. Одержаний шляхом звернення (зміни на протилежний напрям) дуг граф G, представлений на мал. 6.27.
Виконавши пошук в глибину на графі Gr, одержимо глибинний остовний ліс, показаний на мал. 6.28. Обхід остовного лісу ми починаємо з вершини а, що приймається як корінь дерева, оскільки вона має найвищий номер. З кореня а можна досягти тільки вершин cіb. Наступне дерево має лише корінь d, оскільки вершина d має найвищий номер серед тих, що залишилися (до того ж вона є єдиною вершиною, що залишилася). Кожне з цих дерев формує окрему сильно зв'язну компоненту початкового графа G.

Вище ми стверджували, що вершини строго зв'язної компоненти повністю відповідають вершинам дерева в остовном лісі, одержаному при застосуванні пошуку в глибину до графа Gr. Доведемо це.
Спочатку покажемо, що якщо вершини v і w належать одній зв'язній компоненті, то вони належать і одному остовному дереву. Якщо вершини v і w належать одній зв'язній компоненті, то в графі G існує шлях від вершини v до вершини w і шлях від вершини w до вершини v. Припустимо, що пошук в глибину на графі Gr, розпочався від деякого кореня х і досяг вершини v, або вершини w. Оскільки існують шляхи (у обидві сторони) між вершинами v і w, то обидві вони належать остовному дереву з коренем x.
Тепер припустимо, що вершини v і w належать одному і тому ж остовному дереву в глибинному остовном лісі графа G. Покажемо, що вони належать одній і тій же сильно зв'язній компоненті. Нехай х — корінь остовного дерева, якому належать вершини v і w. Оскільки вершина v є нащадком вершини х, то в графі Gr існує шлях від вершини х до вершини і, а в графі G — шлях від вершини v до вершини х.
Відповідно до проходження вершин графа Gr методом пошуку в глибину вершина v відвідується пізніше, ніж вершина х, тобто вершина х має вищий номер, ніж вершина v. Тому при обході графа G рекурсивний виклик процедури dfs для вершини v закінчується раніше, ніж виклик dfs для вершини х. Але якщо при обході графа G викликається процедура dfs для вершини v, то через наявність шляху від вершини v до вершини х процедура dfs для вершини х почнеться і закінчиться до закінчення процедури dfs(v), а, отже, вершина х одержить менший номер, ніж вершина v. Отримуємо суперечність.
Звідси робимо висновок, що при обході графа G вершина v відвідується при виконанні dfs(x) і тому вершина v є нащадком вершини х. Отже, в графі G існує шлях від вершини х до вершини v. Більш того, оскільки існує і шлях від вершини v до вершини х, то вершини х і v належать одній сильно зв'язній компоненті. Аналогічно доводиться, що вершини х і w належать одній сильно зв'язній компоненті. Звідси слідує, що і вершини v і w належать тій же сильно зв'язній компоненті, оскільки існує шлях від вершини v до вершини w через вершину х і шлях від вершини w до вершини v через вершину х.

Вправи
6.1.     Представте граф, зображений на мал. 6.29, за допомогою
а)    матриці суміжності, що містить вартості дуг;
б)    зв'язаних списків суміжності, що показують вартість дуг.

6.2.    Побудуйте математичну модель для задачі складання календарного плану робіт. Є множина завдань T1, T2, ... Тn, для виконання яких необхідний час t1, t2, … tn і множина відношень виду "завдання Ті треба виконати до початку виконання завдання Тj". Знайдіть мінімальний час, необхідне для виконання всіх завдань.
6.3.    Виконайте реалізацію операторів FIRST, NEXT і VERTEX для орграфів, представлених за допомогою:
а)    матриць суміжності;
б)    зв'язаних списків суміжності;
в)    списків суміжності, показаних на мал. 6.5.
6.4.    Для графа, показаного на мал. 6.29, використайте
а)    алгоритм Дейкстри для знаходження найкоротших шляхів від вершини а до
решти вершин;
б)    алгоритм Флойда для знаходження найкоротших шляхів між всіма парами
вершин.
6.5.    Напишіть повну програму алгоритму Дейкстри, використовуючи зв'язані списки суміжності і чергу з пріоритетами, реалізовану за допомогою частково впорядкованого дерева.
*6.6. Покажіть, що алгоритм Дейкстри працює неправильно, якщо вартості дуг можуть бути від’ємними.
**6.7. Покажіть, що алгоритм Флойда працює коректно, якщо деякі дуги мають від’ємну  вартість, але немає циклів, що складаються із дуг з від’ємними вартостями.
6.8. Вважаючи, що вершини графа з мал. 6.29 впорядковані як а, b, .... f, побудуйте глибинний остовний ліс. Вкажіть дуги дерева, прямі, зворотні і поперечні, а також підрахуйте глибинні номери вершин.
*6.9. Нехай є глибинний остовний ліс і здійснюється обхід його остовних дерев зліва направо в зворотному порядку. Покажіть, що в цьому випадку список вершин співпадатиме із списком вершин, одержаних за допомогою процедури dfs, що викликається при побудові остовного лісу.
6.10. Коренем ациклічного орграфа називається вершина r така, що існують шляхи, які виходять з цієї вершини і досягають всіх решта вершин орграфа. Напишіть програму, що визначає, чи має даний ациклічний орграф корінь.
*6.11. Нехай ациклічний орграф має е дуг. Зафіксуємо дві різні вершини s і t цього графа. Побудуйте алгоритм з часом виконання O(е) для знаходження максимальної множини вершин, що входять в шляхи від вершини s до вершини t.
6.12.    Побудуйте алгоритм перетворення в ациклічний орграф арифметичних виразів з операторами додавання і множення, використовуючи підвирази, що повторюються. Який час виконання цього алгоритму?
6.13.    Побудуйте алгоритм читання арифметичних виразів, представлених у вигляді ациклічного орграфа.
6.14.    Напишіть програму знаходження найдовшого шляху в ациклічному орграфі. Який час виконання цього алгоритму?
6.15.    Знайдіть сильно зв'язні компоненти графа, представленого на мал. 6.29.
*6.16. Доведіть, що редукований граф строго зв'язних компонент (див. розділ 6.7) обов'язково повинен бути ациклічним орграфом.
6.17.    Намалюйте перший остовний ліс, зворотний граф і другий остовний ліс в процесі визначення сильно зв'язних компонент орграфа, показаного на мал. 6.29.
6.18.    Реалізуйте алгоритм знаходження сильно зв'язних компонент, розглянутий в розділі 6.7.
*6.19. Покажіть, що алгоритм знаходження сильно зв'язних компонент вимагає часу близько 0(e) на орієнтованому графі, що має е дуг і п вершин, якщо п < е.
*6.20. Напишіть програму, на вході якої задається орграф і дві його вершини. Програма повинна роздруковувати всі прості шляхи, що ведуть від однієї вершини до іншої. Яка часова складність (час виконання) цієї програми?
*6.21. Транзитивна редукція орієнтованого графа G = (V, Е) визначається як довільний граф G' = (V, Е'), що має ту ж множину вершин, але з мінімально можливим числом дуг, транзитивне замикання якого співпадає з транзитивним замиканням графа G. Покажіть, що якщо граф G є ациклічним, то його транзитивна редукція єдина.
*6.22. Напишіть програму знаходження транзитивної редукції орграфа. Яка часова складність (час виконання) цієї програми?
*6.23. Орграф G' = (V, E') називається мінімальним еквівалентним орграфом для орграфа G = (V, Е), якщо Е' — найменша підмножина множини Е така, що транзитивні замикання обох орграфів G і G' співпадають. Покажіть, що якщо граф G є ациклічним, то для нього існує тільки один мінімальний еквівалентний орграф, а саме — його транзитивна редукція.
*6.24. Напишіть програму знаходження мінімального еквівалентного орграфа. Яка часова складність (час виконання) цієї програми?
*6.25. Напишіть програму знаходження найдовшого простого шляху від заданої вершини орграфа. Яка часова складність (час виконання) цієї програми?

Search:
????????...

приклади застосування струму в медицині

гобсек текст

"лунає дзвін бандури"

прометей популярнiсть у вiршах

За романом Гобсек неперевершений філософ

ендемічні захворювання виникають внаслідок

Реферат на тему рух по колу.Чому тіло буде скочуватись по краю?

Будь-яка праця стає творчістю, якщо ти вкладаєш в неї душу.

вірші про козаків

лабораторні роботи з фізики 9 кл



?????????? ????????? ????
   
Created by Yura Pagor, 2007-2010