Vergleichbarkeitsgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Das Hasse-Diagramm einer partielle Ordnung (links) und der zugehörige 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[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]

Literatur[Bearbeiten | Quelltext bearbeiten]