Vergleichbarkeitsgraph
# Vergleichbarkeitsgraph

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 $(V,E)$ heißt Vergleichbarkeitsgraph, wenn $(V,<)$ eine Halbordnung auf der Knotenmenge $V$ des Graphen ist, sodass für jede Kante $(u,v)\in E$ die Beziehung

    $u<v$

gilt. Ein ungerichteter Graph $(V,E)$ heißt Vergleichbarkeitsgraph, wenn für jede Kante $\{u,v\}\in E$

    $u<v$ oder $v<u$

gilt.

## Eigenschaften

* Jeder Vergleichbarkeitsgraph ist ein perfekter Graph.
