Індиферентний граф

Індиферентний граф, утворений на множині точок на дійсній прямій з'єднанням пар, відстань між якими не перевищує 1

Індиферентний граф — це неорієнтований граф, побудований призначенням дійсного числа кожній вершині і з'єднанням двох вершин ребром, коли їхні числа відрізняються не більше ніж на одиницюШаблон:Sfn. Індиферентні графи є також графами перетинів множин одиничних відрізків або інтервалів з визначеною властивістю вкладення (ніякий інтервал не містить будь-якого іншого). Ґрунтуючись на цих двох типах інтервальних подань, ці графи називаються також графами одиничних відрізків або власними інтервальними графами. Індиферентні графи утворюють підклас інтервальних графів.

Еквівалентні описи

Заборонені породжені підграфи для індиферентних графів — клешня, «сонце», «мережа» і цикли довжиною чотири і більше (внизу)

Скінченні індиферентні графи можна еквівалентно описати як

• Графи перетинів одиничних відрізківШаблон:Sfn
• Графи перетинів множин інтервалів, ніякі два з яких не вкладені один в іншийШаблон:SfnШаблон:Sfn
• Інтервальні графи без клешеньШаблон:SfnШаблон:Sfn
• Графи, які не містять породжених підграфів, ізоморфних клешні K_1,3, «мережі» (трикутнику з трьома додатковими вершинами, приєднаними до кожної з вершин трикутника), «сонцю» (трикутнику з трьома приєднаними трикутниками, які мають спільні ребра з центральним трикутником), або «дірці» (циклу довжини чотири і більше)Шаблон:Sfn
• Графи непорівнянності Шаблон:Не перекладеноШаблон:Sfn
• Неорієнтовані графи, які мають лінійний порядок, такий, що для кожного шляху з трьох вершин $uvw$, вершини якого впорядковані $u$-$v$-$w$, кінцеві вершини $u$ і $w$ суміжніШаблон:Sfn
• Графи, які не мають астральних трійок, трьох вершин, з'єднаних попарно шляхами, які не проходять через третю вершину, а також не містять двох суміжних вершин, одночасно суміжних вершині з околу третьої вершиниШаблон:Sfn.
• Графи, в яких кожна компонента містить шлях, у якому кожна кліка компоненти утворює неперервний підшляхШаблон:Sfn
• Графи, вершини яких можна пронумерувати так, що будь-який найкоротший шлях утворює монотонну послідовністьШаблон:Sfn
• Графи, матриці суміжності яких можна впорядкувати так, що в кожному рядку і кожному стовпці ненульові елементи утворюють неперервні інтервали, суміжні діагоналі матриціШаблон:Sfn
• Породжені підграфи степенів безхордових шляхівШаблон:Sfn
• Шаблон:Не перекладено, які мають Шаблон:Не перекладено у вигляді гусениціШаблон:Sfn

Для нескінченних графів деякі з цих визначень можуть дати різні графи.

Властивості

Оскільки індиферентні графи є окремим випадком інтервальних графів, індиферентні графи мають усі властивості інтервальних графів. Зокрема, вони є окремим випадком хордальних графів і досконалих графів. Ці графи є також окремим випадком колових графів, що хибно для інтервальних графів загального вигляду.

У моделі Ердеша — Реньї випадкових графів граф з $n$ вершини, число ребер якого істотно менше від $n^{2/3}$, буде з великою ймовірністю індиферентним графом, тоді як граф з числом ребер, істотно більшим від $n^{2/3}$, з великою ймовірністю не буде індиферентним графомШаблон:Sfn.

Шаблон:Не перекладено довільного графу $G$ на одиницю менша від розміру найбільшої кліки в індиферентному графі, який містить $G$ як підграф і вибраний для мінімізації розміру найбільшої клікиШаблон:Sfn. Це властивість утворює паралелі, подібні до зв'язку між шляховою шириною та інтервальними графами, а також між деревною шириною та хордальними графами. Слабше поняття ширини, клікова ширина, може бути довільно великою на індиферентних графахШаблон:Sfn. Однак будь-який власний підклас індиферентних графів, не замкнутий відносно породжених підграфів, має обмежену клікову ширинуШаблон:Sfn.

