← Volver a los ejercicios

Las cuatro representaciones, a mano

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.

1. El grafo y una cuenta previa

Grafo:
¿Cuántas entradas suman, en total, las listas de adyacencia?
Representaciones correctas: 0 de 4

2. Matriz de adyacencia

Haga clic en una celda para poner o quitar un uno. La fila es el origen y la columna el destino.

3. Lista de adyacencia

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.

4. Lista de aristas

Sirve cualquier separador: paréntesis, comas, guiones o espacios. Lo que se lee son los números, de dos en dos.

5. Matriz de incidencia

Las columnas van en el mismo orden de la lista de aristas de arriba, y el encabezado de cada una dice a qué arista corresponde.

6. Las cuatro, lado a lado

Aparece cuando las cuatro estén correctas.

7. Para llevarse

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.