Граф сравнимости

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы[en] в некотором частичном порядке. Графы сравнимости также называют транзитивно ориентируемыми графами, частично упорядочиваемыми графами, и графами вложенности.[1] Граф несравнимости — это неориентированный граф, в котором пары элементов соединяются ребром, если элементы элементы несравнимы[en] в некотором частичном порядке.

Определения и характеристики[править | править вики-текст]

Диаграмма Хассе частично упорядоченного множества (слева) и его граф сравнимости (справа)
Один из запрещённых порождённых подграфов графа сравнимости. Обобщённый цикл abdfdcecba в этом графе имеет нечётную длину (девять), но не имеет хорд триангуляризации.

Для любого частично строгоупорядоченного множества (S,<), граф сравнимости (S, <) — это граф (S, ⊥), вершины которого — элементы S, а рёбра — это пары {u, v} элементов, таких что u < v. Таким образом, для частично упорядоченных множеств берём ориентированный ациклический граф, используем транзитивное замыкание и удаляем ориентацию.

Также, граф сравнимости — это граф, имеющий транзитивную ориентацию,[2] имеющий ориентацию рёбер графа, такую что отношение смежности полученного ориентированного графа является транзитивным — если существуют дуги (x,y) и (y,z), должна существовать дуга (x,z).

Можно представить частично упорядоченное множество как семейство множеств, таких что x < y в частичном порядке, если соответствующее x множество является подмножеством соответствующего y множества. Таким образом, можно показать, что граф сравнимости эквивалентен графу вложенности семейства множеств, то есть графу, вершинами которого служат множества семейства, а рёбра соединяют вершины, если одно из множеств содержится в другом.[3]

Также [4] граф сравнимости — это граф, в котором для любого обобщённого цикла нечётной длины можно найти ребро (x,y), соединяющее две вершины, находящиеся на расстоянии два в цикле. Такин рёбра называются хордами триангуляции. В этом контексте обобщённые циклы являются замкнутым обходом, который проходит каждое ребро графа не более одного раза в каждом направлении.

Граф сравнимости можно описать также заданием запрещённых подграфов[en].[5]

Связь с другими семействами графов[править | править вики-текст]

Любой полный граф является графом сравнимости, графом сравнимости линейно упорядоченного множества. Все ациклические ориентации в полном графе транзитивны. Любой двудольный граф также является графом сравнимости. Ориентация рёбер двудольного графа с одной стороны на другую приводит к транзитивной ориентации, соответствующей частичному порядку высотой два. Как заметил Сеймур (Seymour 2006), любой граф сравнимости, не являющийся ни полным, ни двудольным, имеет косое разложение[en].

Дополнение любого интервального графа является графом сравнимости. Интервальные графы — это в точности хордальные графы, имеющие графы сравнимости в качестве дополнений.[6]

Граф перестановки — это граф вложенности множества интервалов.[7] Таким образом, графы перестановок — это ещё один класс графов сравнимости.

Тривиально совершенные графы[en] — это графы сравнимости корневых деревьев.[8] Кографы можно охарактеризовать как графы сравнимости параллельно-последовательных частичных порядков[en]. Таким образом, кографы тоже являются графами сравнимости.[9]

Любой граф сравнимости является совершенным. Совершенство графов сравнимости — это теорема Мирского[en], а совершенство их дополнений — теорема Дилуорса. Эти факты, вместе со свойством двойственности совершенных графов, можно использовать для доказательства теоремы Дилуорса из теоремы Мирского и наоборот.[10] Точнее, графы сравнимости являются совершенно упорядочиваемыми графами[en], Последние являются подклассом совершенных графов — алгоритм жадной раскраски для топологической сортировки транзитивной ориентации графа раскрашивает его оптимально.[11]

Дополнение любого графа сравнимости является графом строк[en].[12]

Алгоритмы[править | править вики-текст]

Транзитивная ориентация графа, если она существует, может быть найдена за линейное время.[13] Однако, алгоритм, который это делает, определяет ориентацию для любого графа, так что для завершения задачи проверки, является ли граф графом сравнимости, нужно проверить, является ли ориентация транзитивной, что по сложности эквивалентно умножению матриц.

Поскольку графы сравнимости совершенны, многие задачи, сложные для более общих классов графов, включая раскраску графов и задачу о независимом множестве, для графов сравнимости можно решить за полиномиальное время.

Примечания[править | править вики-текст]

  1. Golumbic 1980, p. 105; Brandstädt, Le & Spinrad 1999, p. 94.
  2. Ghouila-Houri 1962; см. Brandstädt, Le, Spinrad 1999, теорема 1.4.1, стр. 12. Хотя ориентация, порождённая частичным порядком, не циклична, нет необходимости включать условие отсутствия циклов.
  3. Urrutia 1989; Trotter 1992; Brandstädt, Le, Spinrad 1999, секция 6.3, стр. 94–96.
  4. Ghouila-Houri 1962 и Gilmore, Hoffman 1964. Смотрите также Brandstädt, Le, Spinrad 1999, теорема 6.1.1, стр. 91.
  5. Gallai 1967; Trotter 1992; Brandstädt, Le, Spinrad 1999, стр. 91 и 112.
  6. Транзитивная ориентируемость дополнений интервальных графов была доказана Гойла-Хоури (Ghouila-Houri 1962); характеризацию интервальных графов можно найти у Гилмора и Хофмана (Gilmore, Hoffman 1964). Смотрите также Голумбика (Golumbic 1980), предложение. 1.3, страницы. 15–16.
  7. Dushnik & Miller 1941. Brandstädt, Le, Spinrad 1999, теорема 6.3.1, стр. 95.
  8. (Brandstädt, Le, Spinrad 1999), теорема 6.6.1, стр. 99.
  9. Brandstädt, Le & Spinrad 1999, следствие 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, Le, Spinrad 1999, стр. 91.

Ссылки[править | править вики-текст]

  • Andreas Brandstädt, Van Bang Le, Jeremy Spinrad Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X..
  • Ben Dushnik, E. W. Miller Partially ordered sets // American Journal of Mathematics. — The Johns Hopkins University Press, 1941. — В. 3. — Т. 63. — С. 600–610. — DOI:10.2307/2371374.
  • J. Fox, J. Pach String graphs and incomparability graphs. — 2009..
  • Tibor Gallai Transitiv orientierbare Graphen // Acta Math. Acad. Sci. Hung.. — 1967. — Т. 18. — С. 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. — С. 1370–1371..
  • A characterization of comparability graphs and of interval graphs // Canadian Journal of Mathematics. — 1964. — Т. 16. — С. 539–548. — DOI:10.4153/CJM-1964-055-5.
  • Martin Charles Golumbic Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — ISBN 0-12-289260-7..
  • M. Golumbic, D. Rotem, J. Urrutia Comparability graphs and intersection graphs // Discrete Mathematics. — 1983. — В. 1. — Т. 43. — С. 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. — В. 2. — Т. 24. — С. 125–133. — DOI:10.1016/0095-8956(78)90013-8.
  • L. Lovász Selected Topics in Graph Theory. — 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. — С. 19–25..
  • Paul Seymour How the proof of the strong perfect graph conjecture was found // Gazette des Mathématiciens. — 2006. — В. 109. — С. 69–83..
  • William T. Trotter Combinatorics and Partially Ordered Sets — Dimension Theory. — Johns Hopkins University Press, 1992..
  • Jorge Urrutia Algorithms and Order. — Kluwer Academic Publishers, 1989. — С. 327–436..