Zyklomatische Zahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Definition[Bearbeiten | Quelltext bearbeiten]

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

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  • 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
berechnet werden, dabei bezeichnet die Anzahl der Kanten (engl. edges), die Anzahl der Knoten (engl. vertices) und die Anzahl der Zusammenhangskomponenten des Graphen.[3]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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.