Граф короны

В теории графов , разделе математики, коронный граф на $2 n$ вершинах — это неориентированный граф с двумя наборами вершин ${u 1, u 2, \dots, un}$ и ${v 1, v 2, \dots,$ $v$ $n$ $}$ $и$ с ребром от $ui$ до $v$ $j$ всякий раз, $когда$ $i$ $\neq$ $j$ .

Граф короны можно рассматривать как полный двудольный граф, из которого удалены ребра совершенного паросочетания , как двудольное двойное покрытие полного графа , как тензорное произведение $K n \times K 2$ , как дополнение декартова прямого произведения $K n$ и $K 2$ или как двудольный граф Кнезера $H n,1$ представляющий подмножества из 1 и $(n - 1)$ элементов множества из $n$ элементов, с ребром между двумя подмножествами, когда одно содержится в другом.

Примеры

Граф короны с 6 вершинами образует цикл , а граф короны с 8 вершинами изоморфен графу куба . В двойной шестерке Шлефли , конфигурации из 12 линий и 30 точек в трехмерном пространстве, двенадцать линий пересекаются друг с другом в узоре графа короны с 12 вершинами.

Характеристики

Бикликовое покрытие графа короны с десятью вершинами

Число ребер в графе короны — это проническое число $n (n - 1)$ . Его ахроматическое число равно $n$ : можно найти полную раскраску , выбрав каждую пару ${ui, v i}$ в качестве одного из цветовых классов. ^[1] Графы короны симметричны и транзитивны по расстоянию . Архидьякон и др. (2004) описывают разбиения ребер графа короны на циклы одинаковой длины $.$

Граф короны $из 2 n$ вершин может быть вложен в четырехмерное евклидово пространство таким образом, что все его ребра имеют единичную длину. Однако это вложение может также размещать некоторые несмежные вершины на единичном расстоянии друг от друга. Вложение, в котором ребра находятся на единичном расстоянии, а не-ребра не находятся на единичном расстоянии, требует по крайней мере $n - 2$ измерений. Этот пример показывает, что граф может потребовать совершенно разных измерений для представления в виде графа единичных расстояний и в виде строгого графа единичных расстояний. ^[2]

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

\sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\},

обратная функция центрального биномиального коэффициента . ^[3]

Дополнительный граф коронного графа с $2 n$ вершинами является декартовым произведением полных графов $K 2 ▢ K n$ или, что эквивалентно, графом ладьи $2 \times n$ .

Приложения

В этикете традиционное правило рассадки гостей за обеденным столом заключается в том, что мужчины и женщины должны чередовать места, и ни одна супружеская пара не должна сидеть рядом друг с другом. ^[4] Расстановки, удовлетворяющие этому правилу, для вечеринки, состоящей из n супружеских пар, можно описать как гамильтоновы циклы графа короны. Например, расположения вершин, показанные на рисунке, можно интерпретировать как схемы рассадки такого типа, в которых каждый муж и жена сидят как можно дальше друг от друга. Задача подсчета количества возможных схем рассадки или, что почти эквивалентно ^[5], количества гамильтоновых циклов в графе короны, известна в комбинаторике как задача управления ; для графов короны с 6, 8, 10, ... вершинами количество (ориентированных) гамильтоновых циклов равно

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (последовательность A094047 в OEIS )

Графы короны можно использовать для того, чтобы показать, что алгоритмы жадной раскраски ведут себя плохо в худшем случае: если вершины графа короны представлены алгоритму в порядке u ₀ , v ₀ , u ₁ , v ₁ и т. д., то жадная раскраска использует n цветов, тогда как оптимальное количество цветов равно двум. Эта конструкция приписывается Джонсону (1974); графы короны иногда называют графами Джонсона с обозначением J _n . ^[6] Фюрер (1995) использует графы короны как часть конструкции, показывающей сложность аппроксимации задач раскраски.

