** Intervals and Derived Graphs**

** Theorem:** There is a unique partition of a program flow graph
into intervals.

After a program graph has been partitioned into intervals, a * derived
graph* * ( I, &Gamma _{ I}) * can be formed as follows:

- Nodes of the derived graph are the intervals of the original graph.
- Transitions of the derived graph are transitions between nodes
of intervals of the original graph.

*&Gamma*_{ I}= { (I_{i}, I_{j}) | &exist x &isin I_{i}&exist y &isin I_{j}(x, y) &isin &Gamma }

where*i &ne j*. Note that a transition can only be to the head node of an interval.

The process of making derived graphs is continued until a single node is
reached. Some graphs are * irreducible*; these are rare in practice
and can be handled by making an artificial duplicate of a node.