Vergleichbarkeitsgraph

Graphentheorie, Teilgebiet der Mathematik

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

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

Literatur

Bearbeiten