Индифферентный граф

Индифферентный граф, образованный на множестве точек на вещественной прямой путём соединения пар, расстояние между которыми не превосходит единицы

Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицу^[1]. Индифферентные графы являются также графами пересечений множеств единичных отрезков или интервалов с определённым свойством вложения (никакой интервал не содержит какой-либо другой). Основываясь на этих двух типах интервальных представлений, эти графы называются также графами единичных отрезков или собственными интервальными графами. Индифферентные графы образуют подкласс интервальных графов.

Эквивалентные описания

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

Конечные индифферентные графы можно эквивалентно описать как

• Графы пересечений единичных отрезков^[1]
• Графы пересечений множеств интервалов, никакие два из которых не вложены друг в друга^[1][2]
• Интервальные графы без клешней^[1][2]
• Графы, не содержащие порождённых подграфов, изоморфных клешне K_1,3, «сети» (треугольника с тремя дополнительными вершинами, присоединёнными к каждой вершине треугольника), «солнцу» (треугольнику с тремя присоединёнными треугольниками, имеющими общие рёбра с центральным треугольником), или «дыры» (циклы длины четыре и более)^[3]
• Графы несравнимости полупорядков^{[англ.][1]}
• Неориентированные графы, которые имеют линейный порядок, такой, что для каждого пути из трёх вершин ${\displaystyle uvw}$, вершины которого упорядочены ${\displaystyle u}$–${\displaystyle v}$–${\displaystyle w}$, конечные вершины ${\displaystyle u}$ и ${\displaystyle w}$ смежны ^[4]
• Графы, не имеющие астральных троек, трёх вершин, соединённых попарно путями, не проходящими через третью вершину, а также не содержащие двух смежных вершин, одновременно смежных вершине из окрестности третьей вершины ^[5].
• Графы, в которых каждая компонента содержит путь, в котором каждая клика компоненты образует непрерывный подпуть^[6]
• Графы, вершины которых могут быть пронумерованы таким образом, что любой кратчайший путь образует монотонную последовательность^[6]
• Графы, матрицы смежности которых могут быть упорядочены так, что в каждой строке и каждом столбце ненулевые элементы образуют непрерывные интервалы, смежные диагонали матрицы^[7]
• Порождённые подграфы степеней безхордовых путей^[8]
• Листовые степени^[англ.], имеющие листовой корень^[англ.] в виде гусеницы^[8]

Для бесконечных графов некоторые из этих определений могут дать различные графы.

Свойства

Поскольку индифферентные графы являются частным случаем интервальных графов, индифферентные графы имеют все свойства интервальных графов. В частности, они являются специальным случаем хордальных графов и совершенных графов. Эти графы являются также специальным случаем круговых графов, что неверно для интервальных графов общего вида.

В модели Эрдёша — Реньи случайных графов граф с ${\displaystyle n}$ вершины, число рёбер которого существенно меньше ${\displaystyle n^{2/3}}$, будет с большой вероятностью индифферентным графом, в то время как графы с числом рёбер, существенно большим ${\displaystyle n^{2/3}}$, с большой вероятностью не будет индифферентным графом^[9].

Ширина ленты^[англ.] произвольного графа ${\displaystyle G}$ на единицу меньше размера наибольшей клики в индифферентном графе, который содержит ${\displaystyle G}$ в качестве подграфа и выбран для минимизации размера наибольшей клики^[10]. Это свойство образует параллели, подобные связи между путевой шириной и интервальными графами, а также между древесной шириной и хордальными графами. Более слабое понятие ширины, кликовая ширина, может быть произвольно большой на индифферентных графах^[11]. Однако любой собственный подкласс индифферентных графов, не замкнутый относительно порождённых подграфов, имеет ограниченную кликовую ширину^[12].

Любой связный индифферентный граф содержит гамильтонов путь^[13]. Индифферентный граф имеет гамильтонов цикл тогда и только тогда, когда он двусвязен^[14].

Индифферентные графы удовлетворяет гипотезе о реконструкции^[англ.] — они единственным образом определяются их подграфами с удалённой вершиной^[15].

Алгоритмы

