Vergleichbarkeitsgraph
Zur Navigation springen
Zur Suche springen
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/29/Poset_et_graphe_de_comparabilit%C3%A9.svg/220px-Poset_et_graphe_de_comparabilit%C3%A9.svg.png)
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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]- Jeder Vergleichbarkeitsgraph ist ein perfekter Graph.
Literatur
[Bearbeiten | Quelltext bearbeiten]- Reinhard Diestel: Graphentheorie. Springer, 2006, ISBN 3-540-33408-4.