Граф чётности

Граф чётности (уникальный наименьший кубический спичечный граф), который не является ни дистанционно-наследуемым, ни двудольным

Граф чётности — это граф, в котором любые два порождённых пути между двумя вершинами имеют одинаковую чётность — либо оба пути имеют нечётные длины, либо оба пути имеют чётные длины. Этот класс графов первым начали изучать и дали ему название Барлет и Ури.

Связанные классы графов

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

Любой граф чётности является графом Мейнеля, то есть графом, в котором любой цикл нечётной длины (длиной 5 и более) имеет по меньшей мере две хорды. В графе чётности любой длинный цикл может быть разбит на два пути различной чётности, ни один из которых не является отдельным ребром и по меньшей мере одна хорда необходима, чтобы эти пути не были порождёнными путями. Тогда после разбиения цикла на два пути между конечными точками первой хорды необходима вторая хорда, чтобы второй путь не был порождённым. Поскольку графы Мейнеля являются совершенными графами, графы чётности также совершенны. Это в точности графы, прямое произведение которых с отдельным ребром остаётся совершенным графом.

Алгоритмы

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

Литература

• 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.