Просмотр кода страницы Factor-control-flow-graph

'''Factor-control-flow-graph''' --- фактор-уграф.

Let <math>R</math> be a set of alts of a cf-graph <math>G</math> such that every node of <math>G</math>
belongs to a single alt from <math>R</math>, i.e. <math>R</math> forms a partition of <math>V(G)</math>.

The cf-graph <math>G'</math> in which <math>V(G')=R</math> is said to be '''obtained by reduction of alts'''
<math>R</math> '''into nodes''' (notation <math>G'=R(G)</math>) if the following properties hold:

(1) for any <math>C_1,C_2\in R</math>, <math>(C_1,C_2)\in A(G')</math> if and only if there are <math>p_1\in C_1</math> and <math>p_2\in C_2</math>
such that <math>(p_1,p_2)\in A(G)</math>,

(2) <math>C\in R</math> is the initial node of <math>G'</math> if and only if <math>C</math> contains the initial node of <math>G</math>,

(3) <math>C\in R</math> is the terminal node of <math>G'</math> if and only if <math>C</math> contains the terminal node of <math>G</math>.

The cf-graph <math>G'</math> is called a '''factor-control-flow-graph''' (or '''factor-cf-graph''') of the cf-graph <math>G</math> with
respect to <math>R</math>.

Let <math>R</math> be a set of mutually disjoint alts of a cf-graph <math>G</math> that form a partitation
of some subset <math>Y\subset V(G)</math>.
Then <math>R(G)</math> is defined as cf-graph <math>R'(G)</math>, where <math>R'=R\bigcup \{ \{p\}: p\in V(G)\setminus Y\}</math>.

[[Категория: Сводимые и регуляризуемые графы]]