Граф перестановки![]() В теорії графів граф перестановки — це граф, вершини якого відповідають елементам перестановки, а ребра представляють пари елементів, порядок слідування яких змінився після перестановки. Графи перестановки можна визначити геометрично як графи перетинів відрізків, кінці яких лежать на двох паралельних прямих. Різні перестановки можуть дати один і той самий граф перестановки. Заданий граф має єдине подання (з точністю до симетрії) якщо він є простим з точки зору модульної декомпозиції[1]. Визначення та описНехай σ = (σ1,σ2, …, σn) — деяка перестановка чисел від 1 до n. Для σ граф перестановки має n вершин v1, v2, …, vn і в цьому графі ребро vivj існує для будь-яких двох індексів i та j, для яких i < j і σi > σj. Таким чином, для двох індексів i та j ребро в графі визначається точно так само, як визначається транспозиція в перестановці. Якщо задано перестановку σ, можна визначити множину відрізків si з кінцевими точками (i,0) і (σi,1). Кінцеві точки цих відрізків розташовуються на двох паралельних прямих y = 0 і y = 1, і два відрізки мають непорожній перетин тоді і тільки тоді, коли вони відповідають інверсії в перестановці. Таким чином, граф перестановки для σ збігається з графом перетинів відрізків. Для будь-яких двох паралельних прямих і будь-якого скінченного набору відрізків з кінцями на цих прямих граф перетинів відрізків є графом перестановки. Якщо всі скінченні точки відрізків різні, перестановку, відповідну графу перестановки, можна отримати нумерацією відрізків на одній з прямих (послідовно, наприклад, зліва направо), тоді числа на інший прямий дадуть шукану перестановку. Графи перестановки можна описати деякими іншими еквівалентними способами:
Ефективні алгоритмиМожна перевірити, чи є граф графом перестановки, і побудувати відповідну йому перестановку за лінійний час[5]. Як для підкласу досконалих графів, багато задач, NP-повних для довільних графів, для графів перестановки можна розв'язати ефективно. Наприклад:
Відношення до інших класів графівГрафи перестановки є особливим випадком колових графів, графів порівнянності, доповненням графів порівнянності і трапецеїдальних графів. Підкласами графів перестановки є двочасткові графи перестановок і кографи. Примітки
Література
Посилання
|
Portal di Ensiklopedia Dunia