В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы в некотором частичном порядке. Графы сравнимости также называют транзитивно-ориентируемыми графами, частично упорядочиваемыми графами и графами вложенности, p. 105; , p. 94..Граф несравнимости — это неориентированный граф, в котором пары элементов соединяются ребром, если элементы несравнимы в некотором частичном порядке.
Определения и характеристики
Для любого частично строгоупорядоченного множества (S,<), граф сравнимости (S, <) — это граф (S, ⊥), вершины которого — элементы S, а рёбра — это пары {u, v} элементов, таких что u < v. Таким образом, для частично упорядоченных множеств берём ориентированный ациклический граф, используем транзитивное замыкание и удаляем ориентацию.
Также, граф сравнимости — это граф, имеющий транзитивную ориентацию'; см. , теорема 1.4.1, стр. 12. Хотя ориентация, порождённая частичным порядком не циклична, нет необходимости включать условие отсутствия циклов, имеющий ориентацию рёбер графа такую, что отношение смежности полученного ориентированного графа является транзитивным — если существуют дуги (x,y) и (y,z), должна существовать дуга (x,z).
Можно представить частично упорядоченное множество, как семейство множеств таких, что x < y в частичном порядке, если соответствующее x множество является подмножеством соответствующего y множества. Таким образом, можно показать, что граф сравнимости эквивалентен графу вложенности семейства множеств, то есть графу, вершинами которого служат множества семейства, а рёбра соединяют вершины, если одно из множеств содержится в другом; ; , секция 6.3, стр. 94—96..
Также и . См. также , теорема 6.1.1, стр. 91. граф сравнимости — это граф, в котором для любого обобщённого цикла нечётной длины можно найти ребро (x,y), соединяющее две вершины, находящиеся на расстоянии два в цикле. Такие рёбра называются хордами триангуляции''. В этом контексте обобщённые циклы являются замкнутым обходом, который проходит каждое ребро графа не более одного раза в каждом направлении.
Граф сравнимости можно описать также заданием запрещённых подграфов; ; , стр. 91 и 112..
Связь с другими семействами графов Любой полный граф является графом сравнимости, графом сравнимости линейно упорядоченного множества. Все ациклические ориентации в полном графе транзитивны. Любой двудольный граф также является графом сравнимости. Ориентация рёбер двудольного графа с одной стороны на другую приводит к транзитивной ориентации, соответствующей частичному порядку высотой два. Как заметил Сеймур , любой граф сравнимости, не являющийся ни полным, ни двудольным, имеет .
Дополнение любого интервального графа является графом сравнимости. Интервальные графы — это в точности хордальные графы, имеющие графы сравнимости в качестве дополненийТранзитивная ориентируемость дополнений интервальных графов была доказана Гойла-Хоури ; характеризацию интервальных графов можно найти у Гилмора и Хофмана . См. также Голумбика , предложение. 1.3, страницы. 15—16..
Граф перестановки — это граф вложенности множества интервалов. , теорема 6.3.1, стр. 95.. Таким образом, графы перестановок — это ещё один класс графов сравнимости.
Тривиально совершенные графы — это графы сравнимости корневых деревьев, теорема 6.6.1, стр. 99.. Кографы можно охарактеризовать как графы сравнимости параллельно-последовательных частичных порядков. Таким образом, кографы тоже являются графами сравнимости, следствие 6.4.1, стр. 96; ..
Любой граф сравнимости является совершенным. Совершенство графов сравнимости — это теорема Мирского, а совершенство их дополнений — теорема Дилуорса. Эти факты, вместе со свойством двойственности совершенных графов, можно использовать для доказательства теоремы Дилуорса из теоремы Мирского и наоборот, теоремы 5.34 и 5.35, стр. 133.. Точнее, графы сравнимости являются вполне упорядочиваемыми графами, последние являются подклассом совершенных графов — алгоритм жадной раскраски для топологической сортировки транзитивной ориентации графа раскрашивает его оптимально.
Дополнение любого графа сравнимости является струнным графом и . См. также ..
Алгоритмы Транзитивная ориентация графа, если она существует, может быть найдена за линейное время; см. , стр. 91.. Однако алгоритм, который это делает, определяет ориентацию для любого графа, так что для завершения задачи проверки, является ли граф графом сравнимости, нужно проверить, является ли ориентация транзитивной, что по сложности эквивалентно умножению матриц.
Поскольку графы сравнимости совершенны, многие задачи, сложные для более общих классов графов, включая раскраску графов и задачу о независимом множестве, для графов сравнимости можно решить за полиномиальное время.
Примечания
Ссылки
Категория:Совершенные графы