Ein Blockgraph ist in der Graphentheorie ein von einem gegebenen Graphen abgeleiteter Graph , der veranschaulicht, wie sich die 2-zusammenhängenden Komponenten von zueinander verhalten.
Definition Bearbeiten
Sei ein einfacher Graph sowie die Menge seiner Artikulationen und die Menge seiner Blöcke. Man bezeichnet den Graphen, der als Knotenmenge hat und der eine Kante genau dann besitzt, wenn für und gilt, dass (also wenn die Artikulation Teil des Blockes ist) als Blockgraph von .
Eigenschaften Bearbeiten
- Ein Blockgraph ist immer ein bipartiter Graph und die Mengen sind die Partitionsklassen des Graphen.
- Der Blockgraph eines Graphen ist ein Wald.
- ist genau dann Baum (also azyklisch und zusammenhängend), wenn zusammenhängend ist.
Literatur Bearbeiten
- Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.).