Перестановочный граф

Перестановочный граф (Permutation graph) — граф пересечений сегментов в диаграмме пересечений перестановки; для построений последней возьмем по [math]\displaystyle{ \,n }[/math] точек на двух параллельных прямых и соединим прямолинейными отрезками пары точек согласно биекции определяемой перестановкой.

Литература

• Golumbic M.C. Algorithmic graph theory and perfect graphs. — New York: Academic Press, 1980.