La definición de un puente e = (v, w) es que G ‘= G – e tiene un componente conectado más que G.
En aras de la simplicidad, voy a escribir una prueba asumiendo que G está conectado, y solo vamos a analizar el caso en el que estamos creando dos componentes. El caso general se deriva fácilmente de esto.
Por lo tanto, suponga que construye un árbol de expansión T de G de modo que e no esté en T. Dado que T es un árbol de expansión, existe una ruta única de v a w utilizando bordes solo en T, llámelo P.
- ¿Cómo se puede ser bueno para resolver problemas de algoritmos / programación? Soy un principiante, y me sugirieron que leyera el libro CLRS para aprender sobre algoritmos.
- Como principiante, ¿debería leer el libro CLRS antes de comenzar con Interviewbit?
- ¿Qué idioma debo aprender para el comercio de algoritmos?
- ¿Cuál es la diferencia principal entre algoritmo y pseudocódigo?
- ¿Qué es la compresión de datos en la base de datos?
Sabemos que P es así: v, p_1, …, p_r, p_ {r + 1}, …, p_t, w. Es decir, P comienza en v, termina en w y pasa por los nodos p_k para k en 1 a t. En algún punto de P (llamado (p_r, p_ {r + 1})), cruzamos desde el componente conectado en G ‘en el que v estaba, hasta el componente conectado en el que estaba w.
Esto significa que el borde de p_r a p_ {r + 1} conecta los dos componentes de G ‘. Por lo tanto, originalmente teníamos otra forma de conectar estos dos componentes, lo que significa que G ‘no tiene dos componentes conectados y, por lo tanto, e no es un puente.
