Un grafo dibujado no le sirve a un programa. Aquí hay que escribir las cuatro representaciones del mismo grafo —matriz de adyacencia, lista de adyacencia, lista de aristas y matriz de incidencia— y comprobarlas por separado. Al final, las cuatro lado a lado con lo que ocupa cada una.
Haga clic en una celda para poner o quitar un uno. La fila es el origen y la columna el destino.
Escriba, para cada vértice, los vecinos separados por comas. El orden dentro de la lista no cambia el grafo, pero sí el orden en que un recorrido lo visita.
Sin solución aquí.
El producto de la incidencia por su transpuesta. Sea B la matriz de incidencia de H1 y BT su transpuesta. Calcule B · BT, que es de V × V, y diga qué hay en la diagonal y qué hay fuera de ella. Compare el resultado con la matriz de adyacencia. Es el Ejercicio 22.1-7 de CLRS, planteado allá para grafos dirigidos.
Las seis conversiones. Entre lista de adyacencia, matriz de adyacencia y lista de aristas hay seis conversiones posibles. Escriba las funciones y diga, para cada una, cuánto cuesta en términos de $V$ y $E$. Hay una que no puede costar menos de $\Theta(V^2)$ pase lo que pase: encuéntrela y explique por qué.
Cuándo cambiar de representación. Un problema entrega el grafo como lista de aristas y el algoritmo que hay que correr hace un recorrido completo. ¿Conviene convertir a lista de adyacencia primero, o trabajar directamente sobre la lista de aristas? Compare $\Theta(V+E)$ de convertir más $\Theta(V+E)$ de recorrer, contra $\Theta(V \cdot E)$ de recorrer sin convertir.