В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом.
Примеры Корона с шестью вершинами образует цикл, а корона с восемью вершинами изоморфна графу куба. В двойной шестёрке Шлефли конфигурации 12 прямых и 30 точек в трёхмерном пространстве, двенадцать прямых пересекают друг друга по схеме короны с 12 вершинами.
Свойства
Число рёбер в короне является прямоугольным числом n(n − 1). Её ахроматическое число равно n — можно найти полную раскраску путём выбора пары {ui, vi} в качестве классов цвета. Короны являются симметричными и дистанционно-транзитивными графами. Архдьякон с соавторами описывают разбиение рёбер короны на циклы равной длины.
Корону с 2n вершинами можно вложить в четырёхмерное евклидово пространство так, что все её рёбра будут иметь длину единица. Однако такое вложение может поместить несмежные вершины на расстояние единица. Вложение, при котором рёбра имеют длину единица, а расстояние между любыми несмежными вершинами не равно единице, требует как минимум размерности n − 2. Это показывает, что для представления графа в виде графа единичных расстояний и графа строго единичных расстояний требуются совсем различные размерности. Минимальное число полных двудольных подграфов, требующихся для покрытия рёбер короны (её двудольная размерность, или размер минимального покрытия кликами) равно
то есть обратная функция центрального биномиального коэффициента.
Дополнением короны с 2n вершинами является прямое произведением полных графов K2 Kn, что эквивалентно ладейному графу 2 × n.
Приложение В этикете — традиционных правилах рассаживания гостей за обеденным столом — мужчины и женщины должны перемежаться и ни одна семейная пара не должна сидеть рядом. Рассаживание, удовлетворяющее этим правилам для вечеринки n семейных пар, можно описать как гамильтонов цикл короны. Задача подсчёта числа возможных рассаживаний или, что почти то же самоеВ задаче о гостях начальная позиция цикла существенна, так что число гамильтоновых циклов и решение задачи о гостях различаются в 2n раз., что число гамильтоновых циклов в короне известна в комбинаторике как задача о гостях. Для корон с числом вершин 6, 8, 10, … число (ориентированных) гамильтоновых циклов равно 2, 12, 312, 9600, 416880, 23879520, 1749363840, … .
Короны можно использовать, чтобы показать, что алгоритм жадной раскраски ведёт себя плохо в некоторых случаях — если вершины короны представлены алгоритму в порядке u0, v0, u1, v1, и т. д., то жадная раскраска использует n цветов, хотя оптимальным числом цветов является два. Это построение приписывается Джонсону, а сами короны иногда называют графами Джонсона с обозначением Jn. Фюрер использовал короны как часть построения, показывающего сложность аппроксимации задачи раскраски.
Матушек использовал расстояние в коронах как пример метрического пространства, которое трудно вложить в нормированное векторное пространство.
Как показали Миклавич и Порошник, короны входят в небольшое число различных типов графов, которые являются дистанционно-регулярными циркулянтными графами.
Агарвал и соавторы описывают многоугольники, имеющие короны в качестве графов видимости. Они используют их в качестве примера, чтобы показать, что представление графов в виде объединения полных двудольных графов не всегда эффективно по памяти.
Корона с 2n вершинами с рёбрами, ориентированными от одной стороны двудольного графа к другой, образует стандартный пример частично упорядоченного множества с n.
Примечания
Ссылки
Категория:Теория графов Категория:Регулярные графы