Direkt zum Inhalt

Lexikon der Mathematik: Zyklenraum

Begriff aus der Graphentheorie.

Ein Zyklenraum ist ein Untervektorraum des Kantenraumes, der von den Kantenmengen der Kreise in einem Graphen erzeugt wird.

Ist G einGraph, so bildet die Menge aller Teilmengen von K(G) zusammen mit der symmetrischen Differenz als Verknüpfung “+” (also \begin{eqnarray}{K}_{1}+{K}_{2}=({K}_{1}\backslash {K}_{2})\cup ({K}_{2}\backslash {K}_{1})\end{eqnarray} für K1, K2K(G)) eine abelsche Gruppe, die wirals einen Vektorraum, den sogenannten Kantenraum \begin{eqnarray}{\mathscr{K}}\end{eqnarray}(G) von G, über dem Körper \begin{eqnarray}\mathbb{F}\end{eqnarray}2 = {0, 1} (mit 1K = K und 0K = \begin{eqnarray}\rlap{/}{0}\end{eqnarray} für KK(G)) auffassen können. Der Kantenraum hat die Dimension |K(G)|.

Derjenige Unterraum C(G) des Kantenraumes \begin{eqnarray}{\mathscr{K}}\end{eqnarray} (G), der von den Kreisen (genauer, von den Kantenmengen, die zu einem beliebigen Kreis gehören) in G aufgespannt wird, heißt Zyklenraum, und seine Dimension ist gerade die zyklomatische Zahl \begin{eqnarray}\mu (G)=|K(G)|-|E(G)|\eta (G),\end{eqnarray} wobei η(G) die Anzahl der Zusammenhangskomponenten (zusammenhängender Graph) von G bedeutet.

Sind E1 und E2 zwei disjunkte und nicht leere Teilmengen der Eckenmenge E(G) mit E1E2 = E(G), so nennen wir die Menge aller Kanten, die mit einer Ecke aus E1 und einer Ecke aus E2 inzidieren, einen Schnitt in G. Derjenige Unterraum S(G) von K(G), der von den Schnitten in G aufgespannt wird, heißt Schnittraum, und seine Dimension ist \begin{eqnarray}|E(G)|-\eta (G).\end{eqnarray} Ferner gilt \begin{eqnarray}C(G)=S{(G)}^{\perp }\quad \text{und}\quad S(G)=C{(G)}^{\perp }.\end{eqnarray}

Schreiben Sie uns!

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

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.