В теорії графів граф порівнянності — це неорієнтований граф, у якому пари елементів з'єднано ребром, якщо ці елементи в деякому частковому порядку. Графи порівнянності також називають транзитивно-орієнтованими графами, частково впорядковуваними графами і графами вкладеності, стор. 105; , стор. 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.. Однак алгоритм, який це робить, визначає орієнтацію для будь-якого графа, так що для завершення задачі перевірки, чи є граф графом порівнянності, потрібно перевірити, чи є орієнтація транзитивною, що за складністю еквівалентне множенню матриць.

Оскільки графи порівнянності досконалі, багато задач, складні для загальніших класів графів, зокрема розфарбовування графів і задача про незалежну множину, для графів порівнянності можна розв'язати за поліноміальний час.

Див. також Тривіально досконалий граф

Примітки

Посилання