Separatoren

Def: Für G = (V, E), a, b $ \in$ V: S$ \subeteq$V(G) heißt (a, b) -Separator, falls a, b in verschiedenen Komponenten von G $ \setminus$ S.

Satz: G ist chordal $ \iff$ jeder minimale (a, b)-Separator induziert eine Clique in G.



Johannes Waldmann 2005-01-25