Слабый компонент

Разбиение вершин ориентированного графа

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

Определение

Слабые компоненты были определены в статье 1972 года Рональдом Грэмом , Дональдом Кнутом и (посмертно) Теодором Моцкиным по аналогии с сильно связными компонентами ориентированного графа, которые образуют тончайшее возможное разбиение вершин графа на подмножества, частично упорядочены по достижимости. Вместо этого они определили слабые компоненты как наилучшее разбиение вершин на подмножества, которые полностью упорядочены по достижимости. ^{[1] [2]}

Более подробно Кнут (2022) определяет слабые компоненты посредством комбинации четырех симметричных отношений на вершинах любого ориентированного графа, обозначенных здесь как , , и : ${\displaystyle \Leftrightarrow }$ ${\displaystyle \parallel }$ ${\displaystyle \approx }$ ${\displaystyle \asymp }$

• Для любых двух вершин и графа тогда и только тогда, когда каждая вершина достижима из другой: в графе существуют пути от до и от до . Отношение является отношением эквивалентности , и его классы эквивалентности используются для определения сильно связных компонентов графа. ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\Leftrightarrow v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle \Leftrightarrow }$
• Для любых двух вершин и графа тогда и только тогда, когда ни одна вершина не достижима из другой: в графе не существует путей ни в одном направлении между и . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\parallel v}$ ${\displaystyle u}$ ${\displaystyle v}$
• Для любых двух вершин и графа тогда и только тогда, когда либо или . То есть между этими вершинами может быть двусторонняя связь, либо они могут быть взаимно недоступными, но односторонней связи у них может не быть. ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\approx v}$ ${\displaystyle u\Leftrightarrow v}$ ${\displaystyle u\parallel v}$
• Отношение определяется как транзитивное замыкание . То есть, когда существует последовательность вершин, начинающаяся с и заканчивающаяся на , такая, что каждая последовательная пара в последовательности связана соотношением . ${\displaystyle \asymp }$ ${\displaystyle \approx }$ ${\displaystyle u\asymp v}$ ${\displaystyle u\approx \cdots \approx v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \approx }$

Тогда существует отношение эквивалентности : каждая вершина связана сама с собой (поскольку она может достичь себя в обоих направлениях по путям нулевой длины), любые две вершины, связанные между собой, могут быть заменены друг на друга без изменения этого отношения (поскольку построено вне симметричных отношений и ), и является транзитивным отношением (поскольку оно является транзитивным замыканием другого отношения). Как и любое отношение эквивалентности, его можно использовать для разделения вершин графа на классы эквивалентности , подмножества вершин, такие, что две вершины связаны тогда и только тогда, когда они принадлежат одному и тому же классу эквивалентности. Эти классы эквивалентности являются слабыми компонентами данного графа. ^[2] ${\displaystyle \asymp }$ ${\displaystyle \asymp }$ ${\displaystyle \asymp }$ ${\displaystyle \asymp }$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle \parallel }$ ${\displaystyle \asymp }$ ${\displaystyle \asymp }$

Исходное определение Грэма, Кнута и Моцкина эквивалентно, но сформулировано несколько иначе. Учитывая ориентированный граф , ${\displaystyle G}$ они сначала строят другой граф как граф дополнения к транзитивному замыканию . Как описывает Тарьян (1974), ребра в представляют собой не-пути , пары вершин, которые не соединены путем в . ^[3] Тогда две вершины принадлежат одному и тому же слабому компоненту , если они принадлежат одному и тому же сильно связному компоненту или . ^{[1] [3]} Как доказывают Грэм, Кнут и Моцкин, это условие определяет отношение эквивалентности, ^[1] то же самое, определенное выше как . ^[4] ${\displaystyle {\hat {G}}}$ ${\displaystyle G}$ ${\displaystyle {\hat {G}}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle {\hat {G}}}$ ${\displaystyle \asymp }$

В соответствии с этими определениями ориентированный граф называется слабо связным , если он имеет ровно одну слабую компоненту. Это означает, что его вершины не могут быть разделены на два подмножества, так что все вершины в первом подмножестве могут достигать всех вершин во втором подмножестве, но так, что ни одна из вершин во втором подмножестве не может достичь ни одной из вершин. в первом подмножестве. Он отличается от других представлений о слабой связности в литературе, таких как связность и компоненты в базовом несвязном графе, для которых Кнут предлагает альтернативную терминологию « ненаправленные компоненты» . ^[2]

Характеристики

Если и являются двумя слабыми компонентами ориентированного графа, то либо все вершины в могут достичь всех вершин по путям в графе, либо все вершины в могут достичь всех вершин в . Однако между этими двумя компонентами не может существовать отношений достижимости в обоих направлениях. Следовательно, мы можем определить порядок слабых компонентов, согласно которому все вершины в могут достигать всех вершин в . По определению, . Это асимметричное отношение (два элемента могут быть связаны только в одном направлении, но не в другом), и оно наследует свойство транзитивности от транзитивности достижимости. Следовательно, он определяет полное упорядочение по слабым компонентам. Это наилучшее возможное разбиение вершин на полностью упорядоченный набор вершин, совместимый с достижимостью. ^[1] ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X<Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\nless X}$

