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

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

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

Эквивалентные описания[править | править код]

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

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

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

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

Свойства[править | править код]

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

В модели Эрдёша — Реньи случайных графов граф с вершины, число рёбер которого существенно меньше , будет с большой вероятностью индифферентным графом, в то время как графы с числом рёбер, существенно большим , с большой вероятностью не будет индифферентным графом[9].

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

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

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

Алгоритмы[править | править код]

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

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

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

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

Приложения[править | править код]

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

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

См.также[править | править код]

Примечания[править | править код]

  1. ↑ 1 2 3 4 5 6 Roberts, 1969, с. 139–146.
  2. ↑ 1 2 Bogart, West, 1999, с. 21–23.
  3. ↑ Wegner, 1967.
  4. ↑ 1 2 3 Looges, Olariu, 1993, с. 15–25.
  5. ↑ Jackowski, 1992, с. 103–109.
  6. ↑ 1 2 Gutierrez, Oubiña, 1996, с. 199–205.
  7. ↑ Mertzios, 2008, с. 332–337.
  8. ↑ 1 2 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. ↑ 1 2 Lozin, 2008, с. 871–882.
  13. ↑ 1 2 Bertossi, 1983, с. 97–101.
  14. ↑ 1 2 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 Rn. — 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.

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Индифферентный_граф&oldid=119930788