Direkt zum Inhalt

Lexikon der Mathematik: Block-Schnittecken-Graph

ein Graph, der aus den Blöcken und den trennenden Ecken eines gegebenen Graphen gewonnen wird.

Es sei G ein zusammenhängender Graph. Sind \({B}_{1},{B}_{2},\ldots, {B}_{t}\) die Blöcke und x1, x2, …, xr die trennenden Ecken von G, so besteht der Block-Schnittecken-Graph oder Block-Artikulationsgraph aus den Eckenmengen X = B1, B2, …, Bt sowie \(Y=\{{x}_{1},{x}_{2},\ldots, {x}_{r}\}\) und den Kanten \({x}_{i}{B}_{j}\) für \(1\le i\le r\) und \(1\le j\le t\), falls \({x}_{i}\in E({B}_{j})\) gilt.

Nach dieser Konstruktion ist der Block-Schnittecken-Graph bipartit mit den beiden Partitionsmengen X und Y. Darüber hinaus zeigten Harary und Prins 1966, daß der Block-Schnittecken-Graph sogar ein Baum 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