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 Graphen und seinen Blockgraphen. Dabei entsprechen c₁, …, c₄ den Artikulationspunkten 2, 7, 8, 10. Jeder Knoten b_k entspricht einem Block im Ursprungsgraphen.

Literatur

• Vorlage:Literatur