Blockgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Blockgraph ist ein von einem gegebenen Graphen abgeleiteter Graph , der veranschaulicht wie sich die 2-zusammenhängenden Komponenten von zueinander verhalten.

Definition[Bearbeiten | Quelltext 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 hat genau dann besitzt, wenn für und gilt, dass (also wenn die Artikulation Teil des Blockes ist) als Blockgraph von .

Eigenschaften[Bearbeiten | Quelltext 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 zusammenhängend), wenn zusammenhängend ist.

Literatur[Bearbeiten | Quelltext bearbeiten]