Ayudantía Grafos EDD

Ayudantía Grafos ­ Estructura de Datos  
1) Dado el siguiente grafo: 
 

 
a) Dar su representación de matriz de adyacencia. 
b) Dar su representación de listas de adyacencia c)Mostrar 1 camino simple de longitud 9, un camino cerrado de longitud 11 
d)Mostrar tres subgrafos distintos basados en el conjunto de vértices {v1,v2,v3,v4,v5,v6,v7,v8}. Para cada subgrafo, indique la cantidad de componentes conexas que tiene. 
e)Mostrar  tres  subgrafos  distintos basados  en  el  conjunto  de vértices {v1,v2,v3,v4,v5,v6,v7,v8}. Para cada subgrafo, indique la cantidad de componentes conexas que tiene. 
f ) Mostrar un recorrido en profundidad del grafo, comenzando desde el nodo v1, y un 
recorrido en amplitud comenzando desde el nodo v4. Mostrar en ambos casos el ´arbol resultante del recorrido. 
g) Muestre, de ser posible, 3 ciclos distintos de largo 6. Con ciclos distintos nos referimos a que si consideramos los ciclos de a pares, hay al menos un v´ertice de un ciclo que no 
est´a en el otro. 
h) Muestre la máxima cantidad de ciclos distintos de largo 7 que encuentre. 
i) ¿De qué longitud es el ciclo más largo que puede encontrar en el grafo dado? 
 
2)  Suponga  el  subgrafo G0  de  G  definido sobre  los vértices V0 = {v1, v3, v4, v6,  v7, v8, v9},  y que contiene todas las 
aristas definidas en G sobre dichos vértices, y asumiendo la siguiente asignación de pesos: 
 w(v1, v3) = 2; w(v3, v6) = 3; w(v6, v7) = 4; w(v4, v7) = 1; w(v8, v9) = 3; w(v7, v8) = 4 
w(v3, v4) = 4; w(v7, v9) = 4; w(v4, v8) = 3; w(v1, v4) = 3; w(v6, v9) = 4. 
 
Mostrar  el   árbol recubridor  mínimo  para  dicho  subgrafo  G0  obtenido  usando  el  algoritmo  de  Kruskal  (sólo  el  árbol 
final).  Marque  en  qué  orden  fue  agregado  cada  arco  del  árbol  obtenido  (es decir,  cuál  fue  el  primer  arco,   cuál  el  
segundo, y así  siguiendo). Muestre también el costo del árbol obtenido. 
 
3)  Suponga  que  un  grafo  G ...