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

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

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

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

Если σ = (σ₁, σ₂, ..., σ_п) любой перестановка чисел от 1 до п, то можно определить граф перестановок из σ, в котором есть п вершины v₁, v₂, ..., v_п, и в котором есть ребро v_яv_j для любых двух индексов я и j для которого я < j и σ_я > σ_j. То есть два индекса я и j определяют ребро в графе перестановок именно тогда, когда они определяют инверсия в перестановке.

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

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

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

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

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

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

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

Отношение к другим классам графов

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

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

Примечания

^ Brandstädt, Le & Spinrad (1999), с.191.
^ Brandstädt, Le & Spinrad (1999), Предложение 4.7.1, стр.57.
^ Душник и Миллер (1941).
^ Бейкер, Фишберн и Робертс (1971).
^ Макконнелл и Спинрад (1999).
^ Голумбик (1980).
^ Бодлендер, Клокс и Крач (1995)

внешняя ссылка

[1] Brandstädt, Le & Spinrad (1999), с.191.

[2] Brandstädt, Le & Spinrad (1999), Предложение 4.7.1, стр.57.

[3] Душник и Миллер (1941).

[4] Бейкер, Фишберн и Робертс (1971).

[5] Макконнелл и Спинрад (1999).

[6] Голумбик (1980).

[7] Бодлендер, Клокс и Крач (1995)

[1]

[2]

[3]

[4]

[5]

[6]

[7]