Applications of Loop Trees

Abstract

Aims: In a previous paper we have obtained a result which provides a new way to consider structured programs. Any directed graph whatsoever, according to this result, is a dag overlaid by a structured graph, with loops within loops in which no loops overlap. In such a structured graph, the only backward edges go from somewhere in a loop to the head of that loop. Crucial to this result is the construction of what we call a loop tree. As suggested by R. E. Tarjan, we here apply this result to three well-known situations. We also compare our decomposition method to two earlier such methods, one by Tarjan and one, much older, by Luce. Methodology: We use the conventions of classical mathematics, in which sets and functions underlie all structures, such as directed graphs and loop trees, and in which all facts obtained in the course of the work are presented as theorems and lemmas, based on definitions and accompanied by valid proofs. Results: We give a method of solving the single-source path expression problem for a reducible graph by examining its loop tree, which must be unique. We give a necessary and sufficient loop tree condition for a graph to have two edge-disjoint spanning trees, and a necessary and sufficient loop tree condition for a graph to have a feedback vertex. Conclusion: The study of loop trees can be used to clarify many situations in the theory of directed graphs, in addition to the complete classification of directed graphs mentioned above.