4.3.4. Algoritmos sobre grafos dirigidos.
Grafos dirigidos acíclicos
Definición: un grafo dirigido acíclico (GDA) es un grafo dirigido y sin ciclos.
Ejemplos: estructura de directorios (con posibilidad de enlaces simbólicos), representación de expresiones aritméticas (con subexpresiones comunes), prerrequisitos para realizar un curso, grafo de actividades para planificación de tareas.
Representación de órdenes parciales. Un orden parcial en un conjunto S es una relación binaria que cumple:
- Para cualquier elemento a de S, (a R a) es falso.
- Para cualquier a, b, c de S, si (a R b) y (b R c) entonces (a R c).
Ejemplo. La relación de inclusión propia entre conjuntos (?).