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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж Робертс, Фред С. (1969), «Графики безразличия», Методы доказательства в теории графов (Труды Второй конференции по теории графов в Анн-Арборе, Анн-Арбор, Мичиган, 1968) , Academic Press, Нью-Йорк, стр. 139–146. , МР 0252267 .
^ Jump up to: Перейти обратно: ^а ^б Богарт, Кеннет П.; Уэст, Дуглас Б. (1999), «Краткое доказательство того, что «собственное = единица» », Discrete Mathematics , 201 (1–3): 21–23, arXiv : math/9811036 , doi : 10.1016/S0012-365X(98 )00310-0 , МР 1687858 .
^ Вегнер, Г. (1967), Свойства нервов гомологически простых семейств в R ^н, к.т.н. диссертация, Геттинген, Германия: Геттингенский университет . По данным Hell & Huang (2004) .
^ Jump up to: Перейти обратно: ^а ^б ^с Лугес, Питер Дж.; Олариу, Стефан (1993), «Оптимальные жадные алгоритмы для графов безразличия», Computers & Mathematics with Applications , 25 (7): 15–25, doi : 10.1016/0898-1221(93)90308-I , MR 1203643 .
^ Джековский, Зигмунт (1992), «Новая характеристика графов собственных интервалов», Discrete Mathematics , 105 (1–3): 103–109, doi : 10.1016/0012-365X(92)90135-3 , MR 1180196 .
^ Jump up to: Перейти обратно: ^а ^б Гутьеррес, М.; Обинья, Л. (1996), «Метрические характеристики правильных интервальных графов и графов древовидных клик», Journal of Graph Theory , 21 (2): 199–205, doi : 10.1002/(SICI)1097-0118(199602)21 :2<199::AID-JGT9>3.0.CO;2-M , MR 1368745 .
^ Мерциос, Джордж Б. (2008), «Матричная характеристика графиков интервалов и собственных интервалов», Applied Mathematics Letters , 21 (4): 332–337, doi : 10.1016/j.aml.2007.04.001 , MR 2406509 .
^ Jump up to: Перейти обратно: ^а ^б Брандштедт, Андреас; Хундт, Кристиан; Манчини, Федерико; Вагнер, Питер (2010), «Графы направленных путей с корнем являются степенями листьев», Discrete Mathematics , 310 : 897–910, doi : 10.1016/j.disc.2009.10.006 .
^ Коэн, Джоэл Э. (1982), «Асимптотическая вероятность того, что случайный граф представляет собой граф единичных интервалов, граф безразличия или собственный граф интервалов», Discrete Mathematics , 40 (1): 21–24, doi : 10.1016/0012- 365Х(82)90184-4 , МР 0676708 .
^ Каплан, Хаим; Шамир, Рон (1996), «Проблемы ширины пути, пропускной способности и завершения для правильных интервальных графов с небольшими кликами», SIAM Journal on Computing , 25 (3): 540–561, doi : 10.1137/S0097539793258143 , MR 1390027 .
^ Голумбик, Мартин Чарльз ; Ротикс, Уди (1999), «Ширина клики графов единичных интервалов не ограничена», Труды Тридцатой Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1999) , Congressus Numerantium, vol. 140, стр. 5–17, МР 1745205 .
^ Jump up to: Перейти обратно: ^а ^б Лозин, Вадим В. (2008), «От ширины дерева к ширине клики: исключение графа единичных интервалов», Алгоритмы и вычисления , Конспект лекций по вычислительной технике. наук, том. 5369, Springer, Berlin, стр. 871–882, doi : 10.1007/978-3-540-92182-0_76 , MR 2539978 .
^ Jump up to: Перейти обратно: ^а ^б Бертосси, Алан А. (1983), «Нахождение гамильтоновых схем в графах правильных интервалов», Information Processing Letters , 17 (2): 97–101, doi : 10.1016/0020-0190(83)90078-9 , MR 0731128 .
^ Jump up to: Перейти обратно: ^а ^б Панда, бакалавр наук; Дас, Саджал К. (2003), «Алгоритм распознавания линейного времени для правильных интервальных графиков», Information Processing Letters , 87 (3): 153–161, doi : 10.1016/S0020-0190(03)00298-9 , MR 1986780 .
^ фон Римша, Михаэль (1983), «Реконструируемость и совершенные графы», Discrete Mathematics , 47 (2–3): 283–291, doi : 10.1016/0012-365X(83)90099-7 , MR 0724667 .
^ Бентли, Джон Л .; Станат, Дональд Ф.; Уильямс, Э. Холлинз-младший (1977), «Сложность поиска ближайших соседей с фиксированным радиусом», Information Processing Letters , 6 (6): 209–212, doi : 10.1016/0020-0190(77)90070-9 , МР 0489084 .
^ Корнейл, Дерек Г .; Ким, Хирёнг; Натараджан, Шридхар; Олариу, Стефан; Спраг, Алан П. (1995), «Простое линейное распознавание графиков единичных интервалов», Information Processing Letters , 55 (2): 99–104, CiteSeerX 10.1.1.39.855 , doi : 10.1016/0020-0190(95) 00046-Ф , МР 1344787 .
^ Эррера де Фигейредо, Селина М.; Мейданис, Жуан; Пичинин де Мелло, Селия (1995), «Алгоритм с линейным временем для правильного распознавания интервальных графиков», Information Processing Letters , 56 (3): 179–184, doi : 10.1016/0020-0190(95)00133-W , MR 1365411 .
^ Корнейл, Дерек Г. (2004), «Простой алгоритм LBFS с 3 проходами для распознавания графов единичных интервалов», Discrete Applied Mathematics , 138 (3): 371–379, doi : 10.1016/j.dam.2003.07.001 , МР 2049655 .
^ Черт, Павол ; Хуанг, Цзин (2004), «Сертификация алгоритмов распознавания LexBFS для правильных интервальных графов и правильных интервальных биграфов», SIAM Journal on Discrete Mathematics , 18 (3): 554–570, doi : 10.1137/S0895480103430259 , MR 2134416 .
^ Кейл, Дж. Марк (1985), «Нахождение гамильтоновых схем в интервальных графах», Information Processing Letters , 20 (4): 201–206, doi : 10.1016/0020-0190(85)90050-X , MR 0801816 .
^ Ибарра, Луи (2009), «Простой алгоритм поиска гамильтоновых циклов в правильных интервальных графах», Information Processing Letters , 109 (18): 1105–1108, doi : 10.1016/j.ipl.2009.07.010 , MR 2552898 .
^ Маркс, Даниэль (2006), «Расширение предварительной раскраски графов единичных интервалов», Discrete Applied Mathematics , 154 (6): 995–1002, doi : 10.1016/j.dam.2005.10.008 , MR 2212549 .
^ Робертс, Фред С. (1970), «О нетранзитивном безразличии», Журнал математической психологии , 7 : 243–258, doi : 10.1016/0022-2496(70)90047-7 , MR 0258486 .
^ Голдберг, Пол В.; Голумбик, Мартин С.; Каплан, Хаим; Шамир, Рон (2009), «Четыре удара по физическому картированию ДНК», Журнал вычислительной биологии , 2 (2), doi : 10.1089/cmb.1995.2.139 , PMID 7497116 .

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

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

