Primer Parcial 22/07/2005 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia


1)
2)
a) Sea G un grafo con k comp. conexas. Sea e el eje que se elimina. Si e es puente, entonces era el unico que unia 2 comp. conexas, con lo cual al sacarlo se desconectaran solo esas dos -> se tienen k+1 comp. conexas. En cambio, si no es puente -> forma parte de un circuito, con lo cual si se saca e sigue habiendo un camino entre los vertices que lo componen, entonces no se desconecta G -> se tienen k comp. conexas.
Si G es un arbol -> es minimalmente conexo, con lo cual sacando cualquier eje se obtienen k+1 comp. conexas.
b) Sea G un grafo con k comp. conexas. Sea e el eje que se agrega. Entonces ese eje se puede agregar dentro de una comp. conexa (siguen quedando k comp. conexas) o podria conectar dos comp. conexas formando una sola (quedan k-1 comp. conexas).
Si e conecta dos comp. conexas -> siempre quedan k-1 comp. conexas


3)
4)
5)