Википедия

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

В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы[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), любой граф сравнимости, не являющийся ни полным, ни двудольным, имеет косое разложение[en].

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

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

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

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

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

Алгоритмы править

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

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

Примечания править

  1. ↑ Golumbic, 1980, p. 105; Brandstädt et al, 1999, p. 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. — 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. — С. 600—610. — doi:10.2307/2371374. — JSTOR 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. — Т. 43, вып. 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. — С. 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 / Ivan Rival. — Kluwer Academic Publishers, 1989. — С. 327—436.
Источник — https://ru.wikipedia.org/w/index.php?title=Граф_сравнимости&oldid=136325475