¿Cómo detectar si al romper un borde se descompone un gráfico?

Question

Tengo un gráfico que comienza con un único nodo raíz. Los nodos se agregan uno por uno al gráfico. En el momento de creación del nodo, deben estar vinculados al nodo raíz, oa otro nodo, por un solo borde. Los bordes también se pueden crear y eliminar (uno por uno, entre dos nodos). Los nodos se pueden eliminar de a uno por vez. La creación de nodos y bordes, las operaciones de eliminación pueden ocurrir en cualquier orden arbitraria.

OK, así que aquí está mi pregunta: Cuando se borra un borde, ¿es posible determinar, en tiempo constante (es decir, con un algoritmo O), si esto divide el gráfico en dos subgrafos disjuntos? Si lo hace, ¿a qué lado del borde pertenece el nodo raíz?

Estoy dispuesto a mantener, dentro de unos límites razonables, cualquier estructura de datos adicional que pueda facilitar la obtención de esta información.

Tal vez no sea posible hacerlo en O (1), de ser así, se apreciarán todos los consejos sobre la literatura.

Editar: El gráfico es un gráfico dirigido.

Editar 2: Bien, tal vez pueda restringir el caso a la eliminación de bordes del nodo raíz . [Editar 3: no, en realidad] Además, ningún borde aterriza en el nodo raíz.

Answer 1

¿Se trata de un gráfico dirigido? Lo siguiente se supone no dirigido.

Lo que está buscando es si el borde dado es Bridge en el gráfico. Creo que esto se puede encontrar utilizando un recorrido en busca de ciclos que contengan ese borde y sería O (| V | + | E |).

O (1) es demasiado pedir.

Es posible que le resulte útil buscar mantener los componentes conectados de 2 filos en gráficos dinámicos.

Eppstein et al tienen un papel en esto: http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf

que puede mantener los componentes conectados 2-borde, en un gráfico de n nodos donde se permite inserciones y deleciones de borde. Tiene O (sqrt (n)) tiempo por actualización y O (log n) tiempo por consulta.

De modo que en cualquier momento que elimine, puede consultar en O (logn) para determinar si la cantidad de componentes conectados de 2 bordes ha cambiado. Supongo que también puede indicarle en qué componente se encuentra un nodo específico.

Este documento es más general y se aplica a otros problemas de gráfico, no solo a los 2 componentes conectados por flanco.

Le sugiero que busque puentes y conectividad dinámica de 2 bordes para que pueda comenzar.

Espero que ayude.

Answer 2

Para acelerar un poco más la obvia solución O (| V | + | E |), puede mantener un árbol de expansión que es bastante fácil de actualizar a medida que se cambia el gráfico.

Si se elimina un borde no en el árbol de expansión, el gráfico no se desconecta y no hace nada. Si se elimina un borde en el árbol de expansión, debe intentar encontrar una nueva ruta entre esos dos vértices (si encuentra uno, úselo para actualizar el árbol de expansión, de lo contrario, el gráfico se desconectará).

Entonces, mejor caso O (1), peor caso O (| V | + | E |), pero bastante fácil de implementar de todos modos.

Answer 3

según lo dicho por Moron justo antes, en realidad está buscando un puente en su gráfico.

Ahora un puente es un borde que tiene el atributo descrito y también se origina y termina en Vértices de corte. Cortar vértice es exactamente lo que es un Puente, pero en una edición de vértice (nodo).

De modo que la única forma (aunque basta con doblar la hipótesis de la estructura de datos inicial) de conseguir una complejidad O (1) para esto, es si primero comprueba cada nodo en su gráfico si es un Vértice Cortado y luego simplemente en tiempo constante comprobando si el borde que desea eliminar está atado a uno de esos dos.

Encontrar si un nodo en un gráfico es un Vértice Cortado toma O (m + n) donde m = # bordes yn = # nodos.

Saludos