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

Материал из WEGA
Перейти к навигации Перейти к поиску

Управляющий граф (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], выходит одна или две дуги.

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

См. также

Литература

  • Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
  • Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.
  • Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.