Рёберно совершенный граф (J~Qyjuk vkfyjoyuudw ijgs)

Перейти к навигации Перейти к поиску
Рёберно совершенный граф. Рёбра в каждой двусвязной компоненте выкрашены в чёрный цвет, если компонента двудольная, в синий цвет, если компонента является тетраэдром, и в красный цвет, если компонента является книгой треугольников.

Рёберно совершенный граф — это граф, рёберный граф которого является совершенным. Эквивалентно, это графы, у которых каждый простой цикл нечётной длины является треугольником[1].

Граф является рёберно совершенным тогда и только тогда, когда любая из его двусвязных компонент является двудольным графом, полным графом или книгой треугольников [2]. Поскольку эти три типа двусвязных компонент являются сами по себе совершенными графами, любой рёберно совершенный граф сам совершенен[1]. По аналогичным причинам любой рёберно совершенный граф является графом чётности[3], графом Мейнеля[4] и вполне упорядочиваемым графом.

Рёберно совершенные графы обобщают двудольные графы и разделяют с ними свойства, что наибольшее паросочетание и наименьшее вершинное покрытие имеют одинаковые размеры, а хроматический индекс равен максимальной степени[5].

Примечания

[править | править код]
  1. 1 2 Trotter L. E., Jr. Line perfect graphs // Mathematical Programming. — 1977. — Т. 12, вып. 2. — С. 255–259. — doi:10.1007/BF01593791.
  2. Frédéric Maffray. Kernels in perfect line-graphs // Journal of Combinatorial Theory. — 1992. — Т. 55, вып. 1. — С. 1–8. — doi:10.1016/0095-8956(92)90028-V..
  3. Martin Grötschel, László Lovász, Alexander Schrijver. Geometric algorithms and combinatorial optimization. — 2nd. — Springer-Verlag, Berlin, 1993. — Т. 2. — С. 281. — (Algorithms and Combinatorics). — ISBN 3-540-56740-2. — doi:10.1007/978-3-642-78240-4..
  4. Annegret Wagler. Critical and anticritical edges in perfect graphs // Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings. — Springer, 2001. — Т. 2204. — С. 317–327. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-45477-2_29..
  5. On line-perfect graphs // Mathematical Programming. — 1978. — Т. 15. — P. 236–238. — doi:10.1007/BF01609025..