Індиферентний граф
Індиферентний граф — це неорієнтований граф, побудований призначенням дійсного числа кожній вершині і з'єднанням двох вершин ребром, коли їхні числа відрізняються не більше ніж на одиницю[1]. Індиферентні графи є також графами перетинів множин одиничних відрізків або інтервалів з визначеною властивістю вкладення (ніякий інтервал не містить будь-якого іншого). Ґрунтуючись на цих двох типах інтервальних подань, ці графи називаються також графами одиничних відрізків або власними інтервальними графами. Індиферентні графи утворюють підклас інтервальних графів.
Еквівалентні описи[ред. | ред. код]
Скінченні індиферентні графи можна еквівалентно описати як
- Графи перетинів одиничних відрізків[1]
- Графи перетинів множин інтервалів, ніякі два з яких не вкладені один в інший[1][2]
- Інтервальні графи без клешень[1][2]
- Графи, які не містять породжених підграфів, ізоморфних клешні K1,3, «мережі» (трикутнику з трьома додатковими вершинами, приєднаними до кожної з вершин трикутника), «сонцю» (трикутнику з трьома приєднаними трикутниками, які мають спільні ребра з центральним трикутником), або «дірці» (циклу довжини чотири і більше)[3]
- Графи непорівнянності напівпорядків[en][1]
- Неорієнтовані графи, які мають лінійний порядок, такий, що для кожного шляху з трьох вершин , вершини якого впорядковані --, кінцеві вершини і суміжні[4]
- Графи, які не мають астральних трійок, трьох вершин, з'єднаних попарно шляхами, які не проходять через третю вершину, а також не містять двох суміжних вершин, одночасно суміжних вершині з околу третьої вершини[5].
- Графи, в яких кожна компонента містить шлях, у якому кожна кліка компоненти утворює неперервний підшлях[6]
- Графи, вершини яких можна пронумерувати так, що будь-який найкоротший шлях утворює монотонну послідовність[6]
- Графи, матриці суміжності яких можна впорядкувати так, що в кожному рядку і кожному стовпці ненульові елементи утворюють неперервні інтервали, суміжні діагоналі матриці[7]
- Породжені підграфи степенів безхордових шляхів[8]
- Листкові степені[en], які мають листковий корінь[en] у вигляді гусениці[8]
Для нескінченних графів деякі з цих визначень можуть дати різні графи.
Властивості[ред. | ред. код]
Оскільки індиферентні графи є окремим випадком інтервальних графів, індиферентні графи мають усі властивості інтервальних графів. Зокрема, вони є окремим випадком хордальних графів і досконалих графів. Ці графи є також окремим випадком колових графів, що хибно для інтервальних графів загального вигляду.
У моделі Ердеша — Реньї випадкових графів граф з вершини, число ребер якого істотно менше від , буде з великою ймовірністю індиферентним графом, тоді як граф з числом ребер, істотно більшим від , з великою ймовірністю не буде індиферентним графом[9].
Ширина стрічки[en] довільного графу на одиницю менша від розміру найбільшої кліки в індиферентному графі, який містить як підграф і вибраний для мінімізації розміру найбільшої кліки[10]. Це властивість утворює паралелі, подібні до зв'язку між шляховою шириною та інтервальними графами, а також між деревною шириною та хордальними графами. Слабше поняття ширини, клікова ширина, може бути довільно великою на індиферентних графах[11]. Однак будь-який власний підклас індиферентних графів, не замкнутий відносно породжених підграфів, має обмежену клікову ширину[12].
Будь-який зв'язний індиферентний граф містить гамільтонів шлях[13]. Індиферентний граф має гамільтонів граф тоді і тільки тоді, коли він двосв'язний[14].
Індиферентні графи задовольняють гіпотезі про реконструкцію[en] — вони єдиним чином визначаються їхніми підграфами з видаленою вершиною[15].
Алгоритми[ред. | ред. код]
Як і з багатовимірними графами одиничних кругів, можна перетворити множину точок на її індиферентний граф або множину одиничних відрізків на її граф одиничних відрізків за лінійний час, якщо вимірювати в термінах розміру початкового графу. Алгоритм округлює точки (або центри інтервалів) до найближчого меншого цілого числа, використовує геш-таблицю для знаходження всіх пар точок, чиї округлені значення відрізняються не більше ніж на одиницю (пошук найближчого сусіда з фіксованим радіусом), і відбирає в отриманому списку пари, неокруглені значення яких лежать не далі ніж на одиницю одне від одного[16].
Можна перевірити, чи є даний граф індиферентним за лінійний час за допомогою PQ-дерев для побудови інтервальних подань графу і потім перевірки, чи задовольняє впорядкування вершин, похідне від цього подання, властивостям індиферентного графу[4]. Можна також заснувати алгоритм розпізнавання для індиферентних графів на алгоритмах розпізнавання для хордального графу[14]. Деякі альтернативні алгоритми розпізнавання за лінійний час ґрунтуються на пошуку в ширину або на лексикографічному пошуку в ширину, а не на зв'язку між індиферентними графами і інтервальними графами[17][18] [19][20].
Як тільки вершини відсортовано за їхніми числовими значеннями, які описують індиферентний граф (або за послідовністю одиничних відрізків у інтервальному поданні), той самий порядок можна використовувати для пошуку оптимального розфарбування цих графів, щоб розв'язати задачу про найкоротший шлях, побудову гамільтонових шляхів і найбільших парувань за лінійний час[4]. Гамільтонів цикл можна знайти з правильного інтервального графу подання за час [13], але, якщо граф є вхідним для завдання, цю ж задачу можна розв'язати за лінійний час, що можна узагальнити на інтервальні графи[21][22] .
Задача спискового розфарбовування[en] залишається NP-повною, навіть коли вона обмежена індиферентними графами[23]. Однак вона є фіксовано-параметрично розв'язною[en], якщо параметризувати за загальною кількістю кольорів на вході[12].
Застосування[ред. | ред. код]
У математичній психології індиферентні графи виникають із функцій корисності масштабуванням функції так, що одна одиниця представляє різницю корисності досить малою, так що для особистості одиниця може вважатися несуттєвою. У цьому застосуванні пари елементів, корисності яких досить великі, можна частково впорядкувати за відносним порядком корисності, що дає напівпорядок[en][1][24].
У біоінформатиці задачу додавання розфарбованого графу до правильно розфарбованого графу одиничних відрізків можна використати для моделювання виявлення помилково негативних збірок геному ДНК із фрагментів[25].
Див. також[ред. | ред. код]
- Пороговий граф — граф, ребра якого визначаються сумами міток вершин, а не різницями міток
- Тривіально досконалий граф — інтервальний граф, для якого кожна пара інтервалів вкладена або неперервана, а не належним чином перетинається
Примітки[ред. | ред. код]
- ↑ а б в г д е Roberts, 1969, с. 139–146.
- ↑ а б Bogart, West, 1999, с. 21–23.
- ↑ Wegner, 1967.
- ↑ а б в Looges, Olariu, 1993, с. 15–25.
- ↑ Jackowski, 1992, с. 103–109.
- ↑ а б Gutierrez, Oubiña, 1996, с. 199–205.
- ↑ Mertzios, 2008, с. 332–337.
- ↑ а б Brandstädt, Hundt, Mancini, Wagner, 2010, с. 897–910.
- ↑ Cohen, 1982, с. 21–24.
- ↑ Kaplan, Shamir, 1996, с. 540–561.
- ↑ Golumbic, Rotics, 1999, с. 5–17.
- ↑ а б Lozin, 2008, с. 871–882.
- ↑ а б Bertossi, 1983, с. 97–101.
- ↑ а б Panda, Das, 2003, с. 153–161.
- ↑ von Rimscha, 1983, с. 283–291.
- ↑ Bentley, Stanat, Williams, 1977, с. 209–212.
- ↑ Corneil, Kim, Natarajan, Olariu, Sprague, 1995, с. 99–104.
- ↑ Herrera de Figueiredo, Meidanis, Picinin de Mello, 1995, с. 179–184.
- ↑ Corneil, 2004, с. 371–379.
- ↑ Hell, Huang, 2004, с. 554–570.
- ↑ Keil, 1985, с. 201–206.
- ↑ Ibarra, 2009, с. 1105–1108.
- ↑ Marx, 2006, с. 995–1002.
- ↑ Roberts, 1970, с. 243–258.
- ↑ Goldberg, Golumbic, Kaplan, Shamir, 2009.
Література[ред. | ред. код]
- Fred S. Roberts. Indifference graphs // Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). — Academic Press, New York, 1969. — С. 139–146.
- Kenneth P. Bogart, Douglas B. West. A short proof that "proper=unit" // Discrete Mathematics. — 1999. — Т. 201, вип. 1-3 (21 квітня). — С. 21–23. — DOI: .
- Wegner G. Eigenschaften der Nerven homologisch-einfacher Familien im Rn. — Göttingen, Germany : Göttingen University, 1967. — (Ph.D. thesis). Як процитовано в Hell, Huang, (2004)
- Peter J. Looges, Stephan Olariu. Optimal greedy algorithms for indifference graphs // Computers & Mathematics with Applications. — 1993. — Т. 25, вип. 7 (21 квітня). — С. 15–25. — DOI: .
- Zygmunt Jackowski. A new characterization of proper interval graphs // Discrete Mathematics. — 1992. — Т. 105, вип. 1-3 (21 квітня). — С. 103–109. — DOI: .
- Gutierrez M., Oubiña L. Metric characterizations of proper interval graphs and tree-clique graphs // Journal of Graph Theory. — 1996. — Т. 21, вип. 2 (21 квітня). — С. 199–205. — DOI: .
- George B. Mertzios. A matrix characterization of interval and proper interval graphs // Applied Mathematics Letters. — 2008. — Т. 21, вип. 4 (21 квітня). — С. 332–337. — DOI: .
- Andreas Brandstädt, Christian Hundt, Federico Mancini, Peter Wagner. Rooted directed path graphs are leaf powers // Discrete Mathematics. — 2010. — Т. 310 (21 квітня). — С. 897–910. — DOI: .
- Joel E. Cohen. The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph // Discrete Mathematics. — 1982. — Т. 40, вип. 1 (21 квітня). — С. 21–24. — DOI: .
- Haim Kaplan, Ron Shamir. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques // SIAM Journal on Computing. — 1996. — Т. 25, вип. 3 (21 квітня). — С. 540–561. — DOI: .
- Martin Charles Golumbic, Udi Rotics. The clique-width of unit interval graphs is unbounded // Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999). — 1999. — Т. 140. — С. 5–17. — (Congressus Numerantium)
- Vadim V. Lozin. From tree-width to clique-width: excluding a unit interval graph // Algorithms and computation. — Springer, Berlin, 2008. — Т. 5369. — С. 871–882. — (Lecture Notes in Comput. Sci.) — DOI:
- Alan A. Bertossi. Finding Hamiltonian circuits in proper interval graphs // Information Processing Letters. — 1983. — Т. 17, вип. 2 (21 квітня). — С. 97–101. — DOI: .
- Panda B. S., Das S. K. A linear time recognition algorithm for proper interval graphs // Information Processing Letters. — 2003. — Т. 87, вип. 3 (21 квітня). — С. 153–161. — DOI: .
- Michael von Rimscha. Reconstructibility and perfect graphs // Discrete Mathematics. — 1983. — Т. 47, вип. 2-3 (21 квітня). — С. 283–291. — DOI: .
- Jon L. Bentley, Donald F. Stanat, E. Hollins Williams, Jr. The complexity of finding fixed-radius near neighbors // Information Processing Letters. — 1977. — Т. 6, вип. 6 (21 квітня). — С. 209–212. — DOI: .
- Derek G. Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, Alan P. Sprague. Simple linear time recognition of unit interval graphs // Information Processing Letters. — 1995. — Т. 55, вип. 2 (21 квітня). — С. 99–104. — DOI: .
- Celina M. Herrera de Figueiredo, João Meidanis, Célia Picinin de Mello. A linear-time algorithm for proper interval graph recognition // Information Processing Letters. — 1995. — Т. 56, вип. 3 (21 квітня). — С. 179–184. — DOI: .
- Derek G. Corneil. A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs // Discrete Applied Mathematics. — 2004. — Т. 138, вип. 3 (21 квітня). — С. 371–379. — DOI: .
- Pavol Hell, Jing Huang. Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs // SIAM Journal on Discrete Mathematics. — 2004. — Т. 18, вип. 3 (21 квітня). — С. 554–570. — DOI: .
- J. Mark Keil. Finding Hamiltonian circuits in interval graphs // Information Processing Letters. — 1985. — Т. 20, вип. 4 (21 квітня). — С. 201–206. — DOI: .
- Louis Ibarra. A simple algorithm to find Hamiltonian cycles in proper interval graphs // Information Processing Letters. — 2009. — Т. 109, вип. 18 (21 квітня). — С. 1105–1108. — DOI: .
- Dániel Marx. Precoloring extension on unit interval graphs // Discrete Applied Mathematics. — 2006. — Т. 154, вип. 6 (21 квітня). — С. 995–1002. — DOI: .
- Fred S. Roberts. On nontransitive indifference // Journal of Mathematical Psychology. — 1970. — Т. 7 (21 квітня). — С. 243–258. — DOI: .
- Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, Ron Shamir. Four strikes against physical mapping of DNA // Journal of Computational Biology. — 2009. — Т. 2, вип. 2 (21 квітня). — DOI: . — PMID 7497116 .
Посилання[ред. | ред. код]
- Information System on Graph Class Inclusions [Архівовано 3 травня 2021 у Wayback Machine.]: unit interval graph [Архівовано 6 травня 2021 у Wayback Machine.]