Сильно связные компоненты

В оставшейся части этой главы мы обратим наше внимание на очень большие графы. Чтобы изучить несколько дополнительных алгоритмов, будем использовать графы связей между хостами в интернете и ссылок между веб-страницами.

Поисковые системы вроде Google и Bing используют в своих интересах тот факт, что страницы в вебе образуют очень большой направленный граф. Чтобы преобразовать в него Всемирную Паутину, мы будем рассматривать страницы, как вершины, а гиперссылки между ними - как соединяющие их рёбра. Рисунок 30 демонстрирует очень маленькую часть графа, получившегося из ссылок от одной страницы к другой со стартовой точкой на домашней странице Luther College’s Computer Science. Конечно, этот граф был бы огромным, так что мы ограничили его сайтами, на которых есть не более десяти ссылок с домашней страницы CS.

../_images/cshome.png

Рисунок 30: Граф из ссылок с домашней страницы Luther Computer Science

Если вы изучите граф на рисунке 30, то сможете сделать несколько любопытных наблюдений. Во-первых, многие из веб-сайтов графа - прочие сайты Luther College. Во-вторых, в графе присутствует несколько ссылок на колледж в Айове. В-третьих, в графе имеется несколько ссылок на другие гуманитарные колледжи. Из этого можно сделать заключение, что здесь присутствует некая внутренняя структура, объединяющая вместе сайты, в чём-то похожие друг на друга.

Один из алгоритмов, помогающих найти кластеры из сильно связных вершин графа, называется алгоритмом поиска сильно связных компонентов (SCC - от англ. strongly connected components). Формально мы можем определить сильно связную компоненту, \(C\) графа \(G\), как наибольшее подмножество вершин \(C \subset V\) таких, что для каждой пары вершин \(v, w \in C\) существует путь от \(v\) до \(w\) и от \(w\) до \(v\). На рисунке 27 показан простой граф с тремя сильно связными компонентами, которые выделены разными затенёнными областями.

../_images/scc1.png

Рисунок 31: Направленный граф с тремя сильно связными компонентами

После определения сильно связных компонент, мы можем показать упрощённый вид графа, собрав все вершины каждой из них в одну большую. Упрощённая версия графа с рисунка 31 показана на рисунке 32.

../_images/scc2.png

Рисунок 32: Упрощённый граф

Вновь мы видим, что, используя поиск в глубину, можем создать очень мощный и эффективный алгоритм. Однако, прежде нужно рассмотреть ещё одно определение. Транспозиция графа \(G\) определяется, как граф \(G^T\), у которого все рёбра имеют обратное направление. Т.е., если в оригинальном графе ребро направлено из узла А в узел В, то \(G^T\) будет содержать ребро из узла В в узел А.

Рисунки 33 и 34 демонстрируют простой граф и его транспозицию.

../_images/transpose1.png

Figure 33: Граф \(G\)

../_images/transpose2.png

Figure 34: Его транспозиция \(G^T\)

Посмотрите ещё раз на рисунки. Обратите внимание, что граф на рисунке 33 имеет две сильно связные компоненты. А теперь взгляните на рисунок 34. На нём так же изображены две сильно связные компоненты.

Теперь мы можем описать алгоритм вычисления SCC в графе.

  1. Вызвать dfs для графа \(G\), чтобы вычислить “времена” выхода каждой вершины.
  2. Вычислить \(G^T\).
  3. Вызвать dfs для графа \(G^T\), но в основном цикле DFS исследовать каждую вершину в порядке убывания “времени” выхода.
  4. Каждое дерево из леса, найденного на шаге 3, будет сильно связной компонентой. Для её идентификации осталось вывести id каждого узла всех деревьев в лесу.

Давайте пошагово проследим описанные выше пункты для графа на рисунке 31. Рисунок 35 показывает “времена” входа и выхода, вычисленные для оригинального графа с помощью алгоритма DFS. На рисунке 36 показаны они же, но вычисленные для транспозиции графа.

../_images/scc1a.png

Рисунок 35: “Времена” выхода для графа \(G\)

../_images/scc1b.png

Рисунок 36: “Времена” выхода для \(G^T\)

Наконец, на рисунке 37 показан лес из трёх деревьев, созданный на третьем шаге SCC алгоритмом. Заметьте, что мы не даём вам код на Python для этого алгоритма, поскольку его написание остаётся в качестве упражнения.

../_images/sccforest.png
Next Section - Задача поиска кратчайшего пути