График четности - Parity graph

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

В теория графов, а граф четности это граф, в котором каждые два индуцированные пути между теми же двумя вершины имеют то же самое паритет: либо оба пути имеют нечетную длину, либо оба имеют четную длину.[1] Этот класс графов был назван и впервые изучен Бурлет и Ури (1984).[2]

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

Графики четности включают дистанционно-наследственные графы, в котором каждые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую длину. Они также включают двудольные графы, которые можно охарактеризовать аналогично как графы, в которых каждые два пути (не обязательно индуцированные пути) между одними и теми же двумя вершинами имеют одинаковую четность, а линейные идеальные графики, обобщение двудольных графов. каждый граф четности является График Мейниеля, граф, в котором каждый нечетный цикл длины пять и более имеет две хорды. Ведь в графе четности любой длинный нечетный цикл можно разделить на два пути с разной четностью, ни один из которых не является единственным ребром, и требуется по крайней мере одна хорда, чтобы оба пути не были индуцированными. Затем, разделяя цикл на два пути между конечными точками этой первой хорды, требуется вторая хорда, чтобы предотвратить возникновение двух путей этого второго разделения. Поскольку графики Мейниеля идеальные графики, графы четности также совершенны.[1] Это как раз те графы, Декартово произведение с одной кромкой остается идеальным.[3]

Алгоритмы

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

Рекомендации

  1. ^ а б Графики четности, Информационная система по классам графов и их включениям, получено 25 сентября 2016 г.
  2. ^ Бурлет, М .; Ури, Ж.-П. (1984), «Графы четности», Темы об идеальных графах, Северная Голландия Math. Stud., 88, Северная Голландия, Амстердам, стр. 253–277, Дои:10.1016 / S0304-0208 (08) 72939-6, МИСТЕР  0778766.
  3. ^ Янсен, Клаус (1998), "Новая характеристика графов четности и проблема раскраски с затратами", LATIN'98: теоретическая информатика (Кампинас, 1998), Конспект лекций по вычисл. Наук, 1380, Springer, Berlin, стр. 249–260, Дои:10.1007 / BFb0054326, HDL:11858 / 00-001M-0000-0014-7BE2-3, МИСТЕР  1635464.
  4. ^ Цицероне, Серафино; Ди Стефано, Габриэле (1997), "Об эквивалентности по сложности основных задач о двудольных и четных графах", Алгоритмы и вычисления (Сингапур, 1997 г.), Конспект лекций по вычисл. Наук, 1350, Springer, Berlin, стр. 354–363, Дои:10.1007/3-540-63890-3_38, МИСТЕР  1651043.