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

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

Определение

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

Ссылки

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

[gkm-1] Перейти обратно: ^а ^б ^с ^д Грэм, РЛ ; Кнут, Делавэр ; Моцкин, Т.С. (1972), «Дополнения и транзитивные замыкания» (PDF) , Дискретная математика , 2 : 17–29, doi : 10.1016/0012-365X(72)90057-X , MR 0323577

[knuth-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Кнут, Дональд Э. (15 января 2022 г.), «Слабые компоненты», Искусство компьютерного программирования, том 4, предварительный выпуск 12A: Компоненты и обход (PDF) , стр. 11–14.

[tarjan-3] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Тарьян, Роберт Эндре (июль 1974 г.), «Новый алгоритм поиска слабых компонентов», Information Processing Letters , 3 (1): 13–15, doi : 10.1016/0020-0190(74)90040-4

[FOOTNOTEKnuth2022Exercise_81,_p._21-4] Кнут (2022) , Упражнение 81, с. 21.

[pacault-5] Пако, Жан Франсуа (1974), «Вычисление слабых компонентов ориентированного графа», SIAM Journal on Computing , 3 : 56–61, doi : 10.1137/0203005 , MR 0376418

[1]

[2]

[3]

[4]

[5]