Zyklomatische Zahl

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

Definition

Sei $G$ ein Graph. Die Anzahl der Basiselemente einer Zyklenbasis, also die Dimension des Zyklenraumes von $G$ heißt zyklomatische Zahl. Sie wird auch Index des Graphen genannt.

Eigenschaften

• 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

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

berechnet werden, dabei bezeichnet $|E(G)|$ die Anzahl der Kanten (engl. edges), $|V(G)|$ die Anzahl der Knoten (engl. vertices) und $\kappa (G)$ die Anzahl der Zusammenhangskomponenten des Graphen.