Будь-який зв'язний індиферентний граф містить гамільтонів шляхШаблон:Sfn. Індиферентний граф має гамільтонів граф тоді і тільки тоді, коли він двосв'язнийШаблон:Sfn.

Індиферентні графи задовольняють Шаблон:Не перекладено — вони єдиним чином визначаються їхніми підграфами з видаленою вершиноюШаблон:Sfn.

Алгоритми

Як і з багатовимірними графами одиничних кругів, можна перетворити множину точок на її індиферентний граф або множину одиничних відрізків на її граф одиничних відрізків за лінійний час, якщо вимірювати в термінах розміру початкового графу. Алгоритм округлює точки (або центри інтервалів) до найближчого меншого цілого числа, використовує геш-таблицю для знаходження всіх пар точок, чиї округлені значення відрізняються не більше ніж на одиницю (пошук найближчого сусіда з фіксованим радіусом), і відбирає в отриманому списку пари, неокруглені значення яких лежать не далі ніж на одиницю одне від одногоШаблон:Sfn.

Можна перевірити, чи є даний граф індиферентним за лінійний час за допомогою PQ-дерев для побудови інтервальних подань графу і потім перевірки, чи задовольняє впорядкування вершин, похідне від цього подання, властивостям індиферентного графуШаблон:Sfn. Можна також заснувати алгоритм розпізнавання для індиферентних графів на алгоритмах розпізнавання для хордального графуШаблон:Sfn. Деякі альтернативні алгоритми розпізнавання за лінійний час ґрунтуються на пошуку в ширину або на лексикографічному пошуку в ширину, а не на зв'язку між індиферентними графами і інтервальними графамиШаблон:SfnШаблон:Sfn Шаблон:SfnШаблон:Sfn.

Як тільки вершини відсортовано за їхніми числовими значеннями, які описують індиферентний граф (або за послідовністю одиничних відрізків у інтервальному поданні), той самий порядок можна використовувати для пошуку оптимального розфарбування цих графів, щоб розв'язати задачу про найкоротший шлях, побудову гамільтонових шляхів і найбільших парувань за лінійний часШаблон:Sfn. Гамільтонів цикл можна знайти з правильного інтервального графу подання за час $O(n\log n)$Шаблон:Sfn, але, якщо граф є вхідним для завдання, цю ж задачу можна розв'язати за лінійний час, що можна узагальнити на інтервальні графиШаблон:SfnШаблон:Sfn .

Задача Шаблон:Нп залишається NP-повною, навіть коли вона обмежена індиферентними графамиШаблон:Sfn. Однак вона є Шаблон:Не перекладено, якщо параметризувати за загальною кількістю кольорів на входіШаблон:Sfn.

Застосування

У математичній психології індиферентні графи виникають із функцій корисності масштабуванням функції так, що одна одиниця представляє різницю корисності досить малою, так що для особистості одиниця може вважатися несуттєвою. У цьому застосуванні пари елементів, корисності яких досить великі, можна частково впорядкувати за відносним порядком корисності, що дає Шаблон:Не перекладеноШаблон:SfnШаблон:Sfn.

У біоінформатиці задачу додавання розфарбованого графу до правильно розфарбованого графу одиничних відрізків можна використати для моделювання виявлення помилково негативних збірок геному ДНК із фрагментівШаблон:Sfn.

Див. також

• Пороговий граф — граф, ребра якого визначаються сумами міток вершин, а не різницями міток
• Тривіально досконалий граф — інтервальний граф, для якого кожна пара інтервалів вкладена або неперервана, а не належним чином перетинається

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга. Як процитовано в Шаблон:Harvtxt
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Information System on Graph Class Inclusions Шаблон:Webarchive: unit interval graph Шаблон:Webarchive