Ejemplos de en donde se pueden aplicar las estructuras de datos Gafo
• Ejemplo 1: Grafo de carreteras entre ciudades.
Problemas que se pueden plantear con el grafo entre ciudades
¿Cuál es el camino más corto de Murcia a Badajoz?
¿Existen caminos entre todos los pares de ciudades?
¿Cuál es la ciudad más lejana a Barcelona?
¿Cuál es la ciudad más céntrica?
¿Cuántos caminos distintos existen de Sevilla a Zaragoza?
¿Cómo hacer un tour entre todas las ciudades en el menor tiempo posible?
• Ejemplo 2: Grafo de transiciones de un AFD (Autómata Finito Determinista).
Problemas que se pueden plantear con el grafo de transiciones de un AFD.
¿La expresión: a b b a b a b b b a, es una expresión válida del lenguaje?
¿Cuál es la expresión válida más corta?
Transformar el grafo en una expresión regular y viceversa.
• Ejemplo 3: Grafo de planificación de tareas.
Problemas que se pueden plantear con el grafo de planificación de tareas.
¿En cuánto tiempo, como mínimo, se puede construir la pirámide?
¿Cuándo debe empezar cada tarea en la planificación óptima?
¿Qué tareas son más críticas (es decir, no pueden sufrir retrasos)?
¿Cuánta gente necesitamos para acabar las obras?