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

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

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

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

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

Для проверки сильной связности направленного графа существует простой алгоритм с линейным временем выполнения, неявно базирующийся на (3.16). Мы выбираем любой узел s и проводим поиск BFS в G, начиная с s. Затем BFS выполняется от s в Grev. Если хотя бы один из двух поисков не найдет все узлы, то очевидно, что G не является сильно связным. Но допустим, мы выяснили, что из s существует путь в каждый другой узел, и из каждого другого узла существует путь s. В этом случае s и v взаимодостижимы для каждого v, из чего можно сделать вывод о взаимодостижимости любых двух узлов и и v: s и и взаимодостижимы, s и v взаимодостижимы, и из (3.16) следует, что и и v также взаимодостижимы. ■

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

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

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

(3.17) Для каждых двух узлов 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). ■

3.6.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Сильная связность:

  1. Сильная энергия
  2. ПОДЧИНЕНИЕ СИЛЬНЫМ
  3. СИЛЬНЫЕ ЖЕЛАНИЯ И ПОСТОЯННЫЕ СТИМУЛЫ
  4. 20. Стремитесь воспитать сильный характер
  5. 15.3. ВЫЖИВАЕТ СИЛЬНЕЙШИЙ
  6. Сильными не рождаются
  7. Планеты с сильным космическим статусом
  8. Отсутствие сильной воли
  9. Человек становился сильнее.
  10. Сильное психолого-педагогическоевоздействие на персонал
  11. Сильно ли вы отличаетесь внешне от нас?
  12. СИЛЬНОЕ ОТКЛОНЕНИЕ ОТ СВОЕГО РУСЛА