Это упорядочение слабых компонентов можно альтернативно интерпретировать как слабое упорядочение самих вершин с тем свойством, что при слабом упорядочении обязательно существует путь от до , но не от до . Однако это не полная характеристика этого слабого упорядочения, поскольку две вершины и могут иметь один и тот же порядок достижимости, но при этом принадлежать к одному и тому же слабому компоненту, что и друг друга. ^[2] ${\displaystyle u<v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle v}$

Каждая слабая компонента представляет собой объединение сильно связных компонент. ^[2] Если сильно связные компоненты любого данного графа сжимаются до одиночных вершин, образуя ориентированный ациклический граф ( конденсация данного графа), а затем эта конденсация топологически отсортирована , то каждый слабый компонент обязательно появляется как последовательная подпоследовательность топологического порядка сильных компонент. ^[3]

Алгоритмы

Алгоритм вычисления слабых компонентов заданного ориентированного графа за линейное время был описан Пако (1974) и впоследствии упрощен Тарьяном (1974) и Кнутом (2022). ^{[2] [3] [5]} Как отмечает Тарьян, алгоритм сильно связанных компонентов Тарьяна, основанный на поиске в глубину , выводит сильно связанные компоненты в (обратном) топологически отсортированном порядке. Алгоритм для слабых компонентов генерирует сильно связные компоненты в этом порядке и поддерживает разделение компонентов, которые были сгенерированы до сих пор, на слабые компоненты их индуцированного подграфа . После того как все компоненты сгенерированы, этот раздел будет описывать слабые компоненты всего графа. ^{[2] [3]}

Удобно поддерживать текущее разбиение на слабые компоненты в стеке , при этом каждый слабый компонент сохраняет дополнительно список своих источников , сильно связных компонентов, не имеющих входящих ребер от других сильно связных компонентов в том же слабом компоненте, причем самые последние сначала сгенерированный исходный код. Каждый вновь сгенерированный сильно связанный компонент может сам по себе сформировать новый слабый компонент или может в конечном итоге объединиться с некоторыми из ранее созданных слабых компонентов в верхней части стека, для которых он не может достичь всех источников. ^{[2] [3]}

Таким образом, алгоритм выполняет следующие шаги: ^{[2] [3]}

• Инициализируйте пустой стек слабых компонентов, каждый из которых связан со списком своих исходных компонентов.
• Используйте алгоритм сильно связных компонентов Тарьяна для генерации сильно связных компонентов данного графа в обратном топологическом порядке. Когда сгенерирован каждый сильносвязный компонент , выполните с ним следующие шаги: ${\displaystyle S}$
  • Пока стек не пуст и не имеет ребер до верхнего слабого компонента стека, извлеките этот компонент из стека. ${\displaystyle S}$
  • Если стек все еще не пуст, и некоторые источники его верхнего слабого компонента не затронуты ребрами из , ${\displaystyle S}$ снова извлеките этот компонент из стека.
  • Создайте новый слабый компонент , ${\displaystyle W}$ содержащий в качестве источников все необработанные источники из верхнего компонента, который был извлечен, и поместите его в стек. ${\displaystyle S}$ ${\displaystyle W}$

Каждый тест на попадание каких-либо ребер в слабый компонент может выполняться за постоянное время, как только мы находим ребро от самого последнего сгенерированного ранее сильно связанного компонента, путем сравнения целевого компонента этого ребра с первым источником второго-последнего. -верхний компонент в стеке. ${\displaystyle S}$ ${\displaystyle S}$

Рекомендации

1. Грэм, RL ; Кнут, Делавэр ; Моцкин, Т.С. (1972), «Дополнения и транзитивные замыкания» (PDF) , Дискретная математика , 2 : 17–29, doi : 10.1016/0012-365X(72)90057-X, MR  0323577
2. Кнут, Дональд Э. (15 января 2022 г.), «Слабые компоненты», Искусство компьютерного программирования, Том 4, Предвыпуск 12A: Компоненты и обход (PDF) , стр. 11–14
3. Тарьян, Роберт Эндре (июль 1974 г.), «Новый алгоритм поиска слабых компонентов», Information Processing Letters , 3 (1): 13–15, doi : 10.1016/0020-0190(74)90040-4
4. Кнут (2022), Упражнение 81, с. 21.
5. Пако, Жан Франсуа (1974), «Вычисление слабых компонентов ориентированного графа», SIAM Journal on Computing , 3 : 56–61, doi : 10.1137/0203005, MR  0376418