Граф порівнянностіВ теорії графів граф порівнянності — це неорієнтований граф, у якому пари елементів з'єднано ребром, якщо ці елементи порівнянні[en] в деякому частковому порядку. Графи порівнянності також називають транзитивно-орієнтованими графами, частково впорядковуваними графами і графами вкладеності[1]. Граф непорівнянності — це неорієнтований граф, у якому пари елементів з'єднуються ребром, якщо елементи непорівнянні[en] в деякому частковому порядку. Визначення й характеристики  Для будь-якої частково строго впорядкованої множини (S, <) граф порівнянності (S, <) — це граф (S, ⊥), вершини якого — елементи S, а ребра — це пари {u, v} елементів, таких що u < v. Таким чином, для частково впорядкованих множин беремо орієнтований ациклічний граф, використовуємо транзитивне замикання і видаляємо орієнтацію. Також, граф порівнянності — це граф, який має транзитивну орієнтацію[2], тобто орієнтація його ребер така, що відношення суміжності є транзитивним — якщо існують дуги (x, y) і (y, z), повинна існувати дуга (x, z). Можна подати частково впорядковану множину, як сімейство множин таких, що x < y у частковому порядку, якщо відповідна x множина є підмножиною множини, відповідної y. Таким чином, можна показати, що граф порівнянності еквівалентний графу вкладеності сімейства множин, тобто графу, вершинами якого є множини сімейства, а ребра з'єднують вершини, якщо одна з множин міститься в іншій[3]. Також[4] граф порівнянності — це граф, у якому для будь-якого узагальненого циклу непарної довжини можна знайти ребро (x, y), яке з'єднує дві вершини, розташовані на відстані два в циклі. Такі ребра називають хордами тріангуляції. У цьому контексті узагальнені цикли є замкнутим обходом, який проходить кожне ребро графа не більше одного разу в кожному напрямку. Граф порівнянності можна описати також заданням заборонених підграфів[5]. Зв'язок з іншими сімействами графівБудь-який повний граф є графом порівнянностілінійно впорядкованої множини. Всі ациклічні орієнтації в повному графі транзитивні. Будь-який двочастковий граф також є графом порівнянності. Орієнтація ребер двочаткового графа з одного боку в інший приводить до транзитивної орієнтації, що відповідає частковому порядку висотою два. Як зауважив Сеймур (Seymour, 2006), будь-який граф порівнянності, який не є ні повним, ні двочастковим, має косий розклад. Доповнення будь-якого інтервального графа є графом порівнянності. Інтервальні графи — це точно хордальні графи, які мають доповненнями графи порівнянності[6]. Граф перестановки — це граф вкладеності множини інтервалів[7]. Таким чином, графи перестановок — це ще один клас графів порівнянності. Тривіально досконалі графи — це графи порівнянності кореневих дерев[8]. Кографи можна схарактеризувати як графи порівнянності паралельно-послідовних часткових порядків. Отже, кографи теж є графами порівнянності[9]. Будь-який граф порівнянності є досконалим. Досконалість графів порівнянності стверджує теорема Мирського[en], а досконалість їх доповнень — теорема Ділуорса. Ці факти, разом зі властивістю подвійності досконалих графів, можна використовувати для доведення теореми Ділуорса з теореми Мирського і навпаки[10]. Точніше, графи порівнянності є цілком упорядковуваними графами, останні є підкласом досконалих графів — алгоритм жадібного розфарбовування для топологічного сортування транзитивної орієнтації графа розфарбовує його оптимально[11]. Доповнення будь-якого графа порівнянності є струнним графом[12]. АлгоритмиТранзитивну орієнтацію графа, якщо вона існує, можна знайти за лінійний час[13]. Однак алгоритм, який це робить, визначає орієнтацію для будь-якого графа, так що для завершення задачі перевірки, чи є граф графом порівнянності, потрібно перевірити, чи є орієнтація транзитивною, що за складністю еквівалентне множенню матриць. Оскільки графи порівнянності досконалі, багато задач, складні для загальніших класів графів, зокрема розфарбовування графів і задача про незалежну множину, для графів порівнянності можна розв'язати за поліноміальний час. Див. такожПримітки
Посилання
|
Portal di Ensiklopedia Dunia
