Reduzierbarer und irreduzierbarer Kontrollflussgraph

Die Menge der Kontrollflussgraphen kann in reduzierbare und irreduzierbare Kontrollflussgraphen partitioniert (geteilt) werden.

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\langle V,E,r\rangle$, 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.

Für einen reduzierbaren Kontrollflussgraphen $G\langle V,E,r\rangle$ gilt eine der folgenden drei (untereinander äquivalenten) Bedingungen.

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 den verbotenen Untergraphen , 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.