У теорії графів корона з 2n вершинами — неорієнтований граф із двома наборами вершин ui та vi і ребрами між ui та vj, якщо i ≠ j. Можна розглядати корону як повний двочастковий граф, з якого видалено досконале парування, як повного графа, або як двочастковий граф Кнезера Hn,1, що представляє підмножини з 1 елемента і (n − 1) елементів множини з n елементів із ребрами між двома підмножинами, якщо одна підмножина міститься в іншій.
Корона () | |
---|---|
Вершин | 2 n |
Ребер | n (n — 1) |
Радіус | |
Діаметр | |
Обхват | |
Хроматичне число | |
Властивості | дистанційно-транзитивний |
Приклади
Корона з шістьма вершинами утворює цикл, а корона з вісьмома вершинами ізоморфна графу куба. У (подвійний шістці Шлефлі) конфігурації 12 прямих і 30 точок у тривимірному просторі, дванадцять прямих перетинають одна одну за схемою корони з 12 вершинами.
Властивості
Число ребер у короні є (прямокутним числом) n(n − 1). Її ахроматичне число дорівнює n — можна знайти повне розфарбування, вибравши пару {ui, vi} як клас кольору. Корони є симетричними і дистанційно-транзитивними графами. [en] зі співавторами описують розбиття ребер корони на цикли рівної довжини.
Корону з 2n вершинами можна вкласти в чотиривимірний евклідів простір так, що всі її ребра будуть мати довжину одиниця. Однак таке вкладення може помістити несуміжні вершини на відстань одиниця. Вкладення, за якого ребра мають довжину одиниця, а відстань між будь-якими несуміжними вершинами не дорівнює одиниці, вимагає принаймні розмірності n − 2. Це показує, що для подання графа у вигляді графа одиничних відстаней і графа строго одиничних відстаней потрібні зовсім різні розмірності. Найменше число повних двочасткових підграфів, потрібне для покриття ребер корони (її двочасткова розмірність, або розмір найменшого покриття кліками) дорівнює
тобто є оберненою функцією від центрального біноміального коефіцієнта.
Доповненням корони з 2n вершинами є прямий добуток повних графів K2 Kn, що еквівалентно туровому графу 2 × n.
Застосування
В етикеті — традиційних правилах розсаджування гостей за обіднім столом — чоловіки й жінки мають перемежовуватися і жодна сімейна пара не повинна сидіти поруч. Розсаджування, що задовольняє цим правилам для вечірки n сімейних пар, можна описати як гамільтонів цикл корони. Задача підрахунку числа можливих розсаджувань або, що майже те ж саме, числа гамільтонових циклів у короні, відома в комбінаториці як (задача про гостей). Для корон із числом вершин 6, 8, 10, … число (орієнтованих) гамільтонових циклів дорівнює
- 2, 12, 312, 9600, 416880, 23879520, 1749363840, … (послідовність A094047 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)
Корони можна використовувати, щоб показати, що алгоритм жадібного розфарбовування поводиться погано в деяких випадках — якщо вершини корони надані алгоритму в порядку u0, v0, u1, v1, і т. д., то жадібне розфарбовування використовує n кольорів, хоча оптимальним числом кольорів є два. Цю побудову приписують Джонсону, а самі корони іноді називають графами Джонсона з позначенням Jn. Фюрер використав корони як частину побудови, що показує складність апроксимації задачі розфарбовування.
Матушеквикористав відстань у коронах як приклад метричного простору, який важко вкласти в нормований векторний простір.
Як показали Миклавич і Поточник, корони входять до невеликого числа різних типів дистанційно-регулярних циркулянтних графів.
[en] і співавтори описують многокутники, які мають корони як . Вони використовують їх як приклад, щоб показати, що подання графів у вигляді об'єднання повних двочасткових графів не завжди ефективне щодо пам'яті.
Корона з 2n вершинами з ребрами, орієнтованими від одного боку двочасткового графа до іншого, утворює стандартний приклад частково впорядкованої множини з [en] n.
Примітки
- Amitabh Chaudhary, Sundar Vishwanathan. SODA '97: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. — 1997. — С. 558—563.
- D. Archdeacon, M. Debowsky, J. Dinitz, H. Gavlas. Cycle systems in the complete bipartite graph minus a one-factor // [en]. — 2004. — Т. 284, вип. 1—3. — С. 37—43. — DOI: .
- Paul Erdős, Miklós Simonovits. On the chromatic number of geometric graphs // Ars Combinatoria. — 1980. — Т. 9. — С. 229—246.
- 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.
- У задачі про гостей початкова позиція циклу істотна, так що число гамільтонових циклів і розв'язок задачі про гостей відрізняються в 2n разів.
- D. S. Johnson. Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematicae. — Winnipeg, 1974. — С. 513—527.
- M. Kubale. Graph Colorings. — American Mathematical Society, 2004. — .
- Fürer. Proc. 36th IEEE Symp. Foundations of Computer Science (FOCS '95). — 1995. — С. 414—421. — . — DOI: .
- Jiří Matoušek. On the distortion required for embedding finite metric spaces into normed spaces // Israel Journal of Mathematics. — 1996. — Т. 93, вип. 1. — С. 333—344. — DOI: .
- Štefko Miklavič, Primož Poročnik. Distance-regular circulants // European Journal of Combinatorics. — 2003. — Т. 24, вип. 7. — С. 777—784. — DOI: .
- Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri. Can visibility graphs be represented compactly? // Discrete and Computational Geometry. — 1994. — Т. 12, вип. 1. — С. 347—365. — DOI: .
Посилання
- Weisstein, Eric W. Граф корона(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет