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

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

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

(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.