Управляющий граф

Управляющий граф (Control flow graph, Flow graph) --- основная модель программы, представляющая в виде орграфа поток управления (систему управляющих связей) в программе; в ней сохраняется только членение программы на операторы (команды, лучи), а также информация о тождественности операторов и возможных передачах управления между операторами.

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

Обычно считается, что управляющий граф является правильным и не содержит кратных дуг, вершин с совпадающими пометками и разных конечных вершин, т.е. управляющий граф --- это орграф с выделенными начальной [math]\displaystyle{ s }[/math] и конечной [math]\displaystyle{ t }[/math] вершинами, каждая вершина которого лежит хотя бы на одном [math]\displaystyle{ s-t }[/math]-пути.

Часто без ограничения общности можно считать, что из [math]\displaystyle{ t }[/math] не выходит и в [math]\displaystyle{ s }[/math] не заходит ни одна дуга управляющего графа, а из каждой вершины, отличной от [math]\displaystyle{ t }[/math], выходит одна или две дуги.

Другие названия --- Граф переходов, Уграф, Схема Мартынюка.

См. также

Альт, Аранжировка, Аранжируемый граф, Базисная нумерация, Гамак, Гамачное представление, Достоверные отношения частоты выполнения, Зона, Зонно-интервальное представление, Иерархия вложенных альтов, Иерархия вложенных зон, Интервал, Каркас уграфа, Крупноблочная схема программы, Линейная компонента, Линейный участок, Непосредственный обязательный преемник, Одновходовый уграф, Разборный граф, Регуляризуемый уграф, Сводимый управляющий граф, Стандартные схемы, Схемы программ, Участок повторяемости, Фактор-уграф, Фрагмент, Циклический участок

Литература

[Касьянов/88], [Ершов/77], [Евстигнеев/85], [Касьянов/86]