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

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

Эквивалентные характеристики [ править ]

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

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

  • В пересечения графиков из единичных интервалов , [1]
  • Графы пересечений наборов интервалов, два из которых не являются вложенными (один содержит другой), [1] [2]
  • В кулачковых свободных графах интервалов , [1] [2]
  • Графы, в которых нет индуцированного подграфа, изоморфного клешне K 1,3 , net (треугольник с вершиной степени один, смежной с каждой из вершин треугольника), sun (треугольник, окруженный тремя другими треугольниками, каждый из которых имеет по одному ребро с центральным треугольником) или отверстие (цикл длиной четыре или более), [3]
  • Несопоставимость графов из semiorders , [1]
  • Неориентированные графы, которые имеют такой линейный порядок , что для каждых трех вершин, упорядоченных - - , если является ребром, то также и [4]
  • Графы без астральной тройки , с тремя вершинами, попарно соединенными путями, которые избегают третьей вершины, а также не содержат двух последовательных соседей третьей вершины, [5]
  • Графы, в которых каждый компонент связности содержит путь, в котором каждая максимальная клика компонента образует непрерывный подпуть, [6]
  • Графы, вершины которых могут быть пронумерованы таким образом, что каждый кратчайший путь образует монотонную последовательность , [6]
  • Графы, матрицы смежности которых могут быть упорядочены так, что в каждой строке и каждом столбце ненулевые элементы матрицы образуют непрерывный интервал, смежный с главной диагональю матрицы. [7]
  • Индуцированные подграфы степеней бесхордовых путей. [8]
  • Эти силы листьев , имеющие корень листа , который гусеница. [8]

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

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

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

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

Внешние ссылки [ править ]

  • Информационная система по включению классов графов : граф единичных интервалов