¿Cuál es la forma más eficiente de determinar si un gráfico dirigido es simplemente conexo?

Question

Estoy trabajando en una tarea en la que uno de los problemas pide derivar un algoritmo para verificar si un gráfico dirigido G=(V,E) está individualmente conectado (hay como máximo una ruta simple de u a v para todos los vértices distintos u, v de v.

Por supuesto, puedes comprobarlo con fuerza bruta, que es lo que estoy haciendo ahora, pero quiero saber si hay una manera más eficiente.¿Alguien podría indicarme la dirección correcta?

Answer 1

¿Usted ha intentado DFS .

Run DFS for every vertex in the graph as source
    If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.

Complejidad O (v ^ 2), o (v) dfs como no repetición.

Answer 2

Hay una mejor respuesta para esta pregunta.puedes hacer eso en O(|V|^2).y con más esfuerzo puedes hacerlo en tiempo lineal.

Primero se encuentran componentes fuertemente conectados de G.En cada componente fuerte, buscas para encontrar estos casos:1) Si hay un borde directo en este componente, no está conectado individualmente, 2) Si hay un borde transversal en este componente, no está conectado individualmente, 3) Si hay al menos dos bordes de espalda en el árbol arraigado en vértice u, a los antepasados ​​adecuados de ti, entonces no está conectado individualmente.

esto se puede hacer en O(E).(Creo que excepto en el caso 3.¡¡No pude implementarlo bien!!).

Si no ocurrió ninguno de los casos anteriores, debe verificar si hay un borde cruzado o un borde delantero en G^SCC (gráfico G, con componentes fuertes reemplazados por nodos individuales), ya que no tenemos bordes posteriores, se puede hacer mediante repitiendo dfs en cada vértice de este gráfico en O(|V|^2).

Answer 3

Leer éste . Realmente explica así.

Answer 4

No estoy de acuerdo que su complejidad será O (V ^ 2), como en la SSE no llamamos para cada vértice como ven en la Introducción al algoritmo libro también, la sintaxis es DFS (G). Sólo llamamos SSE en el gráfico conjunto no para cualquier solo vértice a diferencia de BFS. Así que aquí, en este caso, en mi opinión, tenemos que comprobarlo llamando DFS once.If un vértice visitado se encuentra de nuevo, el gráfico no está conectado por separado (sin duda tenemos que llamarlo para cada componente desconectado pero ya incluido en el código ). SO la complejidad será O (V + E). Como aquí por lo tanto la complejidad deben ser E = V O (V).

Answer 5

pensé en esto: 1) Ejecutar DFS de cualquier vértice, si todos los vértices están cubiertos en el DFS sin bordes delanteros (no puede haber cruz como otro no estarán cubiertos todos los vértices), entonces puede ser un candidato potencial.

2) Si un vértice (nivel j) que se encuentra en la DFS tiene un borde de nuevo a nivel i entonces ningún otro vértice encontrado después de que se debe tener un borde posterior hacia cualquier vértice con un nivel de menos de j y cada vértice mucho sea alcanzable a la raíz (comprobado con segundas DFS).

Esto lo hace en un tiempo lineal si esto es correcto.

Answer 6

Tome un vistazo a la definición de trayectoria simple. Un gráfico cíclico se puede conectar individualmente. DFS no funcionará para A->B, B->A, que está conectado por separado.

Los siguientes usos de papel conectado fuertemente componente para resolver este.

https://www.cs.umd.edu/~samir /grant/khuller99.ps

Answer 7

Ejecutar DFS vez desde cada vértice. La gráfica se individualmente conectado si y sólo si no hay bordes anteriores y no hay bordes transversales dentro de una componente.

Complejidad: O (V.E)