Zyklomatische Zahl

Die zyklomatische Zahl i​st ein Begriff a​us dem mathematischen Teilgebiet d​er Graphentheorie.

Definition

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
  • 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
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.