Zyklomatische Zahl

Die zyklomatische Zahl ist ein Begriff aus dem mathematischen Teilgebiet der Graphentheorie.

Sei ${\displaystyle G}$ ein Graph. Die Anzahl der Basiselemente einer Zyklenbasis, also die Dimension des Zyklenraumes von ${\displaystyle G}$ heißt zyklomatische Zahl. Sie wird auch Index des Graphen genannt.^[1][2]

• Der Index ist nie negativ und verschwindet genau dann, wenn es sich bei dem Graphen um einen Wald handelt.
• Der Index ist nie größer als die Anzahl der Zyklen des Graphen und ist genau dann gleich dieser Anzahl, wenn es sich um einen Kaktusgraph handelt.
• Die zyklomatische Zahl kann durch die Formel

${\displaystyle \mu (G):=|E(G)|-|V(G)|+\kappa (G)}$

berechnet werden, dabei bezeichnet ${\displaystyle |E(G)|}$ die Anzahl der Kanten (engl. edges), ${\displaystyle |V(G)|}$ die Anzahl der Knoten (engl. vertices) und ${\displaystyle \kappa (G)}$ die Anzahl der Zusammenhangskomponenten des Graphen.^[3]

1. ↑ Peter Tittmann: Graphentheorie. Fachbuchverl. Leipzig im Carl-Hanser-Verl., München 2003, ISBN 3-446-22343-6, S. 134. 
2. ↑ Reinhard Diestel: Graph theory. Springer, Berlin 2010, ISBN 978-3-642-14278-9, S. 23. 
3. ↑ Peter Tittmann: Graphentheorie. Fachbuchverl. Leipzig im Carl-Hanser-Verl., München 2003, ISBN 3-446-22343-6, S. 136.