Вікіпедія

Граф порівнянності

неорієнтований граф, у якому пари елементів з'єднано ребром, якщо ці елементи порівнянні в деякому частковому порядку
(Перенаправлено з Граф порівняння)

В теорії графів граф порівнянності — це неорієнтований граф, у якому пари елементів з'єднано ребром, якщо ці елементи порівнянні[en] в деякому частковому порядку. Графи порівнянності також називають транзитивно-орієнтованими графами, частково впорядковуваними графами і графами вкладеності[1]. Граф непорівнянності — це неорієнтований граф, у якому пари елементів з'єднуються ребром, якщо елементи непорівнянні[en] в деякому частковому порядку.

Визначення й характеристики ред.

 
Діаграма Гассе частково впорядкованої множини (зліва) і її граф порівнянності (праворуч)
 
Один із заборонених породжених підграфів графу порівнянності. Узагальнений цикл a-b-d-f-d-c-e-c-b-a в цьому графі має непарну довжину (дев'ять), але не має хорд тріангуляризації

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

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

Див. також ред.

Примітки ред.

  1. ↑ (Golumbic, 1980), стор. 105; (Brandstädt et al, 1999), стор. 94.
  2. ↑ (Ghouila-Houri, 1962); див. (Brandstädt et al, 1999), теорема 1.4.1, стор. 12. Хоча орієнтація, породжена частковим порядком не циклічна, немає потреби включати умову відсутності циклів
  3. ↑ (Urrutia, 1989); (Trotter, 1992); (Brandstädt et al, 1999), секція 6.3, стор. 94—96.
  4. ↑ (Ghouila-Houri, 1962) и (Gilmore, Hoffman, 1964). См. также (Brandstädt et al, 1999), теорема 6.1.1, стор. 91.
  5. ↑ (Gallai, 1967); (Trotter, 1992); (Brandstädt et al, 1999), стор. 91 і 112.
  6. ↑ Транзитивну орієнтовність доповнень інтервальних графів довів Гойла-Гоурі (Ghouila-Houri, 1962); характеризацію інтервальних графів можна знайти в Гілмора і Гофмана (Gilmore, Hoffman, 1964). Див. також Голумбіка (Golumbic, 1980), речення 1.3, сторінки 15—16.
  7. ↑ (Dushnik, Miller, 1941). (Brandstädt et al, 1999), теорема 6.3.1, стор. 95.
  8. ↑ (Brandstädt et al, 1999), теорема 6.6.1, стор. 99.
  9. ↑ (Brandstädt et al1999), наслідок 6.4.1, стор. 96; (Jung, 1978).
  10. ↑ (Golumbic, 1980), теореми 5.34 і 5.35, стор. 133.
  11. ↑ Maffray, 2003.
  12. ↑ (Golumbic, Rotem, Urrutia, 1983) і (Lovász, 1983). Див. також (Fox, Pach, 2009).
  13. ↑ (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. — 1 квітня. — 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 (1 квітня). — С. 600—610. — DOI:10.2307/2371374.
  • J. Fox, J. Pach. String graphs and incomparability graphs. — 2009. — 1 квітня.
  • Tibor Gallai. Transitiv orientierbare Graphen // Acta Math. Acad. Sci. Hung.. — 1967. — Т. 18 (1 квітня). — С. 25—66. — DOI:10.1007/BF02020961.
  • 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 (1 квітня). — С. 1370—1371.
  • A characterization of comparability graphs and of interval graphs // Canadian Journal of Mathematics. — 1964. — Т. 16 (1 квітня). — С. 539—548. — DOI:10.4153/CJM-1964-055-5.
  • Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — 1 квітня. — ISBN 0-12-289260-7.
  • M. Golumbic, D. Rotem, J. Urrutia. Comparability graphs and intersection graphs // Discrete Mathematics. — 1983. — Т. 43, вип. 1 (1 квітня). — С. 37—46. — DOI:10.1016/0012-365X(83)90019-5.
  • H. A. Jung. On a class of posets and the corresponding comparability graphs // Journal of Combinatorial Theory, Series B. — 1978. — Т. 24, вип. 2 (1 квітня). — С. 125—133. — DOI:10.1016/0095-8956(78)90013-8.
  • 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:10.1007/0-387-22444-0_3.
  • R. M. McConnell, J. Spinrad. 8th ACM-SIAM Symposium on Discrete Algorithms. — 1997. — 1 квітня. — С. 19—25.
  • Paul Seymour. How the proof of the strong perfect graph conjecture was found // Gazette des Mathématiciens. — 2006. — Вип. 109 (1 квітня). — С. 69—83. Архівовано з джерела 9 березня 2022. Процитовано 17 травня 2021.
  • William T. Trotter. Combinatorics and Partially Ordered Sets — Dimension Theory. — Johns Hopkins University Press, 1992. — 1 квітня.
  • Jorge Urrutia. Algorithms and Order. — Kluwer Academic Publishers, 1989. — С. 327—436.
Отримано з https://uk.wikipedia.org/w/index.php?title=Граф_порівнянності&oldid=36830725