En la teoría de grafos de matemáticas , una región de entrada única y salida única (SESE) en un grafo dado es un par de aristas ordenadas.
Por ejemplo, con el par de aristas ordenadas, ( 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 al nodo y en un grafo dirigido si cada camino desde el inicio hasta y incluye a x . Se dice que un nodo x posdomina a un nodo y si cada camino desde y hasta el final incluye a x .
Entonces, a y b se refieren al borde 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 asegura 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 bordes posteriores no alteran las relaciones de dominancia o postdominancia, las dos primeras condiciones por sí solas no prohíben que los bordes posteriores entren o salgan de la región.
- La tercera condición codifica dos restricciones: cada camino desde dentro de la región a un punto 'encima' de a pasa por b , y cada camino desde un punto 'debajo' de b a un punto dentro de la región pasa por a . [1]
Referencias
- ^ El árbol de estructura del programa: cálculo de regiones de control en tiempo lineal
