Permutation graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Permutation graph''' --- перестановочный граф, граф перестановки If <math>\pi</math> is a permutation of the numbers <math>1,…») |
(нет различий)
|
Текущая версия от 15:06, 9 июня 2011
Permutation graph --- перестановочный граф, граф перестановки
If [math]\displaystyle{ \pi }[/math] is a permutation of the numbers [math]\displaystyle{ 1, \ldots, n }[/math], we can construct an undirected graph [math]\displaystyle{ G[\pi] = (V,E) }[/math] with a vertex set [math]\displaystyle{ V = \{1, \ldots, n\} }[/math] and an edge set [math]\displaystyle{ E }[/math]:
[math]\displaystyle{ (i,j) \in E \Leftrightarrow (i - j)(\pi_{i}^{-1} - \pi_{j}^{-1}) \lt 0. }[/math]
An undirected graph is called a permutation graph if there exists a permutation [math]\displaystyle{ \pi }[/math] such that [math]\displaystyle{ G \cong G[\pi] }[/math]. It is known that the complement of a permutation graph is also a permutation graph and a permutation graph is a comparability graph.