Сильная связность

Вспомните, что направленный граф называется сильно связным, если для каждых двух узлов u и v существует путь из u в v и путь из v в u.

Также полезно сформулировать некоторые термины для свойства, лежащего в основе этого определения; два узла u и v в направленном графе называются взаимодостижимыми, если существует путь из u в v и путь из v в u. (Таким образом, граф является сильно связным, если каждая пара узлов в нем взаимодостижима.)

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

Если узлы u и v являются взаимодостижимыми и узлы v и w являются взаимодостижимыми, то узлы u и w также являются взаимодостижимыми.

Доказательство. Чтобы построить путь от u к w, мы сначала перейдем от u к v (по пути, существование которого гарантируется взаимодостижимостью u и v), а затем от v к w (по пути, существование которого гарантируется взаимодостижимостью v и w).

Для проверки сильной связности направленного графа существует простой алгоритм с линейным временем выполнения, неявно базирующийся на (3.16). Мы выбираем любой узел s и проводим поиск BFS в G, начиная с s.

Затем BFS выполняется от s в Grev. Если хотя бы один из двух поисков не найдет все узлы, то очевидно, что G не является сильно связным.

Но допустим, мы выяснили, что из s существует путь в каждый другой узел, и из каждого другого узла существует путь s.

В этом случае s и v взаимодостижимы для каждого v, из чего можно сделать вывод о взаимодостижимости любых двух узлов u и v: s и u взаимодостижимы, s и v взаимодостижимы, и из (3.16) следует, что u и v также взаимодостижимы.

По аналогии с компонентами связности в ненаправленных графах мы можем определить сильную компоненту, содержащую узел s, для направленного графа как множество всех узлов v, для которых s и v является взаимодостижимыми.

Если задуматься, алгоритм из предыдущего абзаца в действительности вычисляет сильную компоненту, содержащую s: мы выполняем BFS, начиная с s, в G и Grev; множество узлов, достигнутых при обоих поисках, представляет собой множество узлов с путями в s и из s; следовательно, это множество является сильной компонентой, содержащей s.

На этом сходство между понятиями компоненты связности в ненаправленных графах и сильной компоненты в направленных графах не ограничивается.

Вспомните, что компоненты связности образуют естественное разбиение графа, поскольку каждые две компоненты либо идентичны, либо изолированы. Сильные компоненты также обладают этим свойством, причем фактически по той же причине, следующей из (3.16).

Для каждых двух узлов s и t в направленном графе их сильные компоненты либо идентичны, либо изолированны.

Доказательство. Возьмем два любых взаимодостижимых узла s и t; утверждается, что сильные компоненты, содержащие s и t, идентичны. В самом деле, для каждого узла v, если s и v взаимодостижимы, то, согласно (3.16), t и v также взаимодостижимы. Аналогичным образом, если t и v взаимодостижимы, то, согласно (3.16), s и v также взаимодостижимы.

С другой стороны, если s и t не являются взаимодостижимыми, то не может быть узла v, входящего в сильную компоненту каждого из этих узлов.

Если бы такой узел v существовал, то узлы s и v были бы взаимодостижимыми, узлы v и t были бы взаимодостижимыми, поэтому из (3.16) следовало бы, что s и t также являются взаимодостижимыми.

Хотя подробное обоснование здесь не приводится, при некоторой дополнительной работе возможно вычислить сильные компоненты всех узлов за общее время O(m + n).