Матоушек (1996) использует расстояния в графах корон как пример метрического пространства , которое трудно вложить в нормированное векторное пространство .

Как показывают Миклавич и Поточник (2003), коронные графы являются одним из небольшого числа различных типов графов, которые могут встречаться как дистанционно-регулярные циркулянтные графы .

Агарвал и др. (1994) описывают многоугольники, имеющие графы корон в качестве графов видимости ; они используют этот пример, чтобы показать, что представление графов видимости в виде объединений полных двудольных графов не всегда может быть эффективным с точки зрения использования памяти.

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

Примечания

^ Чаудхари и Вишванатан (2001).
^ Эрдёш и Симоновиц (1980).
^ де Кан, Грегори и Пуллман (1981).
^ Фокс, Сью (2011), Этикет для чайников (2-е изд.), John Wiley & Sons, стр. 244, ISBN 9781118051375
^ В задаче о менажном хозяйстве начальное положение цикла считается значимым, поэтому число гамильтоновых циклов и решение задачи о менажном хозяйстве различаются в 2 n раз .
^ Кубале (2004).

Ссылки

Агарвал, Панкадж К .; Алон, Нога ; Аронов, Борис ; Сури, Субхаш (1994), «Могут ли графы видимости быть представлены компактно?», Дискретная и вычислительная геометрия , 12 (1): 347–365, doi : 10.1007/BF02574385 , MR 1298916.
Архидьякон, Д.; Дебовски, М.; Диниц, Дж .; Гавлас, Х. (2004), «Системы циклов в полном двудольном графе без одного фактора», Дискретная математика , 284 (1–3): 37–43, doi :10.1016/j.disc.2003.11.021, MR 2071894.
Чаудхари, Амитабх; Вишванатан, Сундар (2001), «Алгоритмы аппроксимации для ахроматического числа», Журнал алгоритмов , 41 (2): 404–416, CiteSeerX 10.1.1.1.5562 , doi :10.1006/jagm.2001.1192, MR 1869259, S2CID 9817850.
де Кан, Доминик ; Грегори, Дэвид А.; Пуллман, Норман Дж. (1981), «Булев ранг матриц нуль-единица», в Cadogan, Charles C. (ред.), Proc. 3rd Caribbean Conference on Combinatorics and Computing , Кафедра математики, Университет Вест-Индии, стр. 169–173, MR 0657202.
Эрдеш, Пол ; Симоновиц, Миклош (1980), «О хроматическом числе геометрических графов» (PDF) , Ars Combinatoria , 9 : 229–246, MR 0582295.
Фюрер, Мартин (1995), «Улучшенные результаты определения твёрдости для аппроксимации хроматического числа», Труды IEEE 36th Annual Foundations of Computer Science , стр. 414–421, doi :10.1109/SFCS.1995.492572, ISBN 978-0-8186-7183-8, S2CID 195870010.
Джонсон, Д.С. (1974), «Поведение алгоритмов раскраски графов в наихудшем случае», Труды 5-й Юго-восточной конференции по комбинаторике, теории графов и вычислениям, Utilitas Mathematicae , Виннипег, стр. 513–527, MR 0389644{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
Кубале, М. (2004), Раскраска графов , Американское математическое общество, ISBN 978-0-8218-3458-9, МР 2074481
Матоушек, Йиржи (1996), «Об искажении, необходимом для вложения конечных метрических пространств в нормированные пространства», Israel Journal of Mathematics , 93 (1): 333–344, doi :10.1007/BF02761110, MR 1380650, S2CID 121050316.
Миклавич, Штефко; Поточник, Примож (2003), «Дистанционно-регулярные циркулянты», Европейский журнал комбинаторики , 24 (7): 777–784, doi : 10.1016/S0195-6698(03)00117-3, MR 2009391.

Внешние ссылки

Вайсштейн, Эрик В. «Crown Graph». MathWorld .