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

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

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

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

Будь-який граф порівнянності є досконалим. Досконалість графів порівнянності стверджує теорема Мирського, а досконалість їх доповнень теорема Ділуорса. Ці факти, разом зі властивістю подвійності досконалих графів, можна використовувати для доведення теореми Ділуорса з теореми Мирського і навпаки[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. — 17 лютого. — 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 (17 лютого). С. 600—610. DOI:10.2307/2371374.
  • J. Fox, J. Pach. String graphs and incomparability graphs.  2009. — 17 лютого.
  • Tibor Gallai. Transitiv orientierbare Graphen // Acta Math. Acad. Sci. Hung..  1967. Т. 18 (17 лютого). С. 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 (17 лютого). С. 1370—1371.
  • A characterization of comparability graphs and of interval graphs // Canadian Journal of Mathematics.  1964. Т. 16 (17 лютого). С. 539—548. DOI:10.4153/CJM-1964-055-5.
  • Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — 17 лютого. — ISBN 0-12-289260-7.
  • M. Golumbic, D. Rotem, J. Urrutia. Comparability graphs and intersection graphs // Discrete Mathematics.  1983. Т. 43, вип. 1 (17 лютого). С. 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 (17 лютого). С. 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. — 17 лютого. С. 19—25.
  • Paul Seymour. How the proof of the strong perfect graph conjecture was found // Gazette des Mathématiciens.  2006. Вип. 109 (17 лютого). С. 69—83.
  • William T. Trotter. Combinatorics and Partially Ordered Sets — Dimension Theory. — Johns Hopkins University Press, 1992. — 17 лютого.
  • Jorge Urrutia. Algorithms and Order. — Kluwer Academic Publishers, 1989. — С. 327—436.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.