Supongamos que tenemos un grafo dirigido y dos nodos y . Me gustaría saber si ya hay algoritmos para calcular el siguiente problema de decisión:
¿Hay al menos dos caminos entre y de la misma longitud?
¿Qué tal la complejidad? ¿Puedo resolverlo en tiempo polinómico?
Me gustaría agregar una nueva restricción en el gráfico, tal vez el problema sea más solucionable. En la matriz de adyacencia, cada columna no está vacía. Entonces, cada nodo tiene al menos una flecha en la entrada y también hay al menos un nodo conectado a sí mismo. Entonces, si el nodo es el -ésimo nodo, entonces es un borde en el gráfico.
complexity-theory
graph-theory
time-complexity
graphs
Paolo Parisen T.
fuente
fuente
Respuestas:
Considere un gráfico , queremos saber si hay dos caminos diferentes de a de la misma longitud. ¿Qué hacer? Simple: codifique dos caminos en uno. Defina el gráfico con vértices . Haces un paso en al hacer dos pasos independientes en . El bit adicional le dice si las dos rutas ya se han separado entre sí.A B G ′ V × V × { 0 , 1 } G ′ GG A B G′ V×V×{0,1} G′ G
Formalmente, hay una arista en iff , en y .G ′ i → i ′ j → j ′ G e ′ = e ∨ ( i , i ′ ) ≠ ( j , j ′ )(i,j,e)→(i′,j′,e′) G′ i→i′ j→j′ G e′=e∨(i,i′)≠(j,j′)
El algoritmo verifica si hay una ruta a en , que es , o algo así como .(A,A,0) (B,B,1) G′ O(V4) O((V+E)2)
Si acepta que este algoritmo es correcto, entonces, como consecuencia, la ruta en tiene una longitud máxima de , por lo tanto, las posibles "colisiones de ruta" deben ocurrir más tarde en esa longitud. Puede obtener un algoritmo partir de esta observación, donde es la complejidad de la multiplicación de matrices (pregunte si necesita un spoiler ...).G′ 2n2 O(VωlogV) ω
Creo firmemente que hay un algoritmo , que utiliza más de la estructura del problema.O(V+E)
fuente
Probablemente tengo una respuesta para este problema, pero no estoy seguro de que funcione.
No es importante "encontrar" los dos caminos, lo único importante es "saber" si existen o no. No creo que este sea un problema NP completo.
Por lo tanto, tomar la matriz de adyacencia . Podemos suponer fácilmente que está lleno de valor 0,1. (0 = sin borde; 1 = hay un borde) Usemos el siguiente álgebra con 3 valores (0,1,2), donde todo funciona como de costumbre excepto: 2 + <algo> = 2 ; 2 ∗ <lo que sea mayor que 0> = 2A 2+<something>=2 2∗<whatever greater than 0>=2
Entonces, si hay dos caminos de la misma longitud desde , espero que haya un valor p tal que ( A p ) i , j = 2 .i,j p (Ap)i,j=2
Sea el número de vértices en el gráfico (o, digamos, que A tiene dimensión n × n ). No sé el valor de p , pero si itero A multiplicando consigo mismo como máximo n 2, debería encontrar la respuesta. (entonces, p < n 2 ) (el sentido es que verifico A , luego verifico A 2 , luego verifico A 3 y así sucesivamente ...)n A n×n p A n2 p<n2 A A2 A3
Aquí está mi argumentación:
Me detengo para iterar una vez que encontré .(Ap)i,j=2
¿Me equivoco?
fuente