Direkt zum Inhalt

Lexikon der Mathematik: zyklomatische Zahl

Begriff aus der Graphentheorie.

Die zyklomatische Zahl μ(G) eines Graphen G wird definiert durch \begin{eqnarray}\mu \text{(}G)\text{=|}K\text{(}G)\text{|}-\text{|}E\text{(}G)\text{|+}\eta \text{(}G\text{),}\end{eqnarray} wobei η(G) die Anzahl der Zusammenhangskomponenten von G (zusammenhängender Graph) bedeutet.

Für jeden Graphen G ist μ(G) ≥ 0, und es gilt genau dann μ(G) = 0, wenn G ein Wald ist.

D. König hat 1936 gezeigt daß 2μ(G) mit der Anzahl der geraden Faktoren in einem numerierten Graphen G übereinstimmt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos