Циклический участок

Циклический участок (Loop region) - конструкция, позволяющая на основе анализа уграфа с $n$ вершинами и $m$ дугами за время $O(nm)$ выявлять циклическую структуру алгоритма и находить отношения частот выполнения между всеми подмножествами его элементов, которые не противоречат достоверным отношениям частот выполнения, если уграф $G$ алгоритма является регуляризуемым.

Пусть $G_0=G,G_1,\dots ,G_r$ - такая последовательность уграфов, в которой только $G_r$ не содержит нетривиальных бикомпонент, и для любого $i$ уграф $G_i$ получается из $G_{i-1}$ удалением в каждой нетривиальной бикомпоненте $C$ уграфа $G_{i-1}$ всех дуг, заходящих в один из ее входов. Эту входную вершину бикомпоненты $C$ называют ее головой, а удаленные дуги - дугами повторения уровня $i$. Пусть $I_i$ обозначает множество всех дуг повторения уровня $i$. Части схемы $G$, называемые ее циклическими участками, определяются по следующим двум правилам:

1) Циклический участок нулевого уровня в уграфе $G$ один; он состоит из всех тех вершин и дуг, которые принадлежат путям по $G_r$ от $p_0$ к $q_0$, и имеет головой вершину $p_0$;

2) пусть для некоторого $i$, $i>0$, $C$ - бикомпонента схемы $G_{i-1}$ с головой $p$, тогда в $G$ имеется циклический участок уровня $i$ с головой $p$; он состоит из всех тех вершин и дуг, из которых достижима $p$ в графе, полученном из $C$ удалением всех дуг повторения уровня $j>i$.

См. также

Участок повторяемости.

Литература

[Касьянов/88]