Agregar un nuevo borde para graficar y encontrar un nuevo árbol de expansión en O (n)

Supongamos que se nos da el árbol de expansión mínimo T de un gráfico dado G (con n vértices y m bordes) y un nuevo borde e = (u, v) de peso w que agregaremos a G. Proporcione un algoritmo eficiente para encontrar el árbol de expansión mínimo del gráfico G + e. Su algoritmo debe ejecutarse en O (n) tiempo para recibir crédito completo.Agregar un nuevo borde para graficar y encontrar un nuevo árbol de expansión en O (n)

inicio Prim o de Kruskal ALG de u o v hasta llegar a un fragmento de la ruta del árbol de expansión dado? Parece que el nuevo árbol de expansión no cambiará mucho desde un nuevo borde.

Fuente

2011-01-26 yetanothercoder

Dado que este es un problema de tarea, ¿puede explicar más específicamente lo desea ayuda? Este es un gran problema, pero no solo vamos a darte la respuesta. – templatetypedef

Determine la ruta entre los puntos finales del nuevo borde en G. Si el borde de longitud máxima en esa ruta es mayor que el del borde nuevo, reemplácelo con el nuevo borde. Esto se ejecuta en O (N) tiempo.

Fuente: Trail Maintenance IOI 2003

Fuente

2011-01-26 20:22:48 marcog

Respuesta perfecta para una pregunta que no es para la tarea. Pero es una pregunta de tarea, entonces -1. –

+16

@j_random_hacker - Algunas personas sienten curiosidad por saber por qué votó negativamente: vea [esta pregunta en Meta] (http://meta.stackexchange.com/questions/76694). ¿Qué debería decir Marcog para hacer de esta una mejor respuesta a una pregunta de tarea? – ChrisW

¡Guau! No esperaba crear tanta controversia. Gracias @ChrisW por el puntero. Trataré de explicar mi posición sobre esa pregunta de Meta (que creo que es un gran ejemplo de una pregunta de Meta, por cierto). –

Agregar un nuevo borde para graficar y encontrar un nuevo árbol de expansión en O (n)

Respuesta

Cuestiones relacionadas