Direkt zum Inhalt

Lexikon der Mathematik: Block

ein maximaler zusammenhängender Teilgraph ohne Artikulation.

Es sei G ein zusammenhängender Graph mit mindestens zwei Ecken. Ein zusammenhängender Teilgraph B von G heißt Block von G, wenn B keine trennende Ecke besitzt, und wenn es keinen zusammenhängenden Teilgraphen \({B}^{^{\prime} }\subseteq G\) ohne trennende Ecke gibt mit \(B\subseteq {B}^{^{\prime} }\) und \(B\ne {B}^{^{\prime} }\).

Da der vollständige Graph \({K}_{2}\) keine trennende Ecke hat, enthält jeder Block mindestens eine Kante. Sind \({B}_{1},{B}_{2},\ldots, {B}_{t}\) alle Blöcke eines Graphen G, so hat König 1936 folgende Strukturaussagen nachgewiesen.

Zwei verschiedene Blöcke haben höchstens eine gemeinsame Ecke und damit insbesondere keine gemeinsame Kante.

Daraus ergibt sich

\begin{eqnarray}K(G)=K({B}_{1})\cup K({B}_{2})\cup \ldots \cup K({B}_{t}).\end{eqnarray}

Eine Ecke x ist genau dann eine gemeinsame Ecke zweier verschiedener Blöcke, wenn x eine trennende Ecke von G ist. Im Jahre 1953 haben Harary und Norman gezeigt, daß das Zentrum eines Graphen G in einem einzigen Block von G enthalten ist.

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