В теории графов граф четности — это граф , в котором каждые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую четность : либо оба пути имеют нечетную длину, либо оба имеют четную длину. [1] Этот класс графов был назван и впервые изучен Берлетом и Ури (1984). [2]
Графы четности включают в себя дистанционно-наследуемые графы , в которых каждые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую длину. Они также включают в себя двудольные графы , которые можно охарактеризовать аналогично как графы, в которых каждые два пути (не обязательно индуцированные пути) между одними и теми же двумя вершинами имеют одинаковую четность, и линейные совершенные графы , обобщение двудольных графов. Каждый граф четности является графом Мейниэля , графом, в котором каждый нечетный цикл длины пять или более имеет две хорды. Так как в графе четности любой длинный нечетный цикл может быть разделен на два пути разной четности, ни один из которых не является единственным ребром, и нужна по крайней мере одна хорда, чтобы предотвратить то, что они оба являются индуцированными путями. Затем, разделяя цикл на два пути между конечными точками этой первой хорды, нужна вторая хорда, чтобы предотвратить индуцирование двух путей этого второго разбиения. Поскольку графы Мейниэля являются совершенными графами , графы четности также совершенны. [1] Это именно те графы, декартово произведение которых с одним ребром остается совершенным. [3]
Граф является графом четности тогда и только тогда, когда каждый компонент его разбиения на части является либо полным графом , либо двудольным графом . [4] На основе этой характеристики можно проверить, является ли данный граф графом четности за линейное время . Та же самая характеристика также приводит к обобщениям некоторых алгоритмов оптимизации графов с двудольных графов на графы четности. Например, используя разбиение на части, можно найти взвешенное максимальное независимое множество графа четности за полиномиальное время . [5]