Vergleichbarkeitsgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Ein Vergleichbarkeitsgraph bezüglich der lexikalischen Ordnung

Ein Vergleichbarkeitsgraph ist in der Graphentheorie ein Graph, dessen Kanten einer Ordnungsrelation auf seinen Knoten genügen.

Definition[Bearbeiten]

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[Bearbeiten]

Literatur[Bearbeiten]