Con seis vértices cualquier representación sirve igual. La
pregunta es qué pasa cuando el grafo crece, y la respuesta se ve mejor
moviendo los controles que leyendo la fórmula. Aquí se comparan las tres
sobre las que se programa: lista de adyacencia, matriz de adyacencia y lista
de aristas.
1. Antes de mover nada
Una red de 100 000 vértices donde cada uno
tiene, en promedio, 4 vecinos. Un computador hace unas cien millones
de operaciones por segundo.
¿Cuántos segundos tarda el recorrido sobre la matriz de adyacencia?
2. Mueva el grafo
1 000
4
Con esos valores, E = 2 000 aristas.
3. Cuánto tarda
Representación
Operaciones
Tiempo
En rojo, lo que pasa de un segundo. Los jueces en línea
suelen dar entre uno y tres.
4. De dónde sale cada término
El costo sobre lista de adyacencia es
$\Theta(V + E)$. ¿Por qué aparece el $V$, si las aristas ya están contadas
en el $E$?
5. Cuándo empatan
¿En qué caso la matriz de adyacencia deja de ser más cara que la lista?
Suba el grado medio hasta acercarlo al número de
vértices y las dos barras se igualan. Ahí la matriz no desperdicia nada,
y además contesta en una sola consulta si existe una arista, cosa que la
lista no puede.
6. Para llevarse
Sin solución aquí. Un problema de juez da
$V \leq 10^5$, $E \leq 2 \cdot 10^5$ y un límite de dos segundos, y pide
responder $Q \leq 10^5$ preguntas del tipo ``¿existe la arista $(u,v)$?''.
Decida qué representación usar, estime las operaciones totales con los
controles de arriba y justifique la decisión. Después cambie el enunciado
a $V \leq 2000$ y vuelva a decidir.