Граф Мейнеля

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

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

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

Совершенство[править | править код]

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

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

Связанные классы графов[править | править код]

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

Домик является совершенным графом, но не является графом Мейнеля

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

Алгоритмы и сложность[править | править код]

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

Примечания[править | править код]

  1. ↑ 1 2 3 4 Meyniel graphs Архивная копия от 28 июля 2019 на Wayback Machine, Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
  2. ↑ 1 2 Meyniel, 1976, с. 339–342.
  3. ↑ 1 2 Маркосян, Карапетян, 1976, с. 292–296.
  4. ↑ Hoàng, 1987, с. 302–312.
  5. ↑ Burlet, Fonlupt, 1984, с. 225–252.
  6. ↑ Hertz, 1990, с. 231–240.
  7. ↑ Roussel, Rusu, 2001, с. 107–123.

Литература[править | править код]

  • Meyniel H. On the perfect graph conjecture // Discrete Mathematics. — 1976. — Т. 16, вып. 4. — С. 339–342. — doi:10.1016/S0012-365X(76)80008-8.
  • С. Маркосян, И. Карапетян. О совершенных графах // ДАН Арм. ССР. — 1976. — Вып. 5.
  • Hoàng C. T. On a conjecture of Meyniel // Journal of Combinatorial Theory. — 1987. — Т. 42, вып. 3. — С. 302–312. — doi:10.1016/0095-8956(87)90047-5.
  • Burlet M., Fonlupt J. Polynomial algorithm to recognize a Meyniel graph // Topics on perfect graphs. — North-Holland, Amsterdam, 1984. — Т. 88. — С. 225–252. — (North-Holland Math. Stud.). — doi:10.1016/S0304-0208(08)72938-4.
  • Hertz A. A fast algorithm for coloring Meyniel graphs // Journal of Combinatorial Theory. — 1990. — Т. 50, вып. 2. — С. 231–240. — doi:10.1016/0095-8956(90)90078-E.
  • Roussel F., Rusu I. An O(n2) algorithm to color Meyniel graphs // Discrete Mathematics. — 2001. — Т. 235, вып. 1—3. — С. 107–123. — doi:10.1016/S0012-365X(00)00264-8.
Источник — https://ru.wikipedia.org/w/index.php?title=Граф_Мейнеля&oldid=125065441