Граф Мейниэля
В теории графов граф Мейнеля — это граф , в котором каждый нечетный цикл длины пять и более имеет как минимум две хорды (ребра, соединяющие непоследовательные вершины цикла). [1] Хорды могут быть непересекающимися (как показано на рисунке) или пересекаться друг с другом, если их хотя бы две.
Графы Мейнеля названы в честь Анри Мейнеля (также известного благодаря гипотезе Мейнеля ), который доказал, что они являются совершенными графами в 1976 году. [2] задолго до того, как доказательство сильной теоремы о совершенных графах полностью охарактеризовало совершенные графы.Тот же результат был независимо открыт Маркосяном и Карапетяном (1976) . [3]
Совершенство
[ редактировать ]Графы Мейнеля являются подклассом идеальных графов. Каждый индуцированный подграф графа Мейниэля является другим графом Мейниэля, и в каждом графе Мейниэля размер максимальной клики равен минимальному количеству цветов, необходимых для раскраски графа . Таким образом, графы Мейнеля соответствуют определению идеального графа, согласно которому кликовое число равно хроматическому числу в каждом индуцированном подграфе. [1] [2] [3]
Графы Мейниэля также называются очень сильно совершенными графами , потому что (как предположил Мейниэль и доказал Хоанг) они могут быть охарактеризованы свойством, обобщающим определяющее свойство сильно совершенных графов : в каждом индуцированном подграфе графа Мейнеля каждая вершина принадлежит , независимое множество пересекающее каждую максимальную клику . [1] [4]
Связанные классы графов
[ редактировать ]Графы Мейниэля содержат хордальные графы , графы четности и их подклассы — интервальные графы , дистанционно-наследственные графы , двудольные графы и линейные совершенные графы . [1]
Хотя графы Мейнеля образуют очень общий подкласс идеальных графов, они не включают в себя все совершенные графы. Например, граф дома (пятиугольник только с одной хордой) идеален, но не является графом Мейнеля.
Алгоритмы и сложность
[ редактировать ]Графики Мейнеля можно распознать за полиномиальное время . [5] и несколько задач оптимизации графов, включая раскраску графов , которые являются NP-сложными для произвольных графов, могут быть решены за полиномиальное время для графов Мейниэля. [6] [7]
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с д Графики Мейниэля , Информационная система по классам графов и их включениям, получено 25 сентября 2016 г.
- ↑ Перейти обратно: Перейти обратно: а б Мейниэль, Х. (1976), «О гипотезе идеального графа», Discrete Mathematics , 16 (4): 339–342, doi : 10.1016/S0012-365X(76)80008-8 , MR 0439682 .
- ↑ Перейти обратно: Перейти обратно: а б Markosjan, S. E.; Karapetjan, I. A. (1976), "Perfect graphs", Doklady Akademiya Nauk Armyanskoĭ SSR , 63 (5): 292–296, MR 0450130 .
- ^ Хоанг, Коннектикут (1987), «О гипотезе Мейниэля», Журнал комбинаторной теории , серия B, 42 (3): 302–312, doi : 10.1016/0095-8956(87)90047-5 , MR 0888682 .
- ^ Берлет, М.; Фонлупт, Дж. (1984), «Полиномиальный алгоритм распознавания графа Мейниэля», Темы об идеальных графах , North-Holland Math. Студ., вып. 88, Северная Голландия, Амстердам, стр. 225–252, doi : 10.1016/S0304-0208(08)72938-4 , hdl : 10068/49205 , MR 0778765 .
- ^ Герц, А. (1990), «Быстрый алгоритм раскраски графов Мейниэля», Журнал комбинаторной теории , серия B, 50 (2): 231–240, doi : 10.1016/0095-8956(90)90078-E , MR 1081227 .
- ^ Руссель, Ф.; Русу, И. (2001), «An O ( n 2 ) алгоритм раскраски графов Мейниэля», Discrete Mathematics , 235 (1–3): 107–123, doi : 10.1016/S0012-365X(00)00264-8 , MR 1829840 .