operación inversa para "Unir y encontrar"

Sabemos que hay "unión y búsqueda" para conjuntos disjuntos. http://en.wikipedia.org/wiki/Union_find operación inversa para "Unir y encontrar"

¿Pero cómo hacer la operación inversa? Considere un conjunto con N nodos conectados con bordes E (que de hecho es un gráfico). Y en cada paso queremos eliminar algunos bordes y verificar si esta operación de eliminación lleva a tener otro conjunto disjunto. ¿Es posible hacerlo rápidamente como en "Union and find"?

P.S esto no es tarea, tenemos vacaciones :)

Fuente

2011-06-22 Spinach

Esto se conoce como el problema de decapado de los bordes en línea o problema de conectividad en línea. Algunos enlaces a algoritmos están en este section of the Wikipedia article on graph connectivity.

Fuente

2011-06-22 10:24:52

Gracias por el enlace. Solo puedo encontrar artículos para comprar en ACM. ¿No se pudo encontrar información sobre TopCoder, ningún enlace directo? :) – Spinach

¿Entonces su pregunta es cómo detectar eficientemente un Bridge? Esto se puede hacer en tiempo lineal (también vea el enlace).

Fuente

2011-06-22 10:25:43 dcn

Dado que @Chris aparentemente quiere hacer la operación repetidamente (dice "en cada paso") podemos ser más eficientes que la detección de puentes en cada etapa. – borrible

creo que si ejecuta ese algoritmo de búsqueda de puentes y marca los puentes y observa que a menos que se agregue un borde a un gráfico, no pueden aparecer nuevos puentes; todos los puentes que existen en ese gráfico permanecen como puentes a medida que se eliminan los bordes y los nuevos puentes solo pueden aparecer si elimina un borde que no es un puente; por lo que solo tiene que volver a ejecutar el algoritmo en los dos subgrafos que estaban conectados por un borde que no sea puente que se acaba de quitar. –

Union-find se usa en el algoritmo de Kruskal, que agrega repetidamente el borde del peso mínimo que no hace un ciclo. Una idea inversa: eliminar los bordes del peso máximo, siempre que no desconecte el gráfico, se usa en reverse-delete algorithm, que aparentemente puede hacer uso de una estructura de datos complicada (ver Wikipedia).

Fuente

2011-06-22 11:29:03 sdcvvc

Siguiente buen enlace, pero demasiado generalizado y no hay código para ver :( – Spinach

operación inversa para "Unir y encontrar"

Respuesta

Cuestiones relacionadas