Каркас уграфа

Материал из WikiGrapp
Перейти к:навигация, поиск

Каркас уграфа (DAG of control flow graph) — такой уграф K, что Kациклический остов уграфа G, каркасом которого он является, и добавление в K еще одной любой дуги G нарушает ацикличность K.

DAG of control flow graph.png

Справедливы следующие свойства:

(1) Для любого простого пути P по G от ее начальной вершины p_0 существует такой каркас K уграфа G, что P является путем по K.

(2) Каркас любого аранжируемого уграфа G может быть получен из G удалением всех дуг назад.

(3) Уграф G является регуляризуемым тогда и только тогда, когда имеет единственный каркас.

(4) Уграф G является регуляризуемым тогда и только тогда, когда существует такое разбиение множества его дуг U на два подмножества U_1 и U_2, что U_1 образует каркас уграфа, а для любой дуги (p, q)\in U_2 вершина q обязательно предшествует вершине p в G.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.