График безразличия - Indifference graph

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

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

Эквивалентные характеристики

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

Конечные графы безразличия могут быть эквивалентно охарактеризованы как

  • В графы пересечений из единичные интервалы,[1]
  • Графы пересечений наборов интервалов, два из которых не являются вложенными (один содержит другой),[1][2]
  • В без когтей интервальные графики,[1][2]
  • Графики, не имеющие индуцированный подграф изоморфен коготь K1,3, net (треугольник с вершиной степени один, примыкающей к каждой из вершин треугольника), sun (треугольник, окруженный тремя другими треугольниками, каждый из которых имеет одно ребро с центральным треугольником) или hole (цикл длиной четыре или более) ,[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]

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

Приложения

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

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

Смотрите также

Рекомендации

  1. ^ а б c d е ж Робертс, Фред С. (1969), «Графы безразличия», Методы доказательства в теории графов (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 139–146, МИСТЕР  0252267.
  2. ^ а б Bogart, Kenneth P .; Уэст, Дуглас Б. (1999), "Краткое доказательство того, что" собственное = единица"", Дискретная математика, 201 (1–3): 21–23, arXiv:математика / 9811036, Дои:10.1016 / S0012-365X (98) 00310-0, МИСТЕР  1687858.
  3. ^ Вегнер, Г. (1967), Eigenschaften der Nerven homologisch-einfacher Familien im рп, Кандидат наук. дипломная работа, Геттинген, Германия: Геттингенский университет. Как цитирует Ад и Хуанг (2004).
  4. ^ а б c Looges, Питер Дж .; Олариу, Стефан (1993), "Оптимальные жадные алгоритмы для графов безразличия", Компьютеры и математика с приложениями, 25 (7): 15–25, Дои:10.1016 / 0898-1221 (93) 90308-И, МИСТЕР  1203643.
  5. ^ Jackowski, Zygmunt (1992), "Новая характеристика собственных интервальных графов", Дискретная математика, 105 (1–3): 103–109, Дои:10.1016 / 0012-365X (92) 90135-3, МИСТЕР  1180196.
  6. ^ а б Gutierrez, M .; Обинья, Л. (1996), "Метрические характеристики собственных интервальных графов и графов древовидных клик", Журнал теории графов, 21 (2): 199–205, Дои:10.1002 / (SICI) 1097-0118 (199602) 21: 2 <199 :: AID-JGT9> 3.0.CO; 2-M, МИСТЕР  1368745.
  7. ^ Мерциос, Джордж Б. (2008), "Матричная характеристика интервальных и собственных интервальных графов", Письма по прикладной математике, 21 (4): 332–337, Дои:10.1016 / j.aml.2007.04.001, МИСТЕР  2406509.
  8. ^ а б Брандштадт, Андреас; Хундт, Кристиан; Манчини, Федерико; Вагнер, Питер (2010), «Графы ориентированных путей с корнем являются листовыми степенями», Дискретная математика, 310: 897–910, Дои:10.1016 / j.disc.2009.10.006.
  9. ^ Коэн, Джоэл Э. (1982), «Асимптотическая вероятность того, что случайный граф является графом единичных интервалов, графом безразличия или правильным графом интервалов», Дискретная математика, 40 (1): 21–24, Дои:10.1016 / 0012-365X (82) 90184-4, МИСТЕР  0676708.
  10. ^ Каплан, Хаим; Шамир, Рон (1996), «Проблемы с пропускной способностью, пропускной способностью и завершением для правильных интервальных графов с небольшими кликами», SIAM Журнал по вычислениям, 25 (3): 540–561, Дои:10.1137 / S0097539793258143, МИСТЕР  1390027.
  11. ^ Голумбик, Мартин Чарльз; Ротикс, Уди (1999), "Кликовая ширина графов единичных интервалов не ограничена", Труды тридцатой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1999), Congressus Numerantium, 140, стр. 5–17, МИСТЕР  1745205.
  12. ^ а б Лозин, Вадим В. (2008), «От ширины дерева к ширине клики: исключение графа единичных интервалов», Алгоритмы и вычисления, Конспект лекций по вычисл. Наук, 5369, Springer, Берлин, стр. 871–882, Дои:10.1007/978-3-540-92182-0_76, МИСТЕР  2539978.
  13. ^ а б Бертосси, Алан А. (1983), "Нахождение гамильтоновых схем в собственных интервальных графах", Письма об обработке информации, 17 (2): 97–101, Дои:10.1016/0020-0190(83)90078-9, МИСТЕР  0731128.
  14. ^ а б Panda, B.S .; Дас, Саджал К. (2003), "Алгоритм распознавания линейного времени для правильных интервальных графов", Письма об обработке информации, 87 (3): 153–161, Дои:10.1016 / S0020-0190 (03) 00298-9, МИСТЕР  1986780.
  15. ^ фон Римша, Майкл (1983), "Реконструируемость и совершенные графы", Дискретная математика, 47 (2–3): 283–291, Дои:10.1016 / 0012-365X (83) 90099-7, МИСТЕР  0724667.
  16. ^ Бентли, Джон Л.; Станат, Дональд Ф .; Уильямс, Э. Холлинс-младший (1977), "Сложность поиска ближайших соседей фиксированного радиуса", Письма об обработке информации, 6 (6): 209–212, Дои:10.1016/0020-0190(77)90070-9, МИСТЕР  0489084.
  17. ^ Корнейл, Дерек Г.; Ким, Хирён; Натараджан, Шридхар; Олариу, Стефан; Спраг, Алан П. (1995), "Простое линейное распознавание по времени графов единичных интервалов", Письма об обработке информации, 55 (2): 99–104, CiteSeerX  10.1.1.39.855, Дои:10.1016 / 0020-0190 (95) 00046-Ф, МИСТЕР  1344787.
  18. ^ Эррера де Фигейредо, Селина М .; Мейданис, Жоао; Пичинин де Мелло, Селия (1995), "Алгоритм линейного времени для правильного распознавания интервального графа", Письма об обработке информации, 56 (3): 179–184, Дои:10.1016 / 0020-0190 (95) 00133-В, МИСТЕР  1365411.
  19. ^ Корнейл, Дерек Г. (2004), "Простой алгоритм LBFS с 3 развертками для распознавания графов единичных интервалов", Дискретная прикладная математика, 138 (3): 371–379, Дои:10.1016 / j.dam.2003.07.001, МИСТЕР  2049655.
  20. ^ Ад, Павол; Хуанг, Цзин (2004), "Сертификация алгоритмов распознавания LexBFS для правильных интервальных графов и правильных интервальных биграфов", Журнал SIAM по дискретной математике, 18 (3): 554–570, Дои:10.1137 / S0895480103430259, МИСТЕР  2134416.
  21. ^ Кейл, Дж. Марк (1985), "Поиск гамильтоновых схем в интервальных графах", Письма об обработке информации, 20 (4): 201–206, Дои:10.1016 / 0020-0190 (85) 90050-Х, МИСТЕР  0801816.
  22. ^ Ибарра, Луи (2009), "Простой алгоритм для поиска гамильтоновых циклов в собственных интервальных графах", Письма об обработке информации, 109 (18): 1105–1108, Дои:10.1016 / j.ipl.2009.07.010, МИСТЕР  2552898.
  23. ^ Маркс, Даниэль (2006), "Расширение предварительной раскраски на графах единичных интервалов", Дискретная прикладная математика, 154 (6): 995–1002, Дои:10.1016 / j.dam.2005.10.008, МИСТЕР  2212549.
  24. ^ Робертс, Фред С. (1970), «О нетранзитивном безразличии», Журнал математической психологии, 7: 243–258, Дои:10.1016/0022-2496(70)90047-7, МИСТЕР  0258486.
  25. ^ Голдберг, Пол В .; Golumbic, Martin C .; Каплан, Хаим; Шамир, Рон (2009), «Четыре удара по физическому картированию ДНК», Журнал вычислительной биологии, 2 (2), Дои:10.1089 / cmb.1995.2.139, PMID  7497116.

внешняя ссылка