Zyklomatische Zahl

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]