Zyklomatische Zahl
# 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.
