Algoritmo de tiempo lineal para hacer un gráfico fuertemente conectado

Tenemos un dígrafo débilmente acíclico.Algoritmo de tiempo lineal para hacer un gráfico fuertemente conectado

También tenemos un conjunto A que contiene vértices de G que tienen en grado cero y un conjunto B que contiene vértices que tienen un grado cero. (el tamaño de A es más pequeño que el tamaño de B).

Además de eso, también sabemos que si los elementos en A y B tienen un orden particular (por ejemplo, A = a1, a2, ..., a.m. y B = b1, b2, ..., bn) a DFS comenzó en ai visitas bi (1≤ i ≤ m).

¿Es posible diseñar un algoritmo de tiempo lineal que hace que G se conecte fuertemente al agregarle tan pocos bordes como sea posible?

Fuente

2011-11-16 Anonymous

-> math.stackexchange.com? – Vlad

"DFS iniciado en ai visitas bi (1≤ i ≤ m)" No lo entiendo. ¿Hay (1) elementos repetitivos en A y vacíos en B O (2) su gráfico tiene una propiedad especial, que comenzando desde el vértice en grado cero podemos lograr un estrictamente un vértice de cero grado cero (3) nada de eso (dé su explicación en ese caso). –

Añadir arcos b _j -> a _{j + 1} para j = 1, ..., m-1 y arcos b _j -> a para j = m, ... , n.

El gráfico resultante está conectado fuertemente debido a y b de las A están fuertemente conectados por los arcos añadidos y los caminos de un _i a B _i y, para cada nodo x, existen i, j tal que hay existe una ruta en el gráfico original de _i a xy una ruta en el gráfico original de x a b _j.

no podemos utilizar un menor número de arcos, porque un arco saliente debe ser añadido a cada uno de b , ..., b _n.

Fuente

2011-11-16 17:35:10 Per

Es muy simple. Pero hay una pregunta. Hay ambigüedad en la declaración original ** Pregunté acerca de **. Si ha dirigido un gráfico acíclico donde la versión no dirigida es un gráfico conectado Y un número de vértice con un grado cero (A) menor o igual que un número de vértice con un grado cero (B) no significa que tienes correspondencia entre A y B. ** Si puedes probarlo, HAZLO. Sin este hecho, no es una respuesta **. –

@ Wisdom's Wind ¿Por qué debería probar lo que es claramente una hipótesis en la redacción de la pregunta actual? – Per

Puede haber un problema con esta solución. Considere un gráfico compuesto por dos anillos, X e Y, y un punto aislado.Hay un enlace de X a Y y de Y al punto aislado. El punto aislado es el único miembro del conjunto B. Se conecta como un gráfico acíclico, pero no está fuertemente conectado, porque no se puede obtener de Y a X, o del nodo aislado a Y. Como A no tiene elementos, tu propuesta sería no agregue ningún enlace – mcdowella

Editado - Después de no producir una solución con menos enlaces:

Puede ejecutar http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm en tiempo lineal. Propongo que hagas esto y ten en cuenta que "ningún componente fuertemente conectado se identificará antes que cualquiera de sus sucesores". Por lo tanto, el primer componente fuerte del gráfico no debe ser un sucesor de ninguno de los otros componentes. Sugiero que cada vez que emita un componente fuertemente conectado que no tenga sucesor, agregue un enlace que lo conecte a este primer componente. Sugiero que también agregue un enlace cada vez que esencialmente reinicia el algoritmo de Tarjan con una llamada no recursiva a strongconnect(), conectando el primer componente al vértice en el que está reiniciando.

Con estos enlaces puede pasar del primer componente fuerte a cualquier otro componente, y de cualquier otro componente al primer componente fuerte. - desafortunadamente esta no es necesariamente la solución con menos enlaces - ver el segundo comentario de Per a continuación.

Fuente

2011-11-16 18:56:02 mcdowella

¿Cómo maneja más de un componente sin predecesores? – Per

Mi intención es que los componentes secundarios sin predecesores sean los componentes en los que el algoritmo de Tarjan se reinicie con llamadas no recursivas, de modo que obtengan enlaces del primer componente y sean accesibles desde él. Sus sucesores, o ellos mismos, obtienen enlaces al primer componente, completando el ciclo. Sin embargo, dado que el punto que mencioné en su respuesta era incorrecto, ¿quizás también estoy equivocado aquí? – mcdowella

Si entiendo tu algoritmo correctamente, en el gráfico {a1-> b1, a1-> b2, a2-> b2}, el componente fuerte {a1} podría ser el primero emitido, seguido de {b1} y {b2}, así que b1 y b2 obtienen enlaces a a1. La conexión de a1 y a2 requiere un enlace más para un total de 3, frente a los 2 necesarios para conectar b1-> a2, b2-> a1. – Per

Algoritmo de tiempo lineal para hacer un gráfico fuertemente conectado

Respuesta

Cuestiones relacionadas