Regularizable graph

Regularizable graph --- регуляризуемый граф.

1. A graph [math]\displaystyle{ G = (V,E) }[/math] is mathcalled regularizable (Berge), if for each edge [math]\displaystyle{ e \in E }[/math] there is a positive integer [math]\displaystyle{ m(e) }[/math] such that the multigraph which arises from [math]\displaystyle{ G }[/math] by replacing every edge [math]\displaystyle{ e }[/math] by [math]\displaystyle{ m(e) }[/math] parallel edges is a regular graph.

2. A cf-graph [math]\displaystyle{ G }[/math] is called a regularizable graph (or generalized reducible) (Kasyanov), if there is a sequence of cf-graphs [math]\displaystyle{ G_0 }[/math], [math]\displaystyle{ G_1 }[/math], [math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ G_r }[/math] such that [math]\displaystyle{ G_0=G }[/math], [math]\displaystyle{ G_r }[/math] is trivial, and for all [math]\displaystyle{ i }[/math], [math]\displaystyle{ 0\lt i\leq r }[/math], graph [math]\displaystyle{ G_i }[/math] is obtained from [math]\displaystyle{ G_{i-1} }[/math] by reduction of a nonempty set of nontrivial disjoint intervals into nodes.

Many problems on program development and processing are significantly simplified if programs have a regular structure and admit a representation in the form of a nested fragments of a special form. For example, structured programming consider various types of statement composition as basic ones, but all of them are intervals. When allowing any intervals to be considered as basic ones, we get the class of programs with regularizable cf-graphs.

Control flow graphs of programs that occur in practice frequently fall into the class of regularizable graphs. Exclusive use of structured flow-of-control statements, such as if-then-else, while-do, continue, and break statements, produces programs whose flow graphs are always regularizable. Even programs written using goto statements by programmers with no prior knowledge of structured program design are almost always regularizable. Moreover, any program can be transformed via splitting statements to the equivalent one with a regularizable cf-graph.

Theorem. The following properties of a cf-graph [math]\displaystyle{ G }[/math] are equivalent: (1) [math]\displaystyle{ G }[/math] is a regularizable graph, (2) [math]\displaystyle{ G }[/math] is a reducible graph, (3) [math]\displaystyle{ G }[/math] is an arrangeable graph, (4) [math]\displaystyle{ G }[/math] is a collapsible graph,(5) [math]\displaystyle{ G }[/math] is a single-entry graph, (6) [math]\displaystyle{ G }[/math] has no forbidden subgraph, (7) [math]\displaystyle{ G }[/math] has a single dag.