Primer Parcial 21/10/2006 (Algoritmos III)

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


1)
2)
a)Sea v un vertice de corte. Sup. que es hoja de un AG de G. Entonces dA(v)=1. Como v es vertice de corte, es el unico conecta a dos componentes conexas, con lo cual el arbol necesita pasar por ese vertice para cubrirlos todos, entonces dA(v) es al menos 2. Pero por HI dA(v)=1 -> ABS
b)Por el punto a) se sabe que todo vertice de corte no puede ser hoja de un AG, con lo cual como todo grafo conexo tiene AG, y todo arbol tiene al menos 2 hojas -> todo grafo conexo tiene vertices no de corte. Para obtener ese vertice, entonces, por ej. puede construirse un AGM mediante el algoritmo de Prim y devolver alguna de las hojas.


3) (Revisar)
Por induccion en n:

  • CB n=2

o o y o-o son los unicos grafos posibles con 2 vertices. Ambos estan en R y puede verse que en ambos casos G y H son isomorfos <=> G=H, con lo cual D(G)=D(H)

  • PI

Sup. que vale HI para todo grafo de n vertices. Sean v,w dos vertices, y tomemos G'=G-v y H'=H-w. Como G,H estan en R -> los vertices de un mismo grado son (o no) adyacentes de par en par. Entonces al sacar un vertice, se disminuye el grado de todos sus adyacentes en 1, con lo cual siguen estando en R.
(...)


4)
a) Se puede modelar con camino minimo entre A y B, tomando los pueblos como vertices, los tramos como ejes y los peajes como pesos. Para resolverlo se puede usar Dijkstra ya que solo se necesita saber el camino minimo de un vertice a otro (no todos como los alg. matriciales) y ademas tiene mejor complejidad que el alg. de Ford.
b) En este caso se puede utilizar BFS, que asumiendo listas de adyacencias puede tener complejidad O(n+m)
c)