[roberts-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж Робертс, Фред С. (1969), «Графики безразличия», Методы доказательства в теории графов (Труды Второй конференции по теории графов в Анн-Арборе, Анн-Арбор, Мичиган, 1968) , Academic Press, Нью-Йорк, стр. 139–146. , МР 0252267 .

[bogart-west-2] Jump up to: Перейти обратно: ^а ^б Богарт, Кеннет П.; Уэст, Дуглас Б. (1999), «Краткое доказательство того, что «собственное = единица» », Discrete Mathematics , 201 (1–3): 21–23, arXiv : math/9811036 , doi : 10.1016/S0012-365X(98 )00310-0 , МР 1687858 .

[3] Вегнер, Г. (1967), Свойства нервов гомологически простых семейств в R ^н, к.т.н. диссертация, Геттинген, Германия: Геттингенский университет . По данным Hell & Huang (2004) .

[greedy-4] Jump up to: Перейти обратно: ^а ^б ^с Лугес, Питер Дж.; Олариу, Стефан (1993), «Оптимальные жадные алгоритмы для графов безразличия», Computers & Mathematics with Applications , 25 (7): 15–25, doi : 10.1016/0898-1221(93)90308-I , MR 1203643 .

[5] Джековский, Зигмунт (1992), «Новая характеристика графов собственных интервалов», Discrete Mathematics , 105 (1–3): 103–109, doi : 10.1016/0012-365X(92)90135-3 , MR 1180196 .

[metric-6] Jump up to: Перейти обратно: ^а ^б Гутьеррес, М.; Обинья, Л. (1996), «Метрические характеристики правильных интервальных графов и графов древовидных клик», Journal of Graph Theory , 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 .

[leafroot-8] Jump up to: Перейти обратно: ^а ^б Брандштедт, Андреас; Хундт, Кристиан; Манчини, Федерико; Вагнер, Питер (2010), «Графы направленных путей с корнем являются степенями листьев», Discrete Mathematics , 310 : 897–910, doi : 10.1016/j.disc.2009.10.006 .

[9] Коэн, Джоэл Э. (1982), «Асимптотическая вероятность того, что случайный граф представляет собой граф единичных интервалов, граф безразличия или собственный граф интервалов», Discrete Mathematics , 40 (1): 21–24, doi : 10.1016/0012- 365Х(82)90184-4 , МР 0676708 .

[10] Каплан, Хаим; Шамир, Рон (1996), «Проблемы ширины пути, пропускной способности и завершения для правильных интервальных графов с небольшими кликами», SIAM Journal on Computing , 25 (3): 540–561, doi : 10.1137/S0097539793258143 , MR 1390027 .

[11] Голумбик, Мартин Чарльз ; Ротикс, Уди (1999), «Ширина клики графов единичных интервалов не ограничена», Труды Тридцатой Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1999) , Congressus Numerantium, vol. 140, стр. 5–17, МР 1745205 .

