В математике , А граф перестановка является графом , вершины которого представляют элементы перестановки , а ребра представляют собой пары элементов, которые обратные перестановкой . Графы перестановок также могут быть определены геометрически, как графы пересечений отрезков прямых, концы которых лежат на двух параллельных прямых. Различные перестановки могут привести к одному и тому же графу перестановок; данный граф имеет уникальное представление (с точностью до симметрии перестановки), если он прост относительно модулярного разложения . [1]
Определение и характеристика
Если σ = (σ 1 , a 2 , ..., σ п ) любая перестановка из чисел от 1 до п , то можно определить перестановку граф из а , в которой имеются п вершин v 1 , V 2 ,. .., v n , и в котором есть ребро v i v j для любых двух индексов i и j, для которых i < j и σ i > σ j . То есть два индекса i и j определяют ребро в графе перестановок именно тогда, когда они определяют инверсию перестановки.
Учитывая перестановку σ, можно также определить набор отрезков s i с конечными точками ( i , 0) и (σ i , 1). Концы этих сегментов лежат на двух параллельных прямых y = 0 и y = 1, и два сегмента имеют непустое пересечение тогда и только тогда, когда они соответствуют инверсии в перестановке. Таким образом, граф перестановок σ совпадает с графом пересечений отрезков. Для каждых двух параллельных прямых и каждого конечного набора линейных сегментов с конечными точками на обеих линиях граф пересечений сегментов является графом перестановок; в случае, когда все конечные точки сегментов различны, перестановка, для которой это граф перестановок, может быть задана путем нумерации сегментов на одной из двух линий в последовательном порядке и считывания этих чисел в том порядке, в котором появляются конечные точки сегмента. по другой линии.
Графы перестановок имеют несколько других эквивалентных характеристик:
- Граф G является графом перестановок тогда и только тогда, когда G - круговой граф , допускающий экватор, т. Е. Дополнительную хорду, пересекающую все остальные хорды. [2]
- Граф G является графом перестановок тогда и только тогда, когда и G, и его дополнение является сопоставимость графики . [3]
- Граф G является граф перестановки тогда и только тогда , когда она является сопоставимость график , из частично упорядоченного множества , который имеет размер порядка не более двух. [4]
- Если граф G является графом перестановок, то также и его дополнение. Перестановка , что представляет собой дополнение G может быть получена путем изменений перестановки , представляющей G .
Эффективные алгоритмы
Можно проверить, является ли данный граф графом перестановок, и, если да, построить перестановку, представляющую его, за линейное время . [5]
Как подкласс совершенных графов , многие проблемы, которые являются NP-полными для произвольных графов, могут быть эффективно решены для графов перестановок. Например:
- самая большая клика в графе перестановок соответствует самой длинной убывающей подпоследовательности в перестановке, определяющей граф, поэтому проблема клики может быть решена за полиномиальное время для графов перестановок с использованием алгоритма самой длинной убывающей подпоследовательности. [6]
- аналогично, возрастающая подпоследовательность в перестановке соответствует независимому набору того же размера в соответствующем графе перестановок.
- древесная ширина и pathwidth перестановок графов могут быть вычислены за полиномиальное время; эти алгоритмы используют тот факт, что количество включаемых минимальных разделителей вершин в графе перестановок полиномиально от размера графа. [7]
Отношение к другим классам графов
Графы перестановок - это частный случай круговых графов , графов сопоставимости , дополнений графов сопоставимости и графов трапеций .
Подклассы графов перестановок включают двудольные графы перестановок (охарактеризованные Spinrad, Brandstädt & Stewart 1987 ) и кографы .
Заметки
- ^ Brandstädt, Le & Спинрад (1999) , с.191.
- ^ Brandstädt, Le & Спинрад (1999) , предложение 4.7.1, стр.57.
- ^ Dushnik & Miller (1941) .
- ^ Бейкер, Фишберн & Roberts (1971) .
- ^ МакКоннелл и Спинрад (1999) .
- ^ Golumbic (1980) .
- ^ Bodlaender, Kloks & Kratsch (1995)
Рекомендации
- Бейкер, Кирби А .; Фишберн, Питер С .; Робертс, Фред С. (1971), «Частичные порядки измерения 2», Сети , 2 (1): 11–28, DOI : 10.1002 / net.3230020103.
- Bodlaender, Hans L .; Клокс, Тон; Kratsch, Дитер (1995), "древесная ширина и pathwidth перестановок графов", SIAM журнал по дискретной математике , 8 (4): 606-616, DOI : 10,1137 / S089548019223992X , ЛВП : 1874/16657.
- Брандштадт, Андреас ; Ле, Ван Банг; Спинрад, Джереми П. (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
- Душник, Бен; Миллер, Эдвин W. (1941), "Частично упорядоченные множества" (PDF) , американский журнал математики , 63 (3): 600-610, DOI : 10,2307 / 2371374 , JSTOR 2371374.
- Голумбик, Мартин К. (1980), Алгоритмическая теория графов и совершенные графы , информатика и прикладная математика, Academic Press, стр. 159 CS1 maint: обескураженный параметр ( ссылка ).
- МакКоннелл, Росс М .; Спинрад, Джереми П. (2011), "Модульное разложение и транзитивна ориентация", дискретная математика , 201 (1-3): 189-241, Arxiv : 1010,5447 , DOI : 10.1016 / S0012-365X (98) 00319-7 , М.Р. 1687819.
- Spinrad, Джереми П .; Брандштадт, Андреас ; Стюарт, Лорна К. (1987), "двудольный граф перестановка", Дискретная прикладная математика , 18 (3): 279-292, DOI : 10.1016 / s0166-218x (87) 80003-3.
Внешние ссылки
- «Граф перестановок» , Информационная система по классам графов и их включениям.
- Вайсштейн, Эрик В. "Перестановочный граф" . MathWorld .