Поняття орієнтованого графа
Орграфом D називається пара (V(D), A(D)), де V(D) - непусте кінцеве безліч елементів, званих вершинами, і A(D) - кінцеве сімейство впорядкованих пар елементів з V(D), званих дугами; V(D) і A(D) називаються відповідно безліччю вершин та сімейством дуг орграфа D. Так, на рис. 1 представлений орграф, дугами якого є (u, v), (v, v), (v, w), (v, w), (w, v), (w, u) та (z, w); порядок вершин на дузі вказано стрілкою.
Граф, отриманий з орграфа D «видаленням стрілок» (тобто заміною кожної дуги виду (v, w) на відповідне ребро), називається основою орграфа D (рис. 2).
Мал. 2. Заснування орграфа
Дві вершини v і w орграфа D називаютьсясуміжними, якщо в A(D) існує дуга виду (v, w) або (w, v); при цьому вершини v і w називаються інцидентними будь-якої такої дуги (а дуга - інцидентною відповідним вершин).
Два орграфи називаютьсяізоморфними, якщо існує ізоморфізм між їх основами, що зберігає порядок вершин на кожній дузі. Матрицею суміжності орграфа G безліччю вершин 1, ..., vn & gt; є матриця А = (aij), у якій aij дорівнює числу дуг виду (vi, vj) у сімействі A(D). Матриця, показана на рис.3 є матрицею суміжності для орграфа, зображеного на рис. 1. Простий орграф визначається очевидним чином.
Мал. 3 Матриця суміжності
Орієнтований маршрутв орграфі D являє собою кінцеву послідовність дуг виду (v0, vj, (vl, v2), vm). Можна записувати цю послідовність у вигляді v0 ->v1 ->. ->vm і говорити про орієнтований маршрут з v0 до vm. Аналогічним чином можна визначитиорієнтовані ланцюги, орієнтовані прості ланцюги таорієнтовані цикли, абоорцепи,прості орцепитаорцикли.
Зауважимо, що хочаорцепьне може містити цю дугу (v, w) більше одного разу, вона може містити одночасно (v, w) та (w, v); наприклад, на рис. 1 z ->w ->v ->w ->u єорцепью. Тепер ми можемо визначити зв'язність. Точніше, ми визначимо тут два найбільш природні і корисні типи зв'язності орграфів, які виникають відповідно до того, хочемо ми чи ні брати до уваги орієнтацію дуг.
Кажуть, що орграф Dзв'язаний(абослабко зв'язаний), якщо він не може бути представлений у вигляді об'єднання двох різних орграфів (визначеного звичайним чином); це еквівалентно тому, що зв'язна основа орграфа D. Припустимо додатково, що для будь-яких двох вершин v і w орграфа D існує проста орцепь з v w; тоді D називається сильно зв'язковим (цей термін настільки устоявся, що ми використовували його замість більш природного «орсвязний»). Ясно, що будь-який зв'язний граф зв'язаний, але зворотне неправильно: на рис. 1 зображено зв'язковий орграф, що не є дуже зв'язковим.
Різниця міжзв'язковимісильно зв'язковиморграфом стане ясніше, якщо ми розглянемо план міста, по всіх вулицях якого допускається лише односторонній рух. Тоді зв'язок відповідного орграфа означає, що ми можемо проїхати з будь-якої частини міста в будь-яку іншу, не звертаючи уваги на правила одностороннього руху; якщо ж цей орграф сильно зв'язаний, то ми можемо проїхати з будь-якої частини міста до будь-якої іншої, слідуючи завжди «правильним шляхом» вздовж вулиць з одностороннім рухом. Важливо, щоб система з одностороннім рухом була дуже зв'язною, і природно виникає питання: за яких умов карту вулиць можна перетворити на систему з одностороннім рухом у такий спосіб, щоб можна булопроїхати з будь-якої частини міста до будь-якої іншої? Якщо, наприклад, місто складається з двох частин, пов'язаних одним мостом, то ми ніколи не зможемо зробити всі його вулиці односторонніми, оскільки який би напрямок ми не приписали мосту, одна частина міста буде відрізана. (Зауважимо, що сюди включається і той випадок, коли в місті є глухий кут.) З іншого боку, якщо мостів немає, то завжди знайдеться відповідна одностороння система.
Для зручності називатимемо граф G орієнтованим, якщо кожне його ребро (розглядається як пара вершин) може бути впорядковане таким чином, що отриманий в результаті орграф буде дуже зв'язковим. Цей процес упорядкування ребер називатимемо «завданням орієнтації графа» або «приписуванням напрямків ребрам». Якщо, наприклад, G – граф, зображений на рис. 4 то його можна орієнтувати і отримати сильно зв'язний орграф, зображений на рис. 5.
Мал. 4. Граф
Мал. 5.з сильно зв'язковий орграф
Теорема. Нехай G - зв'язковий граф; він орієнтуємо тоді й лише тоді, коли кожне його ребро міститься, принаймні, в одному циклі.
Орграфи та матриці
Матрицею суміжностей А(D) орграфа D називається (р×р)-матриця aij, яка має aij= 1, якщо ViVj- дуга орграфа D, і aij=0 інакше. Матриця суміжностей якого має вигляд (рис. 6):
Мал. 6. Матриця суміжності графа
Легко перевірити, що суми елементів по рядках матриці A(D) дорівнюють півступеням результату вершин орграфа D, а суми елементів по стовпчикам - напівступеням заходу.
Як і у випадку графів, ступеня матриці суміжностей А орграфа дають повну інформацію про кількість маршрутів, що йдуть з однієї вершини до іншої. Теорема. (i, j)-й елемент аij n матриці А" дорівнює числу маршрутів довжини n,що йдуть з вершини vi у вершину vj.
Згадаємо тут коротко ще про три матриці, пов'язані з орграфом Ds - проматрицю досяжностей,матрицю відстанейіматрицю обходів. У матриці досяжностей R елемент rij дорівнює 1, якщо вершина vi досяжна з vj і дорівнює 0 в іншому випадку. У матриці відстаней (i, j)-й елемент дорівнює відстані з вершини vi вершину vj; якщо ж з vi в vj немає шляхів, то відповідний елемент вважаємо рівним нескінченності. У матриці обходів (i, j)-й елемент дорівнює довжині найдовшого шляху з vi в vj, а якщо таких шляхів немає, то знову ж таки вважаємо цей елемент рівним нескінченності. Для орграф D, показаного на рис. 7.
Слідство. Елементи матриць досяжностей і відстаней пов'язані зі ступенями матриці наступними співвідношеннями:
1) rii = 1 та dii = 0 для всіх i;
2) rij = 1 тоді і лише тоді, коли aij n > 0 для деякого n;
3) d(vi,vj) дорівнює найменшому з чисел n, для яких aijn> 0
Ефективних методів знаходження елементів матриці обходів немає. Ця проблема тісно пов'язана з деякими іншими давно поставленими алгоритмічними проблемами теорії графів, такими як знаходження кістякових циклів і контурів, а також вирішення задачі про комівояжера.
Поелементний твір В×С матриць B=bij і C=cij має своїм (i, j) елементом bijcij. Матрицю досяжностей орграфа можна використовуватиме знаходження його сильних компонент.