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

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

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

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

Примечания

Литература

Категория:Семейства графов Категория:Совершенные графы