НОУ ІНТУЇТ | лекція | Графи: уявлення, досяжність і зв'язність
Граф досяжності
Один з перших питань, що виникають при вивченні графів, це питання про існування шляхів між заданими або всіма парами вершин. Відповіддю на цей вопроc - введене вище відношення досяжності на вершинах графа G = (V, E): вершина w досяжна з вершини v, якщо v = w або в G є шлях з v в w. Інакше кажучи, ставлення досяжності є рефлексивним і транзитивним замиканням відношення E. Для неорієнтованих графів це відношення також симетрично і, отже, є відношенням еквівалентності на множині вершин V. У неорієнтованому графі класи еквівалентності по відношенню досяжності називаються зв'язковими компонентами. Для орієнтованих графів досяжність, взагалі кажучи, не повинна бути симетричним відношенням. Симетричною є взаємна досяжність.
Визначення 9.8. Вершини v і w орієнтованого графа G = (V, E) називаються взаємно досяжними, якщо в G є шлях з v в w і шлях з w в v.
Ясно, що ставлення взаємної досяжності є рефлексивним, симетричним і транзитивним і, отже, еквівалентність на множині вершин графа. Класи еквівалентності по відношенню взаємної досяжності називаються компонентами сильної зв'язності або двусвязного компонентами графа.
Розглянемо спочатку питання про побудову відносини досяжності. Визначимо для кожного графа його граф досяжності (званий іноді також графом транзитивного замикання), ребра якого відповідають шляхах вихідного графа.
Визначення 9.9. Нехай G = (V, E) - орієнтований граф. Граф досяжності G * = (V, E *) для G має той же безліч вершин V і наступне безліч ребер E * = {(u, v) | в графі G вершина v досяжна з вершини u}.
Приклад 9.3. Розглянемо граф G з прикладу 9.2.
Тоді можна перевірити, що граф досяжності G * для G виглядає так (нові ребра -петлі при кожній з вершин 1-5 не показані):
Яким чином по графу G можна побудувати граф G *? Один спосіб полягає в тому, щоб для кожної вершини графа G визначити безліч досяжних з неї вершин, послідовно додаючи в нього вершини, досяжні з неї шляхах і довжини 0, 1, 2 і т.д.
Ми розглянемо інший спосіб, заснований на використанні матриці суміжності AG графа G і булевих операцій. Нехай безліч вершин V = {v1, ..., vn}. Тоді матриця AG - це булева матриця розміру nxn.
Нижче для збереження подібності зі звичайними операціями над матрицями ми будемо використовувати "арифметичні" позначення для булевих операцій: через + будемо позначати диз'юнкцію 
а через x - кон'юнкцію 
Позначимо через En одиничну матрицю розміру nxn. покладемо 
. нехай 
. Наша процедура побудови G * заснована на наступному твердженні.
Лемма 9.2. нехай 
. тоді
Доказ проведемо індукцією по k.
Базис. При k = 0 і k = 1 твердження справедливо по визначенню 
і .
Індукційний крок. Нехай лема справедлива для k. Покажемо, що вона залишається справедливою і для k + 1. За визначенням 
маємо:
Припустимо, що в графі G з vi в vj є шлях довжини <= k + 1. Розглянемо найкоротший з таких шляхів. Якщо його довжина <= k, то за припущенням індукції a_ {ij} ^ {(k)} = 1. Крім того, ajj (1) = 1. Тому aij (k) ajj (1) = 1 і aij (k + 1) = 1. Якщо довжина найкоротшого шляху з з vi в vj дорівнює k + 1, то нехай vr - його передостання вершина. Тоді з vi в vr є шлях довжини k і за припущенням індукції air (k) = 1. Так як 
, То a_ {rj} ^ {(1)} = 1. Тому air (k) arj (1) = 1 і aij (k + 1) = 1.
Назад, якщо aij (k + 1) = 1, то хоча б для одного r доданок air (k) arj (1) в сумі дорівнює 1. Якщо це r = j, то aij (k) = 1 і по індуктивному припущенню в G є шлях з vi в vj довжини <= k. Якщо ж 
, То air (k) = 1 і arj (1) = 1. Це означає, що в G є шлях з vi в vr довжини <= k і ребро . Об'єднавши їх, отримуємо шлях з vi в vj довжини <= k + 1.
З лем 9.1 та 9.2 безпосередньо отримуємо
Слідство 1. Нехай G = (V, E) - орієнтований граф з n вершин і, а G * - його граф досяжності. Тоді A_ {G *} = 
. Доказ. З леми 5.1 випливає, що, якщо в G є шлях з u в 
, То в ньому є і простий шлях з u в v довжини <= n-1. А по лемі 5.2 все такі шляхи представлені в матриці 
.
Таким чином процедура побудови матриці суміжності AG * графа досяжності для G зводиться до зведення матриці 
в ступінь n-1. Зробимо кілька зауважень, що дозволяють спростити цю процедуру.
Для зведення матриці
в довільну ступінь n досить виконати 
возведений в квадрат: де k - це найменше число таке, що 2k> = n.
- Так як на діагоналі в матриці стоять одиниці, то для будь-яких i <j все одиниці матриці
зберігаються в матриці 
, Зокрема, і в матриці 
. Якщо при обчисленні елемента aij (2) матриці
за стандартною формулою виявляється таке r, що air = 1 і arj = 1, то і вся сума aij (2) = 1. Тому інші складові можна не розглядати.
Приклад 9.3. Розглянемо як приклад обчислення матриці графа досяжності AG * для графа G, представленого на ріс.9.2 . В цьому випадку
Так як у G є 6 вершин, то 
. Обчислимо цю матрицю:
і 
(Остання рівність неважко перевірити). Таким чином,
Як бачимо, ця матриця дійсно задає граф 
, Представлений на рис.9.3 .