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.

Das Hasse-Diagramm einer partiellen Ordnung (links) und der zugehörige Vergleichbarkeitsgraph.

Definition

Ein gerichteter Graph ${\displaystyle (V,E)}$ heißt Vergleichbarkeitsgraph, wenn ${\displaystyle (V,<)}$ eine Halbordnung auf der Knotenmenge ${\displaystyle V}$ des Graphen ist, sodass für jede Kante ${\displaystyle (u,v)\in E}$ die Beziehung

${\displaystyle u<v}$

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

${\displaystyle u<v}$   oder   ${\displaystyle v<u}$

gilt.

Eigenschaften

• Jeder Vergleichbarkeitsgraph ist ein perfekter Graph.

Literatur

• Reinhard Diestel: Graphentheorie. Springer, 2006, ISBN 3-540-33408-4.