Grafos dirigidos y problemas que se resuelven con grafos
Lee grafos dirigidos, cuenta los apretones de manos y los partidos de una liga, y halla la ruta más corta convirtiendo el problema en un grafo.
📖 Empieza aquí: lee los pasos de la «Lección» por orden (1, 2, 3 …) y responde a cada pregunta. Después sigue con «Práctica».
- Rusia: 7.º curso
Guía
Los grafos no forman parte del currículo habitual de Primaria ni de ESO en España: este taller es una ampliación. Un grafo es un modelo muy cómodo: los vértices son personas, pueblos o equipos, y las aristas son relaciones (amistad, carreteras, partidos). Si la relación tiene un sentido («A adelantó a B»), la arista se dibuja con una flecha: es un grafo dirigido. Cada vértice tiene entonces un número de flechas que salen y otro de flechas que llegan.
Problemas clásicos: los apretones de manos en un grupo de n personas (todos con todos, una vez) y los partidos de una liga (cada equipo juega contra todos los demás). La suma de los grados es el doble del número de aristas; por eso las aristas son la mitad de la suma de los grados, y con n vértices unidos todos entre sí salen n·(n − 1) : 2.
Un error frecuente es contar cada arista dos veces. Otro es confundir las flechas que salen con las que llegan. Un problema de rutas se resuelve contando las aristas de el camino más corto.