Вікіпедія

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

вид графів

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

Індиферентний граф, утворений на множині точок на дійсній прямій з'єднанням пар, відстань між якими не перевищує 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].

Див. також ред.

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

Примітки ред.

  1. ↑ а б в г д е Roberts, 1969, с. 139–146.
  2. ↑ а б Bogart, West, 1999, с. 21–23.
  3. ↑ Wegner, 1967.
  4. ↑ а б в Looges, Olariu, 1993, с. 15–25.
  5. ↑ Jackowski, 1992, с. 103–109.
  6. ↑ а б Gutierrez, Oubiña, 1996, с. 199–205.
  7. ↑ Mertzios, 2008, с. 332–337.
  8. ↑ а б Brandstädt, Hundt, Mancini, Wagner, 2010, с. 897–910.
  9. ↑ Cohen, 1982, с. 21–24.
  10. ↑ Kaplan, Shamir, 1996, с. 540–561.
  11. ↑ Golumbic, Rotics, 1999, с. 5–17.
  12. ↑ а б Lozin, 2008, с. 871–882.
  13. ↑ а б Bertossi, 1983, с. 97–101.
  14. ↑ а б Panda, Das, 2003, с. 153–161.
  15. ↑ von Rimscha, 1983, с. 283–291.
  16. ↑ Bentley, Stanat, Williams, 1977, с. 209–212.
  17. ↑ Corneil, Kim, Natarajan, Olariu, Sprague, 1995, с. 99–104.
  18. ↑ Herrera de Figueiredo, Meidanis, Picinin de Mello, 1995, с. 179–184.
  19. ↑ Corneil, 2004, с. 371–379.
  20. ↑ Hell, Huang, 2004, с. 554–570.
  21. ↑ Keil, 1985, с. 201–206.
  22. ↑ Ibarra, 2009, с. 1105–1108.
  23. ↑ Marx, 2006, с. 995–1002.
  24. ↑ Roberts, 1970, с. 243–258.
  25. ↑ 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:10.1016/S0012-365X(98)00310-0.
  • 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:10.1016/0898-1221(93)90308-I.
  • Zygmunt Jackowski. A new characterization of proper interval graphs // Discrete Mathematics. — 1992. — Т. 105, вип. 1-3 (21 квітня). — С. 103–109. — DOI:10.1016/0012-365X(92)90135-3.
  • 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:10.1002/(SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M.
  • George B. Mertzios. A matrix characterization of interval and proper interval graphs // Applied Mathematics Letters. — 2008. — Т. 21, вип. 4 (21 квітня). — С. 332–337. — DOI:10.1016/j.aml.2007.04.001.
  • Andreas Brandstädt, Christian Hundt, Federico Mancini, Peter Wagner. Rooted directed path graphs are leaf powers // Discrete Mathematics. — 2010. — Т. 310 (21 квітня). — С. 897–910. — DOI:10.1016/j.disc.2009.10.006.
  • 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:10.1016/0012-365X(82)90184-4.
  • 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:10.1137/S0097539793258143.
  • 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:10.1007/978-3-540-92182-0_76.
  • Alan A. Bertossi. Finding Hamiltonian circuits in proper interval graphs // Information Processing Letters. — 1983. — Т. 17, вип. 2 (21 квітня). — С. 97–101. — DOI:10.1016/0020-0190(83)90078-9.
  • 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:10.1016/S0020-0190(03)00298-9.
  • Michael von Rimscha. Reconstructibility and perfect graphs // Discrete Mathematics. — 1983. — Т. 47, вип. 2-3 (21 квітня). — С. 283–291. — DOI:10.1016/0012-365X(83)90099-7.
  • 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:10.1016/0020-0190(77)90070-9.
  • 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:10.1016/0020-0190(95)00046-F.
  • 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:10.1016/0020-0190(95)00133-W.
  • 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:10.1016/j.dam.2003.07.001.
  • 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:10.1137/S0895480103430259.
  • J. Mark Keil. Finding Hamiltonian circuits in interval graphs // Information Processing Letters. — 1985. — Т. 20, вип. 4 (21 квітня). — С. 201–206. — DOI:10.1016/0020-0190(85)90050-X.
  • Louis Ibarra. A simple algorithm to find Hamiltonian cycles in proper interval graphs // Information Processing Letters. — 2009. — Т. 109, вип. 18 (21 квітня). — С. 1105–1108. — DOI:10.1016/j.ipl.2009.07.010.
  • Dániel Marx. Precoloring extension on unit interval graphs // Discrete Applied Mathematics. — 2006. — Т. 154, вип. 6 (21 квітня). — С. 995–1002. — DOI:10.1016/j.dam.2005.10.008.
  • Fred S. Roberts. On nontransitive indifference // Journal of Mathematical Psychology. — 1970. — Т. 7 (21 квітня). — С. 243–258. — DOI:10.1016/0022-2496(70)90047-7.
  • 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:10.1089/cmb.1995.2.139. — PMID 7497116 .

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Індиферентний_граф&oldid=35806182