En teoría de grafos matemáticas , una región de entrada única y salida única (SESE) en un gráfico dado es un par de aristas ordenado.
Por ejemplo, con el par de aristas ordenado, ( a , b ) de aristas de flujo de control distintas a y b donde:
- a domina b
- b posdomina a
- Todo ciclo que contiene a también contiene b y viceversa.
donde se dice que un nodo x domina el nodo y en un gráfico dirigido si cada camino desde el inicio hasta y incluye x . Se dice que un nodo x posdomina un nodo y si cada camino desde y hasta el final incluye x .
Entonces, a y b se refieren a los bordes de entrada y salida, respectivamente.
- La primera condición garantiza que cada ruta desde el inicio hasta la región pase por el borde de entrada de la región, a .
- La segunda condición garantiza que cada camino desde el interior de la región hasta el final pase por el borde de salida de la región, b .
- Las dos primeras condiciones son necesarias pero no suficientes para caracterizar las regiones SESE: dado que los backedges no alteran las relaciones de dominancia o posdominancia, las dos primeras condiciones por sí solas no prohíben que los backedges entren o salgan de la región.
- La tercera condición codifica dos restricciones: cada camino desde el interior de la región hasta un punto 'arriba' a pasa por b , y cada camino desde un punto 'debajo' b hasta un punto dentro de la región pasa por a . [1]
Referencias
- ^ El árbol de estructura del programa: calcular regiones de control en tiempo lineal
