В теории графов граф сравнимости — это неориентированный граф , соединяющий пары элементов, сравнимых друг с другом в частичном порядке . Графы сравнимости также называются транзитивно ориентируемыми графами , частично упорядочиваемыми графами , графами включений [ 1] и графами делителей . [2] Граф несравнимости — это неориентированный граф , соединяющий пары элементов, не сравнимых друг с другом, в частичном порядке .
Для любого строгого частично упорядоченного множества ( S ,<) граф сравнения ( S , <) — это граф ( S , ⊥) , вершины которого являются элементами S , а ребра — теми парами { u , v } элементы такие, что u < v . То есть для частично упорядоченного набора возьмите ориентированный ациклический граф , примените транзитивное замыкание и удалите ориентацию.
Эквивалентно, граф сравнимости — это граф, который имеет транзитивную ориентацию , [3] назначение направлений ребрам графа (т. е. ориентацию графа) такое, что отношение смежности результирующего ориентированного графа является транзитивным : всякий раз, когда существует существуют направленные ребра ( x , y ) и ( y , z ) , должно существовать ребро ( x , z ) .
Любой конечный частичный порядок можно представить как семейство множеств, такое что x < y в частичном порядке, если набор, соответствующий x , является подмножеством набора, соответствующего y . Таким образом, можно показать, что графы сравнимости эквивалентны графам вложенности семейств множеств; то есть граф с вершиной для каждого множества в семействе и ребром между двумя множествами, если одно из них является подмножеством другого. [4] Альтернативно, можно представить частичный порядок семейством целых чисел , таким образом, что x < y всякий раз, когда целое число, соответствующее x, является делителем целого числа, соответствующего y . Из-за этой конструкции графы сравнимости также называются графами делителей. [2]
Графы сравнимости можно охарактеризовать как графы, в которых для каждого обобщенного цикла (см. ниже) нечетной длины можно найти ребро ( x , y ) , соединяющее две вершины, находящиеся на расстоянии два в цикле. Такое ребро называется треугольной хордой . В этом контексте обобщенный цикл определяется как замкнутый обход , который использует каждое ребро графа не более одного раза в каждом направлении. [5] Графы сравнимости также можно охарактеризовать списком запрещенных индуцированных подграфов . [6]
Каждый полный граф является графом сравнимости, графом сравнимости полного порядка . Все ациклические ориентации полного графа транзитивны. Любой двудольный граф также является графом сравнимости. Ориентация ребер двудольного графа от одной стороны двудольного графа к другой приводит к транзитивной ориентации, соответствующей частичному порядку высоты два. Как заметил Сеймур (2006), каждый граф сравнимости, который не является ни полным, ни двудольным, имеет косое разбиение .
Дополнением любого интервального графа является граф сравнимости. Отношение сравнимости называется интервальным порядком . Интервальные графы — это именно хордальные графы, имеющие дополнения к графам сравнимости. [7]
Граф перестановок — это граф включения на множестве интервалов. [8] Таким образом, графы перестановок являются еще одним подклассом графов сравнимости.
Тривиально совершенные графы — это графы сравнимости корневых деревьев . [9] Кографы можно охарактеризовать как графы сравнимости последовательно-параллельных частичных порядков ; таким образом, кографы также являются графами сравнимости. [10]
Пороговые графики — это еще один особый вид графов сопоставимости.
Любой граф сравнимости совершенен . Совершенство графов сравнимости — теорема Мирского , а совершенство их дополнений — теорема Дилворта ; эти факты вместе с теоремой об идеальном графике могут быть использованы для доказательства теоремы Дилворта из теоремы Мирского или наоборот. [11] Точнее, графы сравнимости — это идеально упорядочиваемые графы , подкласс идеальных графов: жадный алгоритм раскраски для топологического упорядочения транзитивной ориентации графа оптимально раскрасит их. [12]
Дополнением каждого графа сравнимости является строковый граф . [13]
Транзитивную ориентацию графа, если она существует, можно найти за линейное время. [14] Однако алгоритм для этого присваивает ориентации ребрам любого графа, поэтому для выполнения задачи проверки того, является ли граф графом сравнимости, необходимо проверить, является ли результирующая ориентация транзитивной, - проблема, доказуемо эквивалентная в сложность умножения матриц .
Поскольку графы сравнимости совершенны, многие проблемы, которые сложны для более общих классов графов, включая раскраску графов и проблему независимого множества , могут быть решены за полиномиальное время для графов сопоставимости.