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

Перестановка (4, 3, 5, 1, 2) и соответствующий граф перестановки

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

Определение и описание

Пусть σ = (σ₁,σ₂, ..., σ_n) — какая-либо перестановка чисел от 1 до n. Для σ граф перестановки имеет n вершин v₁, v₂, ..., v_n и в этом графе ребро v_iv_j существует для любых двух индексов i и j , для которых i < j и σ_i > σ_j. Таким образом, для двух индексов i и j ребро в графе определяется в точности таким же образом, как определяется транспозиция в перестановке.

Если задана перестановка σ, можно определить множество отрезков s_i с конечными точками (i,0) and (σ_i,1). Конечные точки этих отрезков располагаются на двух параллельных прямых y = 0 и y = 1, и два отрезка имеют непустое пересечение тогда и только тогда, когда они соответствуют инверсии в перестановке. Таким образом, граф перестановки для σ совпадает с графом пересечений отрезков. Для любых двух параллельных прямых и любого конечного набора отрезков с концами на этих прямых граф пересечений отрезков является графом перестановки. Если все конечные точки отрезков различны, перестановку, соответствующую графу перестановки, можно получить путём нумерации отрезков на одной из прямых (последовательно, например, слева направо), тогда числа на другой прямой дадут искомую перестановку.

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

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

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

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

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

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

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

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

Подклассами графов перестановки являются двудольные графы перестановок и кографы.

Примечания

1. Brandstädt, Le, Spinrad, 1999, стр.191.
2. Brandstädt, Le, Spinrad, 1999, Предложение 4.7.1, стр.57.
3. Dushnik, Miller, 1941.
4. Baker, Fishburn, Roberts, 1971.
5. McConnell, Spinrad, 1999.
6. Golumbic, 1980.
7. Bodlaender, Kloks, Kratsch, 1995.

Литература

• K. A. Baker, P. C. Fishburn, F. S. Roberts. Partial orders of dimension 2 // Networks. — 1971. — Т. 2, вып. 1. — С. 11–28. — doi:10.1002/net.3230020103.
• Hans L. Bodlaender, Ton Kloks, Dieter Kratsch. Treewidth and pathwidth of permutation graphs // SIAM Journal on Discrete Mathematics. — 1995. — Т. 8, вып. 4. — С. 606—616. — doi:10.1137/S089548019223992X.
• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999.
• Ben Dushnik, E. W. Miller. Partially ordered sets // American Journal of Mathematics. — 1941. — Т. 63, вып. 3. — С. 600—610. — doi:10.2307/2371374. — JSTOR 2371374.
• M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. — 1980. — С. 159.
• Ross M. McConnell, Jeremy P. Spinrad. Modular decomposition and transitive orientation // Discrete Mathematics. — 1999. — Т. 201, вып. 1—3. — С. 189—241. — doi:10.1016/S0012-365X(98)00319-7.

Ссылки

• Permutation graph  (неопр.). Information System on Graph Classes and their Inclusions. Дата обращения: 8 апреля 2014. Архивировано 4 апреля 2014 года.
• Weisstein, Eric W. Permutation Graph (англ.) на сайте Wolfram MathWorld.