Набор всех компонент связности

До настоящего момента мы говорили о компоненте связности, содержащей кон- кретный узел 5. Однако для каждого узла в графе существует своя компонента связности. Какими отношениями связаны эти компоненты?

Как выясняется, эти отношения четко структурированы и описываются следу- ющим утверждением.

(3.8) Для любых двух узлов 5 и t в графе их компоненты связности либо иден- тичны, либо не пересекаются.

Это утверждение интуитивно понятно, если взглянуть на граф наподобие изображенного на рис. 3.2. Граф разделен на несколько частей, не соединенных ребрами; самая большая часть — компонента связности узлов 1-8, средняя — ком- понента связности узлов 11, 12 и 13 и меньшая — компонента связности узлов 9 и 10. Чтобы доказать это общее утверждение, достаточно показать, как точно определяются эти «части» для произвольного графа.

Доказательство. Возьмем любые два узла 5 и t в графе G, между которыми существует путь. Утверждается, что компоненты связности, содержащие 5 и t, представляют собой одно и то же множество. Действительно, для любого узла v в компоненте 5 узел v также должен быть достижим из t через путь: мы можем про- сто перейти из t в 5, а затем из 5 в v. Аналогичные рассуждения работают при смене ролей 5 и t, так что узел входит в компоненту одного в том, и только том случае, если он также входит в компоненту другого.

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

Из этого доказательства вытекает естественный алгоритм получения всех ком- понент связности графа, основанный на расширении одной компоненты за раз. Алгоритм начинает с произвольного узла 5, а затем использует BFS (или DFS) для генерирования его компоненты связности. Далее мы находим узел v (если он существует), который не был посещен при поиске от 5, и итеративным методом, используя BFS от узла v, генерирует компоненту связности — которая, согласно

(3.8) , изолирована от компоненты 5. Это продолжается до тех пор, пока алгоритм не посетит все узлы.

3.3.

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

Еще по теме Набор всех компонент связности:

  1. Неполнота набора альтернатив.
  2. Набор черт или нечто большее?
  3. «Ролевой набор» («role-set») и референтная группа*
  4. Таблица 4. Стандартный набор трав для лечения по методу Лессура
  5. Функциональные компоненты правового сознания.
  6. § 3.1. Основные структурные компоненты организации
  7. Участие образных компонентов в мышлении следователя
  8. Основные компоненты.
  9. 54. Основные компоненты социального контроля
  10. Дополнительные компоненты (общие).
  11. Дополнительные компоненты (специальные)
  12. Дополнительные компоненты общие.