Website durchsuchen

Vergleichbarkeitsgraph

Das Hasse-Diagramm einer partiellen 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

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

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 04.11. 2020