Comparability graph

Материал из WikiGrapp
Перейти к:навигация, поиск

Comparability graphграф сравнимости.

Let \,G = (V,E) be an undirected graph and let \,F be an orientation of its edges (i.e. \,(V,F) is the resulting oriented graph). \,F is called a transitive orientation of \,G if the following properties hold:

\,F \cap F^{-1} = \emptyset\mbox{ and }F + F^{-1} = E\mbox{ and }F^{2} \subseteq F,

where \,F^{2} = \{(a,c)| \; \exists_{b \in V}(a,b) \in F \wedge (b,c) \in F\}.

A graph \,G which admits a transitive orientation of its edges is called a comparability graph.

If graph \,G is a comparability graph, then this also holds for every [[induced subgraph]] of \,G.

The other name is a Transitively orientable graph.


  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.