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