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

Граф пересечения единичных интервалов на числовой прямой

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

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

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

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

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

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

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

Характеристики

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

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

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

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

Графы безразличия подчиняются гипотезе реконструкции : они однозначно определяются своими подграфами с удаленными вершинами. ^[15]

Алгоритмы

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

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

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

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

Приложения

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

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

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

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

Ссылки

1. Робертс, Фред С. (1969), «Графы безразличия», Методы доказательства в теории графов (Труды Второй конференции по теории графов в Энн-Арборе, Энн-Арбор, Мичиган, 1968) , Academic Press, Нью-Йорк, стр. 139–146, MR  0252267.
2. Bogart, Kenneth P.; West, Douglas B. (1999), "Краткое доказательство того, что "собственное = единица"", Дискретная математика , 201 (1–3): 21–23, arXiv : math/9811036 , doi :10.1016/S0012-365X(98)00310-0, MR  1687858.
3. Вегнер, Г. (1967), Eigenschaften der Nerven homoologisch-einfacher Familien im R ⁿ , Ph.D. диссертация, Геттинген, Германия: Геттингенский университет. Как цитируют Хелл и Хуан (2004).
4. Looges, Peter J.; Olariu, Stephan (1993), «Оптимальные жадные алгоритмы для графов безразличия», Computers & Mathematics with Applications , 25 (7): 15–25, doi : 10.1016/0898-1221(93)90308-I , MR  1203643.
5. Яцковский, Зигмунт (1992), «Новая характеристика правильных интервальных графов», Дискретная математика , 105 (1–3): 103–109, doi : 10.1016/0012-365X(92)90135-3 , MR  1180196.
6. Gutierrez, M.; Oubiña, L. (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. Мерциос, Джордж Б. (2008), «Матричная характеристика интервальных и правильных интервальных графов», Applied Mathematics Letters , 21 (4): 332–337, doi :10.1016/j.aml.2007.04.001, MR  2406509.
8. Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Корневые ориентированные графы путей являются степенями листьев", Discrete Mathematics , 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 , MR  0676708.
10. Каплан, Хаим; Шамир, Рон (1996), «Проблемы ширины пути, пропускной способности и завершения для правильных интервальных графов с малыми кликами», SIAM Journal on Computing , 25 (3): 540–561, doi :10.1137/S0097539793258143, MR  1390027.
11. Golumbic, Martin Charles ; Rotics, Udi (1999), «Ширина клики графов единичных интервалов не ограничена», Труды Тридцатой юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1999) , Congressus Numerantium, т. 140, стр. 5–17, MR  1745205.
12. Лозин, Вадим В. (2008), "От ширины дерева к ширине клики: исключая граф единичного интервала", Алгоритмы и вычисления , Lecture Notes in Comput. Sci., т. 5369, Springer, Берлин, стр. 871–882, doi :10.1007/978-3-540-92182-0_76, MR  2539978.
13. Bertossi, Alan A. (1983), «Поиск гамильтоновых цепей в правильных интервальных графах», Information Processing Letters , 17 (2): 97–101, doi :10.1016/0020-0190(83)90078-9, MR  0731128.
14. Panda, BS; Das, Sajal K. (2003), "Линейный алгоритм распознавания времени для правильных интервальных графиков", Information Processing Letters , 87 (3): 153–161, doi :10.1016/S0020-0190(03)00298-9, MR  1986780.
15. фон Римша, Михаэль (1983), «Восстанавливаемость и совершенные графы», Дискретная математика , 47 (2–3): 283–291, doi : 10.1016/0012-365X(83)90099-7 , MR  0724667.
16. Бентли, Джон Л .; Станат, Дональд Ф.; Уильямс, Э. Холлинс-младший (1977), «Сложность поиска близких соседей с фиксированным радиусом», Information Processing Letters , 6 (6): 209–212, doi :10.1016/0020-0190(77)90070-9, MR  0489084.
17. Корнейл, Дерек Г.; Ким, Хирионг; Натараджан, Шридхар; Олариу, Стефан; Спраг, Алан П. (1995), «Простое линейное распознавание времени графиков единичных интервалов», Information Processing Letters , 55 (2): 99–104, CiteSeerX 10.1.1.39.855 , doi :10.1016/0020-0190(95)00046-F, MR  1344787 .
18. Эррера де Фигейредо, Селина М.; Мейданис, Жуан; Пичинин де Мелло, Селия (1995), «Алгоритм с линейным временем для правильного распознавания интервальных графиков», Information Processing Letters , 56 (3): 179–184, doi : 10.1016/0020-0190(95)00133-W, MR  1365411.
19. Корнейл, Дерек Г. (2004), «Простой алгоритм LBFS с тремя проходами для распознавания графиков единичных интервалов», Дискретная прикладная математика , 138 (3): 371–379, doi : 10.1016/j.dam.2003.07.001 , MR  2049655.
20. Хелл, Павол ; Хуан, Цзин (2004), «Сертификация алгоритмов распознавания LexBFS для правильных интервальных графов и правильных интервальных биграфов», SIAM Journal on Discrete Mathematics , 18 (3): 554–570, doi :10.1137/S0895480103430259, MR  2134416.
21. Кейл, Дж. Марк (1985), «Поиск гамильтоновых цепей в интервальных графах», 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), «Расширение предварительной раскраски на графах единичных интервалов», Дискретная прикладная математика , 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. Голдберг, Пол В.; Голумбик, Мартин К.; Каплан, Хаим; Шамир, Рон (2009), «Четыре удара против физического картирования ДНК», Журнал вычислительной биологии , 2 (2), doi :10.1089/cmb.1995.2.139, PMID  7497116.

Внешние ссылки

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