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

В теории графов граф сравнимости — это неориентированный граф , соединяющий пары элементов, сравнимых друг с другом в частичном порядке . Графы сравнимости также называются транзитивно ориентируемыми графами , частично упорядочиваемыми графами , графами включения . и графы делителей . Граф несравнимости — это неориентированный граф элементов , соединяющий пары несопоставимых друг с другом в частичном порядке .

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

Диаграмма Хассе частичного множества (слева) и его граф сравнимости (справа)

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

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

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

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

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

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

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

Дополнением интервального любого графа является граф сравнимости. Отношение сравнимости называется интервальным порядком . Интервальные графы — это именно хордальные графы, имеющие дополнения к графам сравнимости.

Граф перестановок — это граф включения на множестве интервалов. Следовательно, графы перестановок являются еще одним подклассом графов сравнимости.

Тривиально совершенные графы — это графы сравнимости корневых деревьев . Кографы можно охарактеризовать как графы сравнимости последовательно-параллельных частичных порядков ; таким образом, кографы также являются графами сравнимости.

Пороговые графики — это еще один особый вид графов сопоставимости.

Любой граф сравнимости совершенен . Совершенство графов сравнимости — теорема Мирского , а совершенство их дополнений — теорема Дилворта ; эти факты вместе с теоремой об идеальном графике могут быть использованы для доказательства теоремы Дилворта из теоремы Мирского или наоборот. Более конкретно, графы сравнимости — это идеально упорядочиваемые графы , подкласс идеальных графов: жадный алгоритм раскраски для топологического упорядочения транзитивной ориентации графа оптимально раскрасит их.

Дополнением строковый каждого графа сравнимости является граф .

Алгоритмы

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

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

См. также

• Связанный граф , другой граф, определенный из частичного порядка.

Ссылки

• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-Х .
• Шартран, Гэри ; Мунтян, Ралука; Саенфолфат, Варапорн; Чжан, Пин (2001), «Какие графы являются графами делителей?», Труды Тридцать второй Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Луизиана, 2001), Congressus Numerantium , 151 : 189–200, МР   1887439
• Душник, Бен; Миллер, EW (1941), «Частично упорядоченные множества», American Journal of Mathematics , 63 (3), The Johns Hopkins University Press: 600–610, doi : 10.2307/2371374 , hdl : 10338.dmlcz/100377 , JSTOR   2371374 , МР   0004862 .
• Фокс, Джейкоб; Пах, Янош (2012), «Струнные графы и графы несравнимости» (PDF) , Advance in Mathematics , 230 (3): 1381–1401, doi : 10.1016/j.aim.2012.03.011 .
• Галлай, Тибор (1967), «Transitiv orientierbare Graphen», Acta Math. акад. наук. Хунг. , 18 (1–2): 25–66, doi : 10.1007/BF02020961 , MR   0221974 , S2CID   119485995 .
• Гуила-Ури, Ален (1962), «Характеризация неориентированных графов, ребра которых могут быть ориентированы так, чтобы получить график отношения порядка», Les Comptes Rends de l'Académie des Sciences , 254 : 1370–1371, MR   0172275 .
• Гилмор, ПК; Хоффман, AJ (1964), «Характеристика графиков сопоставимости и интервальных графиков», Canadian Journal of Mathematics , 16 : 539–548, doi : 10.4153/CJM-1964-055-5 , MR   0175811 .
• Голумбик, Мартин Чарльз (1980), алгоритмическая теория графов и совершенные графы , Academic Press, ISBN  0-12-289260-7 .
• Голуббич, М.; Ротем, Д.; Уррутиа, Дж. (1983), «Графы сопоставимости и графы пересечений», Discrete Mathematics , 43 (1): 37–46, doi : 10.1016/0012-365X(83)90019-5 .
• Юнг, Х.А. (1978), «Об одном классе частично упорядоченных множеств и соответствующих графах сравнимости», Журнал комбинаторной теории, серия B , 24 (2): 125–133, doi : 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 .
• МакКоннелл, РМ; Спинрад, Дж. (1997), «Транзивная ориентация в линейном времени», 8-й симпозиум ACM-SIAM по дискретным алгоритмам , стр. 19–25 .
• Сеймур, Пол (2006), «Как было найдено доказательство сильной гипотезы о совершенном графе» (PDF) , Gazette des Mathématiciens (109): 69–83, MR   2245898 .
• Троттер, Уильям Т. (1992), Комбинаторика и частично упорядоченные множества — теория размерности , Издательство Университета Джонса Хопкинса .
• Уррутия, Хорхе (1989), «Частичные порядки и евклидова геометрия», в Rival, I. (редактор), «Алгоритмы и порядок» , Kluwer Academic Publishers, стр. 327–436, doi : 10.1007/978-94-009-2639 -4 .