← Volver a los ejercicios

La misma pregunta, cuatro costos

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