График сопоставимости - Comparability graph

В теория графов, а график сопоставимости является неориентированный граф который соединяет пары элементов, которые сопоставимый друг к другу в частичный заказ. Графы сопоставимости также называются транзитивно ориентируемые графы, частично упорядочиваемые графики, графики сдерживания,[1] и графы делителей.[2]An граф несравнимости является неориентированный граф который соединяет пары элементов, которые не сопоставимый друг к другу в частичный заказ.

Определения и характеристика

Диаграмма Хассе чугуна (слева) и его граф сопоставимости (справа)
Один из запрещенных индуцированных подграфов графа сравнимости. Обобщенный цикл а–б–d–ж–d–c–е–c–б–а в этом графе имеет нечетную длину (девять), но не имеет треугольных хорд.

Для любого строгий частично упорядоченный набор (S, <), график сопоставимости из (S, <) - граф (S, ⊥), вершины которых являются элементами S а ребра - это те пары {ты, v} таких элементов, что ты < v. То есть для частично упорядоченного набора возьмем ориентированный ациклический граф, подать заявление переходное закрытие и удалите ориентацию.

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

Любой конечный частичный порядок можно представить как семейство множеств, таких что Икс < у в частичном порядке всякий раз, когда набор, соответствующий Икс является подмножеством множества, соответствующего у. Таким образом можно показать, что графы сопоставимости эквивалентны графам включения семейств множеств; то есть граф с вершиной для каждого набора в семействе и ребром между двумя наборами, если одно из них является подмножеством другого.[4]В качестве альтернативы можно представить частичный порядок семейством целые числа, так что Икс < у всякий раз, когда целое число, соответствующее Икс это делитель целого числа, соответствующего у. Из-за этой конструкции графы сравнимости также называются графами делителей.[2]

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

Связь с другими семействами графов

Каждый полный график является графом сопоставимости, граф сопоставимости общий заказ. Все ациклические ориентации полного графа транзитивны. Каждый двудольный граф также является графиком сопоставимости. Ориентация ребер двудольного графа от одной стороны двудольного графа к другой приводит к транзитивной ориентации, соответствующей частичному порядку высоты два. В качестве Сеймур (2006) отмечает, что каждый граф сравнимости, который не является ни полным, ни двудольным, имеет перекос раздела.

В дополнять любой интервальный график - график сопоставимости. Отношение сопоставимости называется интервальный порядок. Графы интервалов - это именно те графы, которые являются хордовыми и имеют дополнения к графам сопоставимости.[7]

А граф перестановок является графом включения на множестве интервалов.[8] Следовательно, графы перестановок - это еще один подкласс графов сопоставимости.

В тривиально совершенные графы графики сопоставимости укоренившиеся деревья.[9]Кографы можно охарактеризовать как графики сопоставимости последовательно-параллельные частичные порядки; таким образом, кографы также являются графами сопоставимости.[10]

Графики пороговых значений - еще один особый вид графа сопоставимости.

Каждый график сопоставимости идеально. Совершенство графиков сопоставимости Теорема Мирского, и совершенство их дополнений Теорема Дилворта; эти факты вместе с теорема о совершенном графе может использоваться для доказательства теоремы Дилворта из теоремы Мирского или наоборот.[11] В частности, графики сопоставимости идеально упорядочиваемые графики, подкласс совершенных графов: a жадная окраска алгоритм для топологический порядок переходной ориентации графа оптимально их раскрасит.[12]

В дополнять каждого графа сопоставимости строковый граф.[13]

Алгоритмы

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

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

