Reduzierbarer und irreduzierbarer Kontrollflussgraph

Die Menge der Kontrollflussgraphen kann in reduzierbare und irreduzierbare Kontrollflussgraphen partitioniert (geteilt) werden. Diese Einteilung geht auf Frances E. Allen zurück. Hecht und Ullman geben äquivalente Charakterisierungen zu Allens ursprünglicher Definition und benutzen diese, um zu zeigen, dass strukturierte Kontrollstrukturen stets reduzierbare Kontrollflussgraphen erzeugen. Eine Auflistung alternativer Charakterisierungen findet sich in einer späteren Veröffentlichung.

Ein für die Definition eines reduzierbaren Kontrollflussgraphen wichtiger Begriff ist der einer Rückwärtskante (engl. backedge). Wenn man im Zuge einer Tiefensuche eines Kontrollflussgraphen $G⟨V,E,r⟩$, die beim Knoten $r$ startet, ausgehend von einem Knoten $u$ entlang der Kante $u\to v$ zu einem Knoten $v$ gelangt, der schon entdeckt worden ist, so nennt man die Kante $u\to v$ Rückwärtskante.

Ein Kontrollflussgraph $G⟨V,E,r⟩$ ist genau dann reduzibel, wenn er eine der folgenden drei (untereinander äquivalenten) Bedingungen erfüllt.

1. Jede Tiefensuche findet dieselbe Menge an Rückwärtskanten.
2. Sei $u\to v$ eine Rückwärtskante. Dann dominiert $v$ den Knoten $u$.
3. $G$ enthält keinen Untergraphen der Form , wobei die eingezeichneten gestrichelten Kanten Pfade repräsentieren.

Nicht reduzierbare Kontrollflussgraphen nennt man irreduzierbar.

Die Unterscheidung in reduzierbare und irreduzierbare Kontrollflussgraphen ist in der Informatik insofern von Interesse, als für reduzierbare Kontrollflussgraphen im Allgemeinen effizientere Algorithmen existieren.