Одинарный вход-один выход

В математической теории графов область с одним входом и одним выходом (SESE) в данном графе представляет собой упорядоченную пару ребер.

Например, с упорядоченной парой ребер ( a , b ) различных потока управления ребер a и b , где:

1. а доминирует б
   
2. б постдоминирует а
   
3. Каждый цикл, содержащий a, также содержит b и наоборот.

где узел x считается доминирующим узлом y в ориентированном графе , если каждый путь от начала до y включает x . узел x Говорят, что постдоминирует над узлом y , если каждый путь от y до конца включает x .

Итак, a и b относятся к входному и выходному краю соответственно.

• Первое условие гарантирует, что каждый путь от начала в регион проходит через входной край региона, a .
• Второе условие гарантирует, что каждый путь изнутри региона до конца проходит через выходной край региона b .
• Первые два условия необходимы, но недостаточны для характеристики регионов SESE: поскольку бэкэджи не меняют отношений доминирования или постдоминирования, сами по себе первые два условия не запрещают бэкэджам входить в регион или выходить из него.
• Третье условие кодирует два ограничения: каждый путь изнутри региона к точке «над» a, проходящий через b , и каждый путь из точки «ниже» b к точке внутри региона проходит через a .