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]

Sei G ein Graph. Die Anzahl der Basiselemente einer Zyklenbasis, also die Dimension den Zyklenraumes von G heißt zyklomatische Zahl.[1][2]

Eigenschaften[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
\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.[3]

Einzelnachweise[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.