Граф сравнимости

В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы^[en] в некотором частичном порядке. Графы сравнимости также называют транзитивно-ориентируемыми графами, частично упорядочиваемыми графами и графами вложенности. Граф несравнимости — это неориентированный граф, в котором пары элементов соединяются ребром, если элементы несравнимы^[en] в некотором частичном порядке.

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

 

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

 

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

Граф сравнимости можно описать также заданием запрещённых подграфов.

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

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

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

Граф перестановки — это граф вложенности множества интервалов. Таким образом, графы перестановок — это ещё один класс графов сравнимости.

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

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

Дополнение любого графа сравнимости является струнным графом.

АлгоритмыПравить

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

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