В теории графов , разделе математики, коронный граф на 2 n вершинах — это неориентированный граф с двумя наборами вершин { u 1 , u 2 , …, un } и { v 1 , v 2 , …, v n } и с ребром от u i до v j всякий раз, когда i ≠ j .
Граф короны можно рассматривать как полный двудольный граф , из которого удалены ребра идеального паросочетания , как двудольное двойное накрытие полного графа , как тензорное произведение K n × K 2 , как дополнение декартова прямого произведение K n и K 2 , или как двудольный граф Кнезера H n ,1 , представляющий подмножества из 1 элемента и ( n – 1) - элементов набора из n - элементов, с ребром между двумя подмножествами, если одно из них содержится в другой.
Граф короны с 6 вершинами образует цикл , а граф короны с 8 вершинами изоморфен графу куба . В двойной шестерке Шлефли , конфигурации из 12 линий и 30 точек в трехмерном пространстве, двенадцать линий пересекаются друг с другом по образцу коронного графа с 12 вершинами.
Количество ребер в графе короны — это проническое число n ( n – 1) . Его ахроматическое число n : можно найти полную раскраску , выбрав каждую пару { u i , v i } в качестве одного из цветовых классов. [1] Графы Короны симметричны и дистанционно транзитивны . Архидиакон и др. (2004) описывают разбиение ребер коронного графа на циклы одинаковой длины.
Граф короны с 2 n вершинами можно вложить в четырехмерное евклидово пространство таким образом, чтобы все его ребра имели единичную длину. Однако это вложение может также разместить некоторые несмежные вершины на расстоянии единицы друг от друга. Вложение, в котором ребра находятся на единичном расстоянии, а не-ребра не находятся на единичном расстоянии, требует как минимум n – 2 измерений. Этот пример показывает, что граф может потребовать очень разных измерений для представления в виде графиков единичных расстояний и в виде строгих графов единичных расстояний. [2]
Минимальное количество полных двудольных подграфов , необходимых для покрытия ребер коронного графа (его двудольная размерность или размер минимального бикликового покрытия), равно
обратная функция центрального биномиального коэффициента . [3]
Граф дополнений коронного графа с 2 n вершинами является декартовым произведением полных графов K 2 ▢ K n или, что то же самое, ладейным графом 2 × n .
В этикете традиционным правилом расположения гостей за обеденным столом является то, что мужчины и женщины должны чередоваться, и ни одна семейная пара не должна сидеть рядом друг с другом. [4] Договоренности, удовлетворяющие этому правилу, для группы, состоящей из n супружеских пар, можно описать как гамильтоновы циклы графа короны. Например, расположение вершин, показанное на рисунке, можно интерпретировать как схемы рассадки такого типа, на которых каждый муж и жена сидят как можно дальше друг от друга. Проблема подсчета количества возможных расстановок мест или, что почти эквивалентно [5] количества гамильтоновых циклов в графе короны, известна в комбинаторике как проблема управления ; для коронных графов с 6, 8, 10, ... вершинами количество (ориентированных) гамильтоновых циклов равно
Графы короны можно использовать, чтобы показать, что алгоритмы жадной раскраски ведут себя плохо в худшем случае: если вершины графа короны представлены алгоритму в порядке u 0 , v 0 , u 1 , v 1 и т. д., то жадная раскраска использует n цветов, тогда как оптимальное количество цветов — два. Эту конструкцию приписывают Джонсону (1974); графы короны иногда называют графами Джонсона с обозначением J n . [6] Фюрер (1995) использует коронные графы как часть конструкции, показывающей сложность аппроксимации задач раскраски.
Матушек (1996) использует расстояния в графах корон как пример метрического пространства , которое трудно встроить в нормированное векторное пространство .
Как показывают Миклавич и Поточник (2003), коронные графы являются одним из небольшого числа различных типов графов, которые могут встречаться как дистанционно регулярные циркулянтные графы .
Агарвал и др. (1994) описывают полигоны, графы коронок которых являются графами видимости ; они используют этот пример, чтобы показать, что представление графов видимости как объединений полных двудольных графов не всегда может быть эффективным с точки зрения использования пространства.
Граф короны с 2 n вершинами, ребра которого ориентированы от одной стороны биразделения к другой, образует стандартный пример частично упорядоченного множества с порядковой размерностью n .
{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )