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 c1, …, c4 den Artikulationspunkten 2, 7, 8, 10. Jeder Knoten bk entspricht einem Block im Ursprungsgraphen.
Literatur
- {{#invoke:Vorlage:Literatur|f}}