Grafos: puntos, líneas y lo que significan
Un grafo son puntos unidos por líneas, y el mismo dibujo puede describir amistades, carreteras o un orden de compilación.
Un grafo son dos cosas: un conjunto de nodos (los puntos) y un conjunto de aristas (las líneas que los unen). Esa es toda la definición. Su fuerza viene de lo que decidas que significan los puntos y las líneas, porque así una sola estructura responde preguntas sobre amistades, ciudades, computadoras y tareas a la vez.
Nodos y aristas — qué puede significar el mismo dibujo: personas - nodo = persona, arista = «es amigo de» familia - nodo = persona, arista = «es el padre o la madre de» mapas - nodo = ciudad, arista = carretera entre ellas redes - nodo = ordenador, arista = cable o enlace Wi-Fi montaje - nodo = tarea, arista = «debe ir después de» Arista dirigida: A -> B no es lo mismo que B -> A. «es el padre o la madre de» es dirigida. «es amigo de» no lo es.
Un árbol es un grafo sin ciclos: entre dos nodos cualesquiera lleva exactamente un camino, y siempre hay un nodo al que puedes llamar raíz. Las estructuras de carpetas, los árboles genealógicos y los torneos de eliminación directa son árboles. En cuanto un camino puede volver a donde empezó, ya no es un árbol.
Práctica
Relaciona cada situación con lo que significan un nodo y una arista dentro de ella.
Pistas
- Pregúntate qué significa un solo paso entre dos elementos en cada situación.
- En una lista de construcción, la flecha dice qué debe ocurrir antes, no qué se parece.
13 XP
Puedes ir de Tom a Ana, luego de Ana a Lena, y también directamente de Lena de vuelta a Tom. ¿Qué es este grafo?
Pistas
- Un árbol no tiene ningún ciclo: si puedes caminar en círculo, no es un árbol.
- En una familia, subes hasta un padre común y luego vuelves a bajar.
14 XP
Dibuja el grafo de compilación: la base de datos debe estar lista antes que el servidor de API, la caché debe estar lista antes que el servidor de API, y el frontend debe estar listo antes que el servidor de API. Solo después del servidor de API el sitio sale en vivo.
Pistas
- Dibuja una flecha por cada regla de "debe estar terminado antes" que aparezca en la descripción.
- La máquina de la que todo depende se encuentra entre esas tres y el paso final.
18 XP