Blockgraph

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

Definition

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

Eigenschaften

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