← Volver a los ejercicios

V + E contra V²

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ónOperacionesTiempo
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.