Граф порівнянності — Вікіпедія
В теорії графів граф порівнянності — це неорієнтований граф, у якому пари елементів з'єднано ребром, якщо ці елементи порівнянні[en] в деякому частковому порядку. Графи порівнянності також називають транзитивно-орієнтованими графами, частково впорядковуваними графами і графами вкладеності[1]. Граф непорівнянності — це неорієнтований граф, у якому пари елементів з'єднуються ребром, якщо елементи непорівнянні[en] в деякому частковому порядку.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/29/Poset_et_graphe_de_comparabilit%C3%A9.svg/300px-Poset_et_graphe_de_comparabilit%C3%A9.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Forbidden_interval_subgraph.svg/220px-Forbidden_interval_subgraph.svg.png)
Для будь-якої частково строго впорядкованої множини (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]. Однак алгоритм, який це робить, визначає орієнтацію для будь-якого графа, так що для завершення задачі перевірки, чи є граф графом порівнянності, потрібно перевірити, чи є орієнтація транзитивною, що за складністю еквівалентне множенню матриць.
Оскільки графи порівнянності досконалі, багато задач, складні для загальніших класів графів, зокрема розфарбовування графів і задача про незалежну множину, для графів порівнянності можна розв'язати за поліноміальний час.
- ↑ Golumbic, 1980, стор. 105; Brandstädt et al, 1999, стор. 94.
- ↑ Ghouila-Houri, 1962; див. Brandstädt et al, 1999, теорема 1.4.1, стор. 12. Хоча орієнтація, породжена частковим порядком не циклічна, немає потреби включати умову відсутності циклів
- ↑ Urrutia, 1989; Trotter, 1992; Brandstädt et al, 1999, секція 6.3, стор. 94—96.
- ↑ Ghouila-Houri, 1962 и Gilmore, Hoffman, 1964. См. также Brandstädt et al, 1999, теорема 6.1.1, стор. 91.
- ↑ Gallai, 1967; Trotter, 1992; Brandstädt et al, 1999, стор. 91 і 112.
- ↑ Транзитивну орієнтовність доповнень інтервальних графів довів Гойла-Гоурі (Ghouila-Houri, 1962); характеризацію інтервальних графів можна знайти в Гілмора і Гофмана (Gilmore, Hoffman, 1964). Див. також Голумбіка (Golumbic, 1980), речення 1.3, сторінки 15—16.
- ↑ Dushnik, Miller, 1941. Brandstädt et al, 1999, теорема 6.3.1, стор. 95.
- ↑ (Brandstädt et al, 1999), теорема 6.6.1, стор. 99.
- ↑ Brandstädt et al1999, наслідок 6.4.1, стор. 96; Jung, 1978.
- ↑ Golumbic, 1980, теореми 5.34 і 5.35, стор. 133.
- ↑ Maffray, 2003.
- ↑ Golumbic, Rotem, Urrutia, 1983 і Lovász, 1983. Див. також Fox, Pach, 2009.
- ↑ McConnell, Spinrad, 1997; див. Brandstädt et al, 1999, стор. 91.
- Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — 27 серпня. — ISBN 0-89871-432-X.
- Ben Dushnik, E. W. Miller. Partially ordered sets // American Journal of Mathematics. — The Johns Hopkins University Press, 1941. — Т. 63, вип. 3 (27 серпня). — С. 600—610. — DOI: .
- J. Fox, J. Pach. String graphs and incomparability graphs. — 2009. — 27 серпня.
- Tibor Gallai. Transitiv orientierbare Graphen // Acta Math. Acad. Sci. Hung.. — 1967. — Т. 18 (27 серпня). — С. 25—66. — DOI: .
- Alain Ghouila-Houri. Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre // Les Comptes rendus de l'Académie des sciences. — 1962. — Т. 254 (27 серпня). — С. 1370—1371.
- A characterization of comparability graphs and of interval graphs // Canadian Journal of Mathematics. — 1964. — Т. 16 (27 серпня). — С. 539—548. — DOI: .
- Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — 27 серпня. — ISBN 0-12-289260-7.
- M. Golumbic, D. Rotem, J. Urrutia. Comparability graphs and intersection graphs // Discrete Mathematics. — 1983. — Т. 43, вип. 1 (27 серпня). — С. 37—46. — DOI: .
- H. A. Jung. On a class of posets and the corresponding comparability graphs // Journal of Combinatorial Theory, Series B. — 1978. — Т. 24, вип. 2 (27 серпня). — С. 125—133. — DOI: .
- L. Lovász. Selected Topics in Graph Theory. — London : Academic Press, 1983. — Т. 2. — С. 55—87.
- Frédéric Maffray. Recent Advances in Algorithms and Combinatorics / Bruce A. Reed, Cláudia L. Sales. — Springer-Verlag, 2003. — Т. 11. — С. 65—84. — (CMS Books in Mathematics) — DOI:
- R. M. McConnell, J. Spinrad. 8th ACM-SIAM Symposium on Discrete Algorithms. — 1997. — 27 серпня. — С. 19—25.
- Paul Seymour. How the proof of the strong perfect graph conjecture was found // Gazette des Mathématiciens. — 2006. — Вип. 109 (27 серпня). — С. 69—83. Архівовано з джерела 9 березня 2022. Процитовано 17 травня 2021.
- William T. Trotter. Combinatorics and Partially Ordered Sets — Dimension Theory. — Johns Hopkins University Press, 1992. — 27 серпня.
- Jorge Urrutia. Algorithms and Order. — Kluwer Academic Publishers, 1989. — С. 327—436.