подграфов (сильно зв'язкових компонентів) орієнтованого графа.
Для визначення сильно зв'язкових подграфов введемо поняття наступних матриць:
матриця досяжності R = | | r ij | |;
матриця контрдостіжімості Q = | | q ij | |;
матриця взаімодостіжімості H = | | h ij | |.
Розмір всіх матриць n ' n, де n - число вершин графа, елементи матриць визначаються таким чином:
r ij = 1, якщо вершина j досяжна з вершини i,
r ij = 0, якщо вершина j недосяжна з вершини i,
q ij = 1, якщо вершина i досяжна з вершини j,
q ij = 0, якщо вершина i недосяжна з вершини j,
h ij = 1, якщо вершина j досяжна з вершини i і вершина i досяжна з вершини j, тобто якщо r ij = 1 і q ij = 1.
h ij = 0, якщо вершина j недосяжна з вершини i або вершина i недосяжна з вершини j, тобто якщо r ij = 0 або q ij = 0.
Ставлення взаімодостіжімості, яке визначається матрицею H = | | h ij | |, розбиває всі безліч вершин V орграфа G на класи взаімодостіжімих вершин. Кожен такий клас породжує подграф, який називається сильно зв'язковим. Орграф і його сильно зв'язкові компоненти показані на рис. 3.18.
Для алгоритмізації процесу виділення сильно зв'язкових подграфов виконаємо наступні дії:
. Використовуючи техніку пошуку в глибину або в ширину, знайдемо матрицю досяжності R.
. Так як r ij = q ij , тобто R = Q T і Q = R T , то, транспоніруя матрицю R, отримаємо матрицю контрдостіжімості Q.
. З матриць R і Q отримаємо матр...
