Blockgraph

Ein Blockgraph ist in der Graphentheorie ein von einem gegebenen Graphen <math> G </math> abgeleiteter Graph <math> G_B </math>, der veranschaulicht, wie sich die 2-zusammenhängenden Komponenten von <math> G </math> zueinander verhalten.

Definition

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

Eigenschaften

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

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