La pregunta es una sola: cuántos vecinos tiene cada
vértice de H1, es decir la secuencia de grados. Cambia la representación
sobre la que se contesta, y con ella el número de operaciones. El contador
que aparece al lado de cada línea lleva la cuenta.
1. Escoja la representación y prediga
Contestar sobre:
¿Cuántas veces se ejecuta la línea 5?
H1 tiene 6 vértices y 7 aristas. Las cuatro versiones
devuelven lo mismo: [2, 2, 4, 2, 2, 2].
2. Ejecute y mire los contadores
g = –
Paso 0 de 0
El número redondo a la derecha de cada línea cuenta
cuántas veces se ha ejecutado.
3. Las cuatro cuentas
Representación
Ejecuciones
En términos de V y E
Cada fila se llena cuando acierte la predicción de esa
representación.
4. Entonces, ¿cuál es la mejor?
5. Cuándo pesa de verdad
¿En qué grafos la diferencia entre V + E y V² se vuelve decisiva?
Las redes que llegan de un problema real —viales,
sociales, de dependencias— son ralas: cada vértice tiene unos pocos
vecinos, sin importar cuántos vértices haya. Ahí la matriz guarda casi
solo ceros y el recorrido los suma todos.
6. Para llevarse
Sin solución aquí. Escriba las cuatro versiones de
una pregunta distinta: ¿cuántos vértices aislados tiene el grafo?
Cuente las operaciones de cada una sobre H1 y diga cuál gana. Después
responda por qué esa pregunta ordena las cuatro representaciones igual que
los grados, y qué pregunta tendría que hacerse para que ganara la
matriz de adyacencia.