[lozin-12] Jump up to: Перейти обратно: ^а ^б Лозин, Вадим В. (2008), «От ширины дерева к ширине клики: исключение графа единичных интервалов», Алгоритмы и вычисления , Конспект лекций по вычислительной технике. наук, том. 5369, Springer, Berlin, стр. 871–882, doi : 10.1007/978-3-540-92182-0_76 , MR 2539978 .

[bertossi-13] Jump up to: Перейти обратно: ^а ^б Бертосси, Алан А. (1983), «Нахождение гамильтоновых схем в графах правильных интервалов», Information Processing Letters , 17 (2): 97–101, doi : 10.1016/0020-0190(83)90078-9 , MR 0731128 .

[pandas-14] Jump up to: Перейти обратно: ^а ^б Панда, бакалавр наук; Дас, Саджал К. (2003), «Алгоритм распознавания линейного времени для правильных интервальных графиков», Information Processing Letters , 87 (3): 153–161, doi : 10.1016/S0020-0190(03)00298-9 , MR 1986780 .

[15] фон Римша, Михаэль (1983), «Реконструируемость и совершенные графы», Discrete Mathematics , 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 , МР 0489084 .

[17] Корнейл, Дерек Г .; Ким, Хирёнг; Натараджан, Шридхар; Олариу, Стефан; Спраг, Алан П. (1995), «Простое линейное распознавание графиков единичных интервалов», Information Processing Letters , 55 (2): 99–104, CiteSeerX 10.1.1.39.855 , doi : 10.1016/0020-0190(95) 00046-Ф , МР 1344787 .

[18] Эррера де Фигейредо, Селина М.; Мейданис, Жуан; Пичинин де Мелло, Селия (1995), «Алгоритм с линейным временем для правильного распознавания интервальных графиков», Information Processing Letters , 56 (3): 179–184, doi : 10.1016/0020-0190(95)00133-W , MR 1365411 .

[19] Корнейл, Дерек Г. (2004), «Простой алгоритм LBFS с 3 проходами для распознавания графов единичных интервалов», Discrete Applied Mathematics , 138 (3): 371–379, doi : 10.1016/j.dam.2003.07.001 , МР 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), «Расширение предварительной раскраски графов единичных интервалов», Discrete Applied Mathematics , 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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

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