Определить, является ли граф полусвязным или нет

Question

Направленный граф G = (V, E) называется полусвязным, если для всех пар вершин u, v в V имеем u -> v или v -> u путь. Дайте эффективный алгоритм, чтобы определить, является ли G пол соединенных

Answer 1

O(V^3) Trivial решение могло бы использовать floyd warshal все к все кратчайший путь, но это излишнее (с точкой зрения сложности времени).

Это можно сделать в O(V+E).

претензия:

ДАГА пола соединено в топологической сортировке, для каждого i, там есть ребро (vi,vi+1)

Доказательство:

Учитывая ДАГ с топологической сортировкой v1,v2,...,vn:

Если нет края (vi,vi+1) для некоторые i, то также нет пути (vi+1,vi) (потому что это топологический вид DAG), и граф не является полусвязным.

Если для каждого i есть ребро (vi,vi+1), то для каждого i,j (ivi- > Vi + 1- > > ...- VJ-1- > VJ, а граф полу подключен.

из этого мы можем получить алгоритм:.

1. Найти Максимальный СОС в графе
2. построить SCC граф G '= (U, E') таким образом, что U представляет собой набор SCCs E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
3. Сделайте топологическую сортировку по G '
4. Проверьте, существует ли для каждого i край Vi, Vi + 1.

Корректность доказательство:

Если граф является полу подключен, для пары (v1,v2), таким образом, что существует путь v1->...->v2 - Пусть V1, V2 быть их СОС. Существует путь от V1 до V2 и, следовательно, также от v1 до v2, поскольку все узлы в V1 и V2 сильно связаны.

Если алгоритм дал истинное значение, чем для любых двух заданных узлов v1, v2 - в SCC V1 и V2. Существует путь от V1 до V2 (без потери общности) и, следовательно, также от v1 до v2.

---

В качестве примечания, и каждый полу-связный граф имеет корень (вершина r, что приводит ко всем вершинам):

Доказательство:
Предположим, что нет корня. Определить #(v) = |{u | there is a path from v to u}| (количество узлов, у которых есть путь от v к ним).
Выберите a такой, что #(a) = max{#(v) | for all v}.
a не является корнем, поэтому существует некоторый узел u, у которого нет пути от a. Поскольку граф полусвязан, это означает, что существует путь u->...->a. Но это означает, что #(u) >= #(a) + 1 (все узлы достижимы от a, а также u).
Противоречие до максимальной величины #(a), при этом есть корень.

Answer 2

Soltuin Amit полностью описывает наиболее эффективный подход. Я могу просто добавить, что можно заменить шаг 4, проверяя, существует ли более одного топологического порядка G '. Если да, то график не является полусвязным. В противном случае граф полусвяз. Это можно легко включить в Kahn's algorithm для нахождения топологического порядка графика.

Другим менее эффективным решением, которое работает в квадратичное время, является следующее.

Сначала постройте еще один граф G *, который является обратным исходному графу. Затем для каждой вершины v из G вы запускаете DFS из v в G и рассматриваете множество достижимых узлов как R_v. Если R_v! = V (G), то запустите другую DFS из v в G * и пусть множество достижимых узлов будет R _v. Если объединение R_v и R _v не является V (G), то граф не является полусвязным.