Zyklomatische Zahl

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

Definition

Sei <math>G</math> ein Graph. Die Anzahl der Basiselemente einer Zyklenbasis, also die Dimension des Zyklenraumes von <math>G</math> heißt zyklomatische Zahl. Sie wird auch Index des Graphen genannt.<ref>Peter Tittmann: Graphentheorie. Fachbuchverl. Leipzig im Carl-Hanser-Verl., München 2003, ISBN 3-446-22343-6, S. 134. </ref><ref>Reinhard Diestel: Graph theory. Springer, Berlin 2010, ISBN 978-3-642-14278-9, S. 23. </ref>

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

<math>\mu (G):=|E(G)|-|V(G)|+\kappa (G)</math>

berechnet werden, dabei bezeichnet <math>|E(G)|</math> die Anzahl der Kanten (engl. edges), <math>|V(G)|</math> die Anzahl der Knoten (engl. vertices) und <math>\kappa (G)</math> die Anzahl der Zusammenhangskomponenten des Graphen.<ref>Peter Tittmann: Graphentheorie. Fachbuchverl. Leipzig im Carl-Hanser-Verl., München 2003, ISBN 3-446-22343-6, S. 136.</ref>

Einzelnachweise