График Мейниеля - Meyniel graph

В графике Мейниеля каждый длинный нечетный цикл (например, показанный здесь черный 5-цикл) должен иметь как минимум две хорды (зеленые).

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

Графы Мейниеля названы в честь Анри Мейниеля (также известного Гипотеза Мейниэля ), которые доказали, что они идеальные графики в 1976 г.[2] задолго до доказательства сильная теорема о совершенном графе полностью охарактеризовал совершенные графики. тот же результат был независимо обнаружен Маркосян и Карапетян (1976).[3]

Совершенство

Графы Мейниеля являются подклассом совершенных графов. Каждый индуцированный подграф графа Мейниеля - это другой граф Мейниеля, и в каждом графе Мейниеля размер максимальная клика равно минимальному количеству цветов, необходимых в раскраска графика. Таким образом, графы Мейниеля соответствуют определению идеального графа, согласно которому кликовое число равно хроматическому числу в каждом индуцированном подграфе.[1][2][3]

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

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

Графики Мейниеля содержат хордовые графы, то графики четности, и их подклассы интервальные графики, дистанционно-наследственные графы, двудольные графы, и линейные идеальные графики.[1]

График дома идеален, но не Мейниэль

Хотя графы Мейниеля образуют очень общий подкласс идеальных графов, они не включают все совершенные графы. Например, домовый граф (пятиугольник с одной хордой) совершенен, но не является графом Мейниеля.

Алгоритмы и сложность

Графы Мейниеля можно распознать в полиномиальное время,[5] и несколько задач оптимизации графа, включая раскраска графика которые NP-жесткий для произвольных графов может быть решена за полиномиальное время для графов Мейниеля.[6][7]

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

  1. ^ а б c d Графики Мейниеля, Информационная система по классам графов и их включениям, получено 25 сентября 2016 г.
  2. ^ а б Мейниэль, Х. (1976), "О гипотезе идеального графа", Дискретная математика, 16 (4): 339–342, Дои:10.1016 / S0012-365X (76) 80008-8, МИСТЕР  0439682.
  3. ^ а б Markosjan, S.E .; Карапетян, И. А. (1976), "Совершенные графы", Доклады Академии Наук Армянской ССР, 63 (5): 292–296, МИСТЕР  0450130.
  4. ^ Хоанг, К. Т. (1987), "О гипотезе Мейниэля", Журнал комбинаторной теории, Серия B, 42 (3): 302–312, Дои:10.1016/0095-8956(87)90047-5, МИСТЕР  0888682.
  5. ^ Бурлет, М .; Фонлупт, Дж. (1984), "Полиномиальный алгоритм распознавания графа Мейниеля", Темы об идеальных графах, Северная Голландия Math. Stud., 88, Северная Голландия, Амстердам, стр. 225–252, Дои:10.1016 / S0304-0208 (08) 72938-4, HDL:10068/49205, МИСТЕР  0778765.
  6. ^ Герц, А. (1990), "Быстрый алгоритм раскраски графов Мейниеля", Журнал комбинаторной теории, Серия B, 50 (2): 231–240, Дои:10.1016 / 0095-8956 (90) 90078-Е, МИСТЕР  1081227.
  7. ^ Roussel, F .; Русу, И. (2001), "Ан О(п2) алгоритм раскрашивания графиков Мейниеля ", Дискретная математика, 235 (1–3): 107–123, Дои:10.1016 / S0012-365X (00) 00264-8, МИСТЕР  1829840.