Blockgraph

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

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

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

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.

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

• Bipartiter Graph
• Bäume und Wälder