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

Граф, представляющий перестановку

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

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

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

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

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

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

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

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

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

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

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

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

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

Подклассы графов перестановок включают двудольные графы перестановок (охарактеризованные Спинрадом, Брандштедтом и Стюартом в 1987 году) и кографы .

Примечания

1. Брандштедт, Le & Spinrad (1999), стр.191.
2. Брандштедт, Le & Spinrad (1999), Предложение 4.7.1, стр.57.
3. Душник и Миллер (1941).
4. Бейкер, Фишберн и Робертс (1971).
5. Макконнелл и Спинрад (1999).
6. Голумбик (1980).
7. Бодлендер, Клокс и Кратч (1995)

Ссылки

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

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

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