Zweifach zusammenhängende Komponenten

Def: x $ \in$ V(G) ist Artikulationspunkt, falls K(G) > K(G $ \setminus$ v)

(wobei K(G) = Anzahl der Zusammenhangskomponenten von G).

Def: M $ \subseteq$ V(G) ist 2-fache Zusammenhangs-Komponente (Block), falls M maximal 2-fach zusammenhängend ist:

  1. G|M ist 2-fach zusammenhängend
  2. für jede echte Obermenge M' $ \supset$ M gilt: G|M' ist nicht 2-fach zusammenhängend

Literatur: Brandstädt: Graphen und Algorithmen



Johannes Waldmann 2005-01-25