imported>PerfektesChaos: tk k

2025-07-31T12:29:48Z

tk k

Neue Seite

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 [[K-Zusammenhang|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 [[Gelenkpunkt (Graphentheorie)|Artikulationen]] und <math> B </math> die Menge seiner [[Block (Graphentheorie)|Blöcke]]. Man bezeichnet den Graphen, der als [[Knoten (Graphentheorie)|Knotenmenge]] <math>V_B= A \cup B </math> hat und der eine [[Kante (Graphentheorie)|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 (Graphentheorie)|Wald]].
* <math>G_B</math> ist genau dann [[Baum (Graphentheorie)|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.

[[Datei:Block-cut tree2.svg|800px|ohne]]

== Literatur ==
* {{Literatur
|Autor=Reinhard Diestel
|Titel=Graphentheorie
|Verlag=Springer
|Ort=Berlin
|Datum=2010
|ISBN=978-3-642-14911-5
|Umfang=354}}

[[Kategorie:Bipartiter Graph]]
[[Kategorie:Bäume und Wälder]]

Blockgraph - Versionsgeschichte

imported>PerfektesChaos: tk k