Граф гіперкуба
У теорії графів графом гіперкуба Qn називається регулярний граф з 2n вершинами, 2n−1n ребрами і n ребрами, що сходяться в одній вершині. Його можна отримати як одновимірний кістяк геометричного гіперкуба. Наприклад, кубічний граф Q3 — це граф, утворений 8 вершинами і 12 ребрами тривимірного куба. Граф можна отримати іншим чином, відштовхуючись від сімейства підмножин множини з n елементами шляхом використання як вершин всі підмножини і з'єднанням двох вершин ребром, якщо відповідні множини відрізняються тільки одним елементом.
Граф гіперкуба | |
---|---|
Вершин | 2n |
Ребер | 2n−1n |
Діаметр | n |
Обхват | 4, якщо n≥2 |
Автоморфізм | n! 2n |
Хроматичне число | 2 |
Спектр | |
Властивості | симетричний клітка граф Мура дистанційно-регулярний граф граф одиничних відстаней гамільтонів граф двочастковий граф |
Графи гіперкубів не слід плутати з кубічними графами, в яких у кожну вершину сходиться рівно три ребра. Єдиний гіперкуб, граф якого кубічний — це Q3.
Побудова
ред.Граф гіперкуба Qn можна побудувати з сімейства підмножин множини з n елементами шляхом використання як вершин всі підмножини і з'єднанням двох вершин ребром, якщо відповідні множини відрізняються тільки одним елементом. Також граф можна побудувати, використовуючи 2n вершин, позначивши їх n-бітними двійковими числами і з'єднавши пари вершин ребрами, якщо відстань Геммінга між відповідними їм мітками дорівнює 1. Ці дві побудови тісно пов'язані — двійкові числа можна представляти як множини (множин позицій, де стоїть одиниця), і дві таких множини відрізняються одним елементом, якщо відстань Геммінга між відповідними двома двійковими числами дорівнює 1.
Qn+1 можна побудувати з незв'язного об'єднання двох гіперкубів Qn шляхом додавання ребер від кожної вершини однієї копії Qn до відповідної вершини іншої копії, як показано на малюнку. З'єднують ребра утворюють парування.
Ще одне визначення Qn — Декартів добуток множин n повних графів K2, містять дві вершини.
Приклади
ред.Граф Q0 складається з єдиної вершини, граф Q1 є повний граф з двома вершинами, а Q2 — цикл довжини 4.
Граф Q3 — це n-кістяк куба, планарний граф з вісьмома вершинами і дванадцятьма ребрами.
Граф Q4 — це граф Леві конфігурації Мебіуса. Він також є графом ходів коня для тороїдальної шахівниці .[1]
Властивості
ред.Двудольність
ред.Всі графи гіперкубів є двочастковими — їх вершини можна розфарбувати тільки двома кольорами. Два кольори цієї розмальовки можна знайти з побудови підмножин графів гіперкубів шляхом привласнення одного кольору підмножини, які мають парне число елементів і іншого кольору підмножини, що мають непарну кількість елементів.
Гамільтонові цикли
ред.Будь-який гіперкуб Qn с n > 1 має гамільтонів цикл, що проходить через кожну вершину рівно один раз. В додаток, гамільтонів шлях між вершинами U, V існує тоді і тільки тоді, коли u и v мають різні кольори в двокольоровому розфарбуванні графа. Обидва факти легко перевірити по індукції по розмірності гіперграфа з побудовою графа гіперкуба шляхом з'єднання двох менших гіперкубів.
Вищеописані властивості гіперкуба тісно пов'язані з теорією кодів Грея. Більш точно, існує бієкційна відповідність між множиною n-бітних циклічних кодів Грея і множиною гамільтонових циклів в гіперкубі Qn.[2] Аналогічна властивість має місце для ациклічності n-бітних кодів Грея і гамільтонових шляхів.
Менш відомий факт, що будь-яке зроблене паросполучення в гіперкубі можна розширити до Гамільтона циклу.[3] Питання, чи можна будь-яке паросполучення розширити до Гамільтона циклу, залишається відкритим.[4]
Інші властивості
ред.Граф гіперкуба Qn (n > 1) :
- є діаграмою Хассе кінцевої булевої алгебри;
- є медійним графом. Будь який медійний граф є ізометричним підграфом гіперкуба[en] і може бути утворений шляхом усічення гіперкуба;
- має більш ніж 22n-2 зроблених паросполучень (це інший наслідок, наступне з індуктивного побудови);
- є транзитивним щодо дуг та симетричним. Симетрії графів гіперкубів можна представити як знакові перестановки[en];
- містить всі цикли довжини 4, 6, …, 2n і тому є біпанциклічним графом;
- може бути намальований як граф одиничних відстаней на евклідовій площині шляхом вибору одиничного вектора для кожного елемента множини і розміщення кожної вершини, відповідно множини S, як суму векторів із S;
- є вершинним n-зв'язковим графом за теоремою Балинського[en];
- є планарним (Може бути намальований без перетинів) в тому і тільки в тому випадку, коли n ≤ 3. Для великих значень n гіперкуб має рід [5][6];
- має в точності — кістякове дерево[6];
- сімейство Qn (n > 1) є сімейством графів Леві[en];
- відомо, що ахроматичне число графа Qn пропорційне , але точна константа пропорційності невідома[7];
- ширина смуги[en] графа Qn точно дорівнює .[8];
- власні значення матриці інцидентності рівні (-n, -n + 2, + 4 -n, …, п-4, п-2, п), а власні значення матриці Кірхгофа графа рівні (0,2, …, 2n);
- Ізопериметричне число дорівнює h(G)=1.
Завдання
ред.Задача пошуку найдовшого шляху або циклу, що є породженим підграфом заданого графа гіперкуба, відома як задача про змія в кубі.
Гіпотеза Шиманського[en] стосується придатності гіперкуба як мережевої топології обміну даними. Гіпотеза стверджує, що як би не переставляли вершини графа, завжди існують такі (спрямовані) шляхи, які з'єднують вершини з їхніми образами, що ніякі два шляхи, які з'єднують різні вершини, не проходять по одному й тому ж ребру в тому ж напрямку[9].
Див. також
ред.Примітки
ред.- ↑ Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, с. 68, ISBN 978-0-691-15498-5.
- ↑ W. H. Mills. Some complete cycles on the n-cube. — American Mathematical Society, 1963. — Т. 14, вип. 4. — С. 640–643. — DOI: .
- ↑ J. Fink. Perfect matchings extend to Hamiltonian cycles in hypercubes. — Journal of Combinatorial Theory, Series B, 2007. — Т. 97. — С. 1074–1076. — DOI: .
- ↑ Ruskey, F. and Savage, C.
- ↑ G. Ringe. ber drei kombinatorische Probleme am n-dimensionalen Wiirfel und Wiirfelgitter. — Abh. Math. Sere. Univ. Hamburg, 1955. — Т. 20. — С. 10-19.
- ↑ а б Frank Harary, John P. Hayes, Horng-Jyh Wu. A survey of the theory of hypercube graphs. — Computers & Mathematics with Applications, 1988. — Т. 15, вип. 4. — С. 277–289. — DOI: .
- ↑ Y. Roichman. On the Achromatic Number of Hypercubes. — Journal of Combinatorial Theory, Series B, 2000. — Т. 79, вип. 2. — С. 177–182. — DOI: .
- ↑ Optimal Numberings and Isoperimetric Problems on Graphs, L.
- ↑ Ted H. Szymanski. On the Permutation Capability of a Circuit-Switched Hypercube // Proc. Internat. Conf. on Paralle. — IEEE Computer Society Press, 1989. — Т. 1. — С. 103–110.