Реберно-досконалий граф: відмінності між версіями
Створено шляхом перекладу сторінки «Рёберно совершенный граф» |
(Немає відмінностей)
|
Версія за 17:51, 3 серпня 2021
Реберно-досконалий граф - це граф, реберний граф якого є досконалим. Еквівалентно, це графи, у яких кожен простий цикл непарної довжини є трикутником[1].
Граф є реберно досконалим тоді і тільки тоді, коли будь-яка з його двозв'язних компонент є двочастковим графом, повним графом або книгою трикутників [2]. Оскільки ці три типи двозв'язних компонент самі є досконалими графами, будь-який реберно-досконалий граф сам досконалий[1]. З тієї ж причини будь-який реберно-досконалий граф є графом парності[3], графом Мейнеля[4] і цілком упорядковуваним графом.
Реберно-досконалі графи узагальнюють дводольні графи і поділяють з ними властивості, що найбільше парування і найменше вершинне покриття мають однакові розміри, а хроматичний індекс дорівнює найбільшому степеню[5].
Див. також
- Стиснутий граф - граф, у якому будь-який периферійний цикл є трикутником
Примітки
- ↑ а б Trotter L. E., Jr. Line perfect graphs // Mathematical Programming. — 1977. — Т. 12, вип. 2. — С. 255–259. — DOI:10.1007/BF01593791.
- ↑ 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..
- ↑ Martin Grötschel, László Lovász, Alexander Schrijver. {{{Заголовок}}}. — Т. 2. — ISBN 3-540-56740-2. — DOI:.
- ↑ Annegret Wagler. {{{Заголовок}}}. — Т. 2204. — DOI:.
- ↑ On line-perfect graphs // Mathematical Programming. — 1978. — Т. 15. — No. 2. — P. 236–238. — DOI:10.1007/BF01609025..