В теории графов граф сравнимости — это неориентированный граф , который соединяет пары элементов, сравнимых друг с другом в частичном порядке . Графы сравнимости также называются транзитивно ориентируемыми графами , частично упорядочиваемыми графами , графами включения , [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] Однако алгоритм для этого назначит ориентации ребрам любого графа, поэтому для завершения задачи проверки того, является ли граф графом сравнимости, необходимо проверить, является ли полученная ориентация транзитивной, что по сложности доказуемо эквивалентно умножению матриц .
Поскольку графы сравнимости являются идеальными, многие задачи, которые сложны для более общих классов графов, включая раскраску графов и задачу о независимом множестве , могут быть решены за полиномиальное время для графов сравнимости.