Vergleichbarkeitsgraph
ungerichteter Graph, dessen Kanten transitiv orientiert werden können
From Wikipedia, the free encyclopedia
Ein Vergleichbarkeitsgraph ist in der Graphentheorie ein Graph, dessen Kanten einer Ordnungsrelation auf seinen Knoten genügen. Vergleichbarkeitsgraphen werden auch als transitiv orientierbare Graphen bezeichnet.
Definition
Ein gerichteter Graph heißt Vergleichbarkeitsgraph, wenn eine Halbordnung auf der Knotenmenge des Graphen ist, sodass für jede Kante die Beziehung
gilt. Ein ungerichteter Graph heißt Vergleichbarkeitsgraph, wenn für jede Kante
- oder
gilt.
Eigenschaften
- Jeder Vergleichbarkeitsgraph ist ein perfekter Graph.
Literatur
- Reinhard Diestel: Graphentheorie. Springer, 2006, ISBN 3-540-33408-4.