CONJUNTOS PO; ORDENACION TOPOLOGICA

Suponga que S es un grafo tal que cada nodo v_i de S representa una tarea y cada arista (u,v) significa que la finalización de la tarea u es un prerrequisito para que comience la tarea u. suponga que tal grafo S contiene un ciclo tal que

P=(u,v,w,u)

Esto significa que no podemos empezar u hasta completar w. así no podemos completar ninguna tarea del ciclo. Por tanto, grafo S  así, que representa tareas y relaciones de procedencia, no puede tener ciclos.

Si S es un grafo sin ciclos. Considere la relación < sobre S definida como sigue:

u       si existe un camino de u a v.

esta relación tiene las tres propiedades  siguientes:

(1)  para cada elemento u de S, tenemos que u

(2)  si u

(3)  Si u

Tal relación < sobre S se llama relación parcial de S, y S con tal relación se llama conjunto parcialmente ordenado o conjunto po. Así un grafo S sin ciclos se puede considerar un conjunto parcialmente ordenado.

Por otro lado suponga que S es un conjunto parcialmente ordenado con la ordenación parcial denotado por <. Entonces S se puede considerar un grafo cuyos nodos son los elemente de S y cuyas aristas están definidas como sigue:

( u,v)       es una arista en S si        u

Un conjunto S parcialmente ordenado, considerado como un grafo