Примечания

  1. ^ Голумбик (1980), п. 105; Brandstädt, Le & Spinrad (1999), п. 94.
  2. ^ а б Chartrand et al. (2001).
  3. ^ Гуила-Хури (1962); видеть Brandstädt, Le & Spinrad (1999), теорема 1.4.1, с. 12. Хотя ориентации, исходящие из частичных заказов, ациклический, необязательно включать ацикличность в качестве условия этой характеристики.
  4. ^ Уррутия (1989); Троттер (1992); Brandstädt, Le & Spinrad (1999), раздел 6.3, стр. 94–96.
  5. ^ Гуила-Хури (1962) и Гилмор и Хоффман (1964). Смотрите также Brandstädt, Le & Spinrad (1999), теорема 6.1.1, с. 91.
  6. ^ Галлай (1967); Троттер (1992); Brandstädt, Le & Spinrad (1999), п. 91 и стр. 112.
  7. ^ Транзитивная ориентируемость дополнений интервальных графов доказана Гуила-Хури (1962); характеристика интервальных графиков обусловлена Гилмор и Хоффман (1964). Смотрите также Голумбик (1980), опора. 1.3. С. 15–16.
  8. ^ Душник и Миллер (1941). Brandstädt, Le & Spinrad (1999), теорема 6.3.1, с. 95.
  9. ^ Brandstädt, Le & Spinrad (1999), теорема 6.6.1, с. 99.
  10. ^ Brandstädt, Le & Spinrad (1999), следствие 6.4.1, с. 96; Юнг (1978).
  11. ^ Голумбик (1980), теоремы 5.34 и 5.35, с. 133.
  12. ^ Маффрей (2003).
  13. ^ Голумбик, Ротем и Уррутия (1983) и Ловас (1983). Смотрите также Фокс и Пач (2012).
  14. ^ МакКоннелл и Спинрад (1997); видеть Brandstädt, Le & Spinrad (1999), п. 91.

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

  • Брандштадт, Андреас; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор, Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-X.
  • Чартран, Гэри; Мунтян, Ралука; Саенфольфат, Варапорн; Чжан, Пин (2001), «Какие графы являются графами делителей?», Труды Тридцать второй Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Лос-Анджелес, 2001), Congressus Numerantium, 151: 189–200, МИСТЕР  1887439
  • Душник, Бен; Миллер, Э. У. (1941), "Частично упорядоченные множества", Американский журнал математики, Издательство Университета Джона Хопкинса, 63 (3): 600–610, Дои:10.2307/2371374, HDL:10338.dmlcz / 100377, JSTOR  2371374, МИСТЕР  0004862.
  • Fox, J .; Пах, Дж. (2012), «Строковые графики и графики несравнимости» (PDF), Успехи в математике, 230 (3): 1381–1401, Дои:10.1016 / j.aim.2012.03.011.
  • Галлай, Тибор (1967), "Transitiv orientierbare Graphen", Acta Math. Акад. Sci. Подвешенный., 18: 25–66, Дои:10.1007 / BF02020961, МИСТЕР  0221974.
  • Гуила-Ури, Ален (1962), "Caractérisation des graphes non orientés dont on peut orienter les arretes de manière à obtenir le graphe d'une Relations d'ordre", Les Comptes rendus de l'Académie des Sciences, 254: 1370–1371, МИСТЕР  0172275.
  • Gilmore, P.C .; Хоффман, А. Дж. (1964), "Характеристика графов сопоставимости и интервальных графов", Канадский математический журнал, 16: 539–548, Дои:10.4153 / CJM-1964-055-5, МИСТЕР  0175811.
  • Голумбик, Мартин Чарльз (1980), Алгоритмическая теория графов и совершенные графы, Academic Press, ISBN  0-12-289260-7.
  • Golumbic, M .; Rotem, D .; Уррутия, Дж. (1983), «Графы сопоставимости и графы пересечений», Дискретная математика, 43 (1): 37–46, Дои:10.1016 / 0012-365X (83) 90019-5.
  • Юнг, Х.А. (1978), "Об одном классе множеств и соответствующих графах сопоставимости", Журнал комбинаторной теории, серия B, 24 (2): 125–133, Дои:10.1016/0095-8956(78)90013-8, МИСТЕР  0491356.
  • Ловас, Л. (1983), «Совершенные графы», Избранные темы теории графов, 2, Лондон: Academic Press, стр. 55–87..
  • Маффре, Фредерик (2003), «О раскраске совершенных графов», в Рид, Брюс А.; Продажи, Клаудия Л. (ред.), Последние достижения в области алгоритмов и комбинаторики, Книги CMS по математике, 11, Springer-Verlag, стр. 65–84, Дои:10.1007/0-387-22444-0_3.
  • McConnell, R.M .; Спинрад, Дж. (1997), "Линейно-временная транзитивная ориентация", 8-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 19–25.
  • Сеймур, Пол (2006), «Как было найдено доказательство сильной гипотезы о совершенном графе» (PDF), Gazette des Mathématiciens (109): 69–83, МИСТЕР  2245898.
  • Троттер, Уильям Т. (1992), Комбинаторика и частично упорядоченные множества - теория размерностей, Издательство Университета Джона Хопкинса.
  • Уррутия, Хорхе (1989), Соперник, И. (ред.), Частичные порядки и евклидова геометрия, Kluwer Academic Publishers, стр. 327–436..