Корона (теория графов)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Короны с шестью, восемью и десятью вершинами
вершин = 2 n
рёбер = n (n - 1)
хроматическое число = \left\{\begin{array}{ll}1 & n = 1\\ 2 & \text{otherwise}\end{array}\right.
радиус = \left\{\begin{array}{ll}\infty & n \le 2\\ 3 & \text{otherwise}\end{array}\right.
диаметр = \left\{\begin{array}{ll}\infty & n \le 2\\ 3 & \text{otherwise}\end{array}\right.
обхват = \left\{\begin{array}{ll}\infty & n \le 2\\ 6 & n = 3\\ 4 & \text{otherwise}\end{array}\right.
свойства = дистанционно-транзитивный
обозначение = S_n^0

В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом[en] полного графа, или как двудольный граф Кнезера[en] Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом.

Примеры[править | править вики-текст]

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

Свойства[править | править вики-текст]

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

Число рёбер в короне является прямоугольным числом n(n − 1). Её ахроматическое число равно n – можно найти полную раскраску путём выбора пары {ui, vi} в качестве классов цвета.[1] Короны являются симметричными и дистанционно-транзитивными графами. Архдьякон с соавторами (Archdeacon, Debowsky, Dinitz, Gavlas, 2004) [2] описывают разбиение рёбер короны на циклы равной длины.

Корону с 2n вершинами можно вложить в четырёхмерное евклидово пространство так, что все её рёбра будут иметь длину единица. Однако такое вложение может поместить несмежные вершины на расстояние единица. Вложение, при котором рёбра имеют длину единица, а расстояние между любыми несмежными вершинами не равно единице, требует как минимум размерности n − 2. Это показывает, что для представления графа в виде графа единичных расстояний и графа строго единичных расстояний требуются совсем различные размерности.[3] Минимальное число полных двудольных подграфов, требующихся для покрытия рёбер короны (её двудольная размерность[en], или размер минимального покрытия кликами) равно

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

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

Дополнением короны с 2n вершинами является прямое произведением полных графов K2 \square Kn, что эквивалентно ладейному графу 2 × n.

Приложение[править | править вики-текст]

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

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

Короны можно использовать, чтобы показать, что алгоритм жадной раскраски ведёт себя плохо в некоторых случаях – если вершины короны представлены алгоритму в порядке u0, v0, u1, v1, и т.д., то жадная раскраска использует n цветов, хотя оптимальным числом цветов является два. Это построение приписывается Джонсону (Johnson, 1974) [6], а сами короны иногда называют графами Джонсона с обозначением Jn.[7] Фюрер (Fürer, 1995) [8] использовал короны как часть построения, показывающего сложность аппроксимации задачи раскраски.

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

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

Агарвал и соавторы (Agarwal, Alon, Aronov, Suri, 1994)) [11] описывают многоугольники, имеющие короны в качестве графов видимости[en]. Они используют их в качестве примера, чтобы показать, что представление графов в виде объединения полных двудольных графов не всегда эффективно по памяти.

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

Замечания[править | править вики-текст]

  1. Amitabh Chaudhary, Sundar Vishwanathan SODA '97: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. — 1997. — С. 558–563..
  2. D. Archdeacon, M. Debowsky, J. Dinitz, H. Gavlas Cycle systems in the complete bipartite graph minus a one-factor // Discrete Mathematics[en]. — 2004. — В. 1–3. — Т. 284. — С. 37–43. — DOI:10.1016/j.disc.2003.11.021.
  3. Paul Erdős, Miklós Simonovits On the chromatic number of geometric graphs // Ars Combinatoria. — 1980. — Т. 9. — С. 229–246..
  4. Dominique de Caen, David A. Gregory, Norman J. Pullman Proc. 3rd Caribbean Conference on Combinatorics and Computing / ред. Charles C. Cadogan. — Department of Mathematics, University of the West Indies, 1981. — С. 169–173..
  5. В задаче о гостях начальная позиция цикла существенна, так что число гамильтоновых циклов и решение задачи о гостях различаются в 2n раз.
  6. D. S. Johnson Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematicae. — Winnipeg, 1974. — С. 513–527.
  7. M. Kubale Graph Colorings. — American Mathematical Society, 2004. — ISBN 0-8218-3458-4
  8. Fürer Proc. 36th IEEE Symp. Foundations of Computer Science (FOCS '95). — 1995. — С. 414–421. — ISBN 0-8186-7183-1. — DOI:10.1109/SFCS.1995.492572.
  9. Jiří Matoušek On the distortion required for embedding finite metric spaces into normed spaces // Israel Journal of Mathematics. — 1996. — В. 1. — Т. 93. — С. 333–344. — DOI:10.1007/BF02761110.
  10. Štefko Miklavič, Primož Poročnik Distance-regular circulants // European Journal of Combinatorics. — 2003. — В. 7. — Т. 24. — С. 777–784. — DOI:10.1016/S0195-6698(03)00117-3.
  11. Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri Can visibility graphs be represented compactly? // Discrete and Computational Geometry. — 1994. — В. 1. — Т. 12. — С. 347–365. — DOI:10.1007/BF02574385.

Ссылки[править | править вики-текст]

External links[править | править вики-текст]