Граф перестановок

Граф перестановок и диаграмма соответствия для перестановки (4,3,5,1,2)

В математической области теории графов граф перестановок — это граф которого , вершины представляют элементы перестановки , а ребра представляют собой пары элементов, которые переворачиваются перестановкой. Графы перестановок также могут быть определены геометрически как графы пересечений отрезков прямых, конечные точки которых лежат на двух параллельных прямых. Различные перестановки могут привести к одному и тому же графу перестановок; данный граф имеет единственное представление (с точностью до перестановочной симметрии ), если он прост относительно модулярного разложения .

Определение и характеристика

Если $\rho =(\sigma _{1},\sigma _{2},...,\sigma _{n})$ это любая перестановка чисел из $1$ к $n$, то можно определить граф перестановок из $\sigma$ в котором есть $n$ вершины $v_{1},v_{2},...,v_{n}$, и в котором есть ребро $v_{i}v_{j}$ для любых двух индексов $i<j$ для чего $j$ появляется раньше $i$ в $\rho$. То есть два индекса $i$ и $j$ определяют ребро в графе перестановок именно тогда, когда они определяют инверсию в перестановке.

Учитывая перестановку $\sigma$, можно также определить набор отрезков $s_{i}$ с конечными точками $(i,0)$ и $(k,1)$, такой, что $\sigma _{k}=i$. Концы этих отрезков лежат на двух параллельных прямых. $y=0$ и $y=1$, и два сегмента имеют непустое пересечение тогда и только тогда, когда они соответствуют инверсии в перестановке. Таким образом, граф перестановок $\sigma$ совпадает с графом пересечения отрезков. Для каждых двух параллельных прямых и каждого конечного набора отрезков прямой с конечными точками на обеих линиях граф пересечения отрезков представляет собой граф перестановок; в случае, если все конечные точки сегмента различны, перестановка, для которой это граф перестановок, может быть задана путем нумерации сегментов на одной из двух строк в последовательном порядке и считывания этих чисел в том порядке, в котором появляются конечные точки сегмента. на другой линии.

Графы перестановок имеют несколько других эквивалентных характеристик:

• График $G$ является графом перестановок тогда и только тогда, когда $G$ — круговой граф , допускающий экватор , т. е. дополнительную хорду , пересекающую все остальные хорды.
• График $G$ является графом перестановок тогда и только тогда, когда оба $G$ и его дополнение ${\overline {G}}$ являются графиками сравнимости .
• График $G$ является графом перестановок тогда и только тогда, когда он является графом сравнимости , частично упорядоченного множества которого порядковая размерность не превышает двух.
• Если график $G$ является графом перестановок, как и его дополнение. Перестановка, представляющая собой дополнение $G$ может быть получено обращением перестановки, представляющей $G$.

Эффективные алгоритмы

Можно проверить, является ли данный граф графом перестановок, и если да, то построить представляющую его перестановку за линейное время .

Будучи подклассом идеальных графов , многие задачи, которые являются NP-полными для произвольных графов, могут быть эффективно решены для графов перестановок. Например:

• наибольшая клика в графе перестановок соответствует самой длинной убывающей подпоследовательности в перестановке, определяющей граф, поэтому проблема клики может быть решена за полиномиальное время для графов перестановок с использованием алгоритма самой длинной убывающей подпоследовательности.
• аналогично возрастающая подпоследовательность в перестановке соответствует независимому набору того же размера в соответствующем графе перестановок.
• ширина дерева и ширина пути графов перестановок могут быть вычислены за полиномиальное время; эти алгоритмы используют тот факт, что количество минимальных разделителей вершин включения в графе перестановок полиномиально по размеру графа.

Связь с другими классами графов

Графы перестановок — это частный случай круговых графов , графов сравнимости , дополнений графов сравнимости и трапециевидных графов .

Подклассы графов перестановок включают двудольные графы перестановок (характеризованные Spinrad, Brandstädt & Stewart 1987 ) и кографы .

Ссылки

• Бейкер, Кирби А.; Фишберн, Питер С .; Робертс, Фред С. (1971), «Частичные порядки размерности 2», Networks , 2 (1): 11–28, doi : 10.1002/net.3230020103 .
• Бодлендер, Ханс Л .; Клокс, Тон; Крач, Дитер (1995), «Ширина дерева и ширина пути графов перестановок», SIAM Journal on Discrete Mathematics , 8 (4): 606–616, doi : 10.1137/S089548019223992X , hdl : 1874/16657 .
• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми П. (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-Х .
• Душник, Бен; Миллер, Эдвин В. (1941), «Частично упорядоченные множества», American Journal of Mathematics , 63 (3): 600–610, doi : 10.2307/2371374 , JSTOR   2371374 .
• Голумбик, Мартин К. (1980), Алгоритмическая теория графов и совершенные графы , Информатика и прикладная математика, Academic Press, стр. 159 .
• МакКоннелл, Росс М.; Спинрад, Джереми П. (1999), «Модульное разложение и транзитивная ориентация», Discrete Mathematics , 201 (1–3): 189–241, doi : 10.1016/S0012-365X(98)00319-7 , MR   1687819 .
• Спинрад, Джереми П.; Брандштедт, Андреас ; Стюарт, Лорна К. (1987), «Двудольные графы перестановок», Discrete Applied Mathematics , 18 (3): 279–292, doi : 10.1016/s0166-218x(87)80003-3 .

Внешние ссылки

• «Граф перестановок» , Информационная система по классам графов и их включениям
• Вайсштейн, Эрик В. , «Граф перестановок» , MathWorld