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

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

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

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

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

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

У моделі Ердеша — Реньї випадкових графів граф з вершини, число ребер якого істотно менше від , буде з великою ймовірністю індиферентним графом, тоді як граф з числом ребер, істотно більшим від , з великою ймовірністю не буде індиферентним графом.

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

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

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

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

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

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

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

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

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

Див. також

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

Примітки

Література

. Як процитовано в

Посилання Information System on Graph Class Inclusions : unit interval graph