Как и с многомерными графами единичных дисков, можно преобразовать множество точек в их индифферентный граф или множество единичных отрезков в их граф единичных отрезков за линейное время, если измерять в терминах размера выходного графа. Алгоритм округляет точки (или центры интервалов) к ближайшему меньшему целому числу, использует хеш-таблицу для нахождения всех пар точек, чьи округлённые значения отличаются не более чем на единицу (задача поиска ближайшего соседа с фиксированным радиусом), и отбирает в полученном списке пары, неокруглённые значения которых находятся не далее чем на единицу друг от друга^[16].

Можно проверить, является ли данный граф индифферентным за линейное время с помощью PQ-деревьев для построения интервальных представлений графа и затем проверки, удовлетворяет ли упорядочение вершин, производное от этого представления, свойствам индифферентного графа^[4]. Можно также основать алгоритм распознавания для индифферентных графов на алгоритмах распознавания для хордального графа^[14]. Некоторые альтернативные алгоритмы распознавания за линейное время основываются на поиске в ширину или на лексикографическом поиске в ширину, а не на связи между индифферентными графами и интервальными графами^{[17][18][19][20]}.

Как только вершины отсортированы по их числовым значениям, которые описывают индифферентный граф (или по последовательности единичных отрезков в интервальном представлении), тот же самый порядок можно использовать для поиска оптимальной раскраски этих графов, чтобы решить задачу о кратчайшем пути, построения гамильтоновых путей и наибольших паросочетаний за линейное время^[4]. Гамильтонов цикл можно найти из правильного интервального графа представления за время ${\displaystyle O(n\log n)}$^[13], но если граф является входным для задачи, та же задача может быть решена за линейное время, что может быть обобщено на интервальные графы^[21][22].

Предписанная раскраска остаётся NP-полной, даже когда она ограничена индифферентными графами^[23]. Однако она является фиксированно-параметрически разрешимой^[англ.], если параметризовать по общему числу цветов на входе^[12].

Приложения

В математической психологии индифферентные графы возникают из функций полезности путём масштабирования функции так, что одна единица представляет разность в полезности достаточно малой, так что для личности единица может рассматриваться как несущественная. В этом приложении пары элементов, полезности которых достаточно велики, могут быть частично упорядочены по относительному порядку полезности, что даёт полупорядок^{[англ.] [1][24]}.

В биоинформатике задача добавления раскрашенного графа к правильно раскрашенному графу единичных отрезков может быть использована для моделирования обнаружения ложноотрицательных сборок генома ДНК из фрагментов^[25].

См.также

• Пороговый граф, a graph whose edges are determined by sums of vertex labels rather than differences of labels
• Тривиально совершенный граф, интервальные графы for which every pair of intervals is nested or disjoint rather than properly intersecting

Примечания

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–23. — doi:10.1016/S0012-365X(98)00310-0.
• Wegner G. Eigenschaften der Nerven homologisch-einfacher Familien im Rⁿ. — Göttingen, Germany: Göttingen University, 1967. — (Ph.D. thesis).. Как процитировано в Шаблон:Harnb
• Peter J. Looges, Stephan Olariu. Optimal greedy algorithms for indifference graphs // Computers & Mathematics with Applications. — 1993. — Т. 25, вып. 7. — С. 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. — С. 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. — С. 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. — С. 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. — С. 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–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. — С. 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. — С. 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. — С. 153–161. — doi:10.1016/S0020-0190(03)00298-9.
• Michael von Rimscha. Reconstructibility and perfect graphs // Discrete Mathematics. — 1983. — Т. 47, вып. 2-3. — С. 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. — С. 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. — С. 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. — С. 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. — С. 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. — С. 554–570. — doi:10.1137/S0895480103430259.
• J. Mark Keil. Finding Hamiltonian circuits in interval graphs // Information Processing Letters. — 1985. — Т. 20, вып. 4. — С. 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. — С. 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. — С. 995–1002. — doi:10.1016/j.dam.2005.10.008.
• Fred S. Roberts. On nontransitive indifference // Journal of Mathematical Psychology. — 1970. — Т. 7. — С. 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. — doi:10.1089/cmb.1995.2.139. — PMID 7497116.

Ссылки

• Information System on Graph Class Inclusions: unit interval graph