Граф четности
В теории графов граф четности — это граф , в котором каждые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую четность : либо оба пути имеют нечетную длину, либо оба имеют четную длину. [1] Этот класс графов был назван и впервые изучен Берлетом и Ури (1984) . [2]
Связанные классы графов
[ редактировать ]Графы четности включают в себя дистанционно-наследственные графы , в которых каждые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую длину. Они также включают двудольные графы , которые можно аналогично охарактеризовать как графы, в которых каждые два пути (не обязательно индуцированные пути) между одними и теми же двумя вершинами имеют одинаковую четность, и линейные совершенные графы , обобщение двудольных графов.Каждый граф четности представляет собой граф Мейнеля , граф, в котором каждый нечетный цикл длины пять или более имеет две хорды. Ведь в графе четности любой длинный нечетный цикл может быть разделен на два пути разной четности, ни один из которых не является единственным ребром, и необходима хотя бы одна хорда, чтобы оба этих пути не были индуцированными путями. Затем, разделив цикл на два пути между конечными точками этой первой хорды, необходима вторая хорда, чтобы предотвратить возникновение двух путей этого второго разделения. Поскольку графы Мейниэля являются совершенными графами , графы четности также совершенны. [1] Это именно те графы, декартово произведение которых с одним ребром остается совершенным. [3]
Алгоритмы
[ редактировать ]Граф является графом четности тогда и только тогда, когда каждый компонент его расщепленного разложения является либо полным графом , либо двудольным графом . [4] На основе этой характеристики можно проверить, является ли данный граф графом четности в линейном времени . Та же характеристика также приводит к обобщению некоторых алгоритмов оптимизации графов с двудольных графов на графы четности. Например, используя расщепленное разложение, можно найти взвешенный максимальный независимый набор графа четности за полиномиальное время . [5]
Ссылки
[ редактировать ]- ^ Jump up to: а б Графы четности , Информационная система по классам графов и их включениям, получено 25 сентября 2016 г.
- ^ Берлет, М.; Ури, Ж.-П. (1984), «Графы четности», Темы о совершенных графах , North-Holland Math. Студ., вып. 88, Северная Голландия, Амстердам, стр. 253–277, номер документа : 10.1016/S0304-0208(08)72939-6 , MR 0778766 .
- ^ Янсен, Клаус (1998), «Новая характеристика графов четности и проблема раскраски со стоимостью», LATIN'98: теоретическая информатика (Campinas, 1998) , Конспекты лекций по вычислениям. наук., вып. 1380, Springer, Berlin, стр. 249–260, doi : 10.1007/BFb0054326 , hdl : 11858/00-001M-0000-0014-7BE2-3 , MR 1635464 .
- ^ Цицерон, Серафино; Ди Стефано, Габриэле (1999), «О расширении двудольных графов до графов четности», Discrete Appl. Математика. , 95 (1–3): 181–195, doi : 10.1016/S0166-218X(99)00074-8 , S2CID 17260334 .
- ^ Цицерон, Серафино; Ди Стефано, Габриэле (1997), «Об эквивалентности по сложности основных задач на двудольных графах и графах четности», Алгоритмы и вычисления (Сингапур, 1997) , Конспекты лекций по вычислениям. наук., вып. 1350, Springer, Berlin, стр. 354–363, номер документа : 10.1007/3-540-63890-3_38 , MR 1651043 .