Форум Статьи Контакты
Строительство — возведение зданий и сооружений, а также их капитальный и текущий ремонт, реконструкция, реставрация и реновация.

Граф Мейнеля

Дата: 18-12-2020, 01:45 » Раздел: Статьи  » 

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

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

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

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

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

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

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

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

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

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


(голосов:0)

Пожожие новости
Комментарии

Ваше Имя:   Ваш E-Mail: