algorithm - graphs - ¿Cómo detectar si romper un borde hará que un gráfico sea disjunto?

graph representations

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, esta es mi pregunta: cuando se borra un borde, ¿es posible determinar, en tiempo constante (es decir, con un algoritmo O (1)), si esto hace que el gráfico se divida en dos subgrafos disjuntos? Si lo hace, ¿a qué lado del borde pertenece el nodo raíz?

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

Tal vez no sea posible hacerlo en O (1), de ser así, se apreciará cualquier sugerencia a la literatura.

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

Editar 2: OK, 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

¿Es esto un gráfico dirigido? Lo siguiente se supone no dirigido.

Lo que está buscando es si el borde dado es un puente 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 componentes conectados de 2 bordes en gráficos dinámicos.

Eppstein y colaboradores tienen un artículo sobre esto: http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf

que puede mantener componentes conectados de 2 bordes, en un gráfico de n nodos donde se permiten las inserciones y eliminaciones de bordes. Tiene O (sqrt (n)) tiempo por actualización y O (log n) tiempo por consulta.

Por lo tanto, cada vez que lo elimine, puede consultar en O (logn) para determinar si la cantidad de componentes conectados de 2 bordes ha cambiado. Supongo que también puede decirle en qué componente se encuentra un nodo específico.

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

Te sugiero que busques puentes y conectividad dinámica de 2 bordes para que comiences.

Espero que ayude.

Answer 2

Para acelerar un poco las cosas con la obvia solución O (| V | + | E |), podría 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 que no está en el árbol de expansión, entonces 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, el mejor caso O (1), el peor de los casos O (| V | + | E |), pero bastante simple de implementar de todos modos.

Answer 3

como dijo Moron justo antes, en realidad estás buscando un Puente en tu gráfica.

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

Entonces, la única forma (aunque doblando la hipótesis de la estructura de datos inicial) en la que puedo pensar, obtener una complejidad O (1) para esto, es si primero verificas cada nodo en tu gráfico si es un Vértice Cortado y luego simplemente Comprobación de tiempo constante si el borde que desea eliminar está adosado 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.

Aclamaciones