Blockgraph

Ein Blockgraph ist in der Graphentheorie ein von einem gegebenen Graphen $G$ abgeleiteter Graph $G_{B}$ , der veranschaulicht, wie sich die 2-zusammenhängenden Komponenten von $G$ zueinander verhalten.

Definition

Sei $G = (V, E)$ ein einfacher Graph sowie $A$ die Menge seiner Artikulationen und $B$ die Menge seiner Blöcke. Man bezeichnet den Graphen, der als Knotenmenge $V_{B} = A \cup B$ hat und der eine Kante $(a, b)$ genau dann besitzt, wenn für $a \in A$ und $b \in B$ gilt, dass $a \in b$ (also wenn die Artikulation Teil des Blockes ist) als Blockgraph $G_{B}$ von $G$ .

Eigenschaften

Ein Blockgraph ist immer ein bipartiter Graph und die Mengen $A, B$ sind die Partitionsklassen des Graphen.
Der Blockgraph $G_{B}$ eines Graphen $G$ ist ein Wald.
$G_{B}$ ist genau dann Baum (also azyklisch und zusammenhängend), wenn $G$ zusammenhängend ist.

Beispiel

Folgende Abbildung zeigt einen Blockgraph. Jede 2-fach zusammenhängende Komponente dieses Graphs ist ein vollständiger Graph (Clique), da er mit jedem Knoten seines Blocks verbunden ist. Die Verbindungsknoten sind die Artikulationen.

Literatur

Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.).