Граф парності — Вікіпедія

Граф парності — це граф, у якому будь-які два породжені шляхи між двома вершинами мають однакову парність — або обидва мають непарні довжини, або обидва парні^[1]. Цей клас графів першим почали вивчати і дали йому назву Барлет та Урі^[2].

Пов'язані класи графів[ред. | ред. код]

Графи парності включають дистанційно-успадковувані графи, в яких будь-які два породжені шляхи між двома вершинами мають однакові довжини. До них належать також двочасткові графи, які можна описати аналогічно як графи, в яких будь-які два шляхи (не обов'язково породжені) між двома вершинами мають однакову парність, і реберно-досконалі графи, що узагальнюють двочасткові графи.

Будь-який граф парності є графом Мейнеля, тобто графом, у якому будь-який цикл непарної довжини (довжиною 5 і більше) має принаймні дві хорди. У графі парності будь-який довгий цикл можна розбити на два шляхи різної парності, жоден з яких не є окремим ребром і необхідна принаймні одна хорда, щоб ці шляхи були породженими шляхами. Тоді після розбиття циклу на два шляхи між кінцевими точками першої хорди необхідна друга хорда, щоб другий шлях не був породженим. Оскільки графи Мейнеля є досконалими графами, графи парності також досконалі^[1]. Це точно графи, прямий добуток яких з окремим ребром залишається досконалим графом^[3].

Алгоритми[ред. | ред. код]

Граф є графом парності тоді й лише тоді, коли будь-яка компонента його розщеплення^[en] є або повним графом, або двочастковим графом. Ґрунтуючись на цьому описі, перевірити, чи є граф графом парності можна за лінійний час. Той самий опис приводить до узагальнення деяких алгоритмів оптимізації на графах із двочасткових графів на графи парності. Наприклад, використовуючи розщеплення графа, зважену найбільшу незалежну множину графа парності можна знайти за поліноміальний час^[4].

Примітки[ред. | ред. код]

Література[ред. | ред. код]

• Burlet M., Uhry J.-P. Parity graphs // Topics on perfect graphs. — Amsterdam : North-Holland, 1984. — Т. 88. — (North-Holland Math. Stud.) — DOI:10.1016/S0304-0208(08)72939-6.
• Klaus Jansen. A new characterization for parity graphs and a coloring problem with costs // LATIN'98: theoretical informatics (Campinas, 1998). — Springer, Berlin, 1998. — Т. 1380. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/BFb0054326.
• Serafino Cicerone, Gabriele Di Stefano. On the equivalence in complexity among basic problems on bipartite and parity graphs // Algorithms and computation (Singapore, 1997). — Springer, Berlin, 1997. — Т. 1350. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/3-540-63890-3_38.