Граф гіперкуба

У теорії графів графом гіперкуба Q_n називається регулярний граф з 2ⁿ вершинами, 2ⁿ⁻¹n ребрами і n ребрами, що сходяться в одній вершині. Його можна отримати як одновимірний кістяк геометричного гіперкуба. Наприклад, кубічний граф Q₃ — це граф, утворений 8 вершинами і 12 ребрами тривимірного куба. Граф можна отримати іншим чином, відштовхуючись від сімейства підмножин множини з n елементами шляхом використання як вершин всі підмножини і з'єднанням двох вершин ребром, якщо відповідні множини відрізняються тільки одним елементом.

Граф гіперкуба
Вершин	2^n
Ребер	2^n−1n
Діаметр	n
Обхват	4, якщо n≥2
Автоморфізм	n! 2^n
Хроматичне число	2
Спектр	${\displaystyle \{(n-2k)^{\binom {n}{k}};k=0,\ldots ,n\}}$
Властивості	симетричний клітка граф Мура дистанційно-регулярний граф граф одиничних відстаней гамільтонів граф двочастковий граф

Графи гіперкубів не слід плутати з кубічними графами, в яких у кожну вершину сходиться рівно три ребра. Єдиний гіперкуб, граф якого кубічний — це Q₃.

Побудова

Побудова Q3 шляхом з'єднання пар відповідних вершин двох копій Q2

Граф гіперкуба Q_n можна побудувати з сімейства підмножин множини з n елементами шляхом використання як вершин всі підмножини і з'єднанням двох вершин ребром, якщо відповідні множини відрізняються тільки одним елементом. Також граф можна побудувати, використовуючи 2n вершин, позначивши їх n-бітними двійковими числами і з'єднавши пари вершин ребрами, якщо відстань Геммінга між відповідними їм мітками дорівнює 1. Ці дві побудови тісно пов'язані — двійкові числа можна представляти як множини (множин позицій, де стоїть одиниця), і дві таких множини відрізняються одним елементом, якщо відстань Геммінга між відповідними двома двійковими числами дорівнює 1. 

Q_n+1 можна побудувати з незв'язного об'єднання двох гіперкубів Qn шляхом додавання ребер від кожної вершини однієї копії Q_n до відповідної вершини іншої копії, як показано на малюнку. З'єднують ребра утворюють парування.

Ще одне визначення Q_n — Декартів добуток множин n повних графів K₂, містять дві вершини.

Приклади

Граф Q₀ складається з єдиної вершини, граф Q₁ є повний граф з двома вершинами, а Q₂ — цикл довжини 4.

Граф Q₃ — це n-кістяк куба, планарний граф з вісьмома вершинами і дванадцятьма ребрами.

Граф Q₄ — це граф Леві (конфігурації Мебіуса). Він також є графом ходів коня для тороїдальної шахівниці ${\displaystyle 4\times 4}$.

Властивості

Двудольність

Всі графи гіперкубів є двочастковими — їх вершини можна розфарбувати тільки двома кольорами. Два кольори цієї розмальовки можна знайти з побудови підмножин графів гіперкубів шляхом привласнення одного кольору підмножини, які мають парне число елементів і іншого кольору підмножини, що мають непарну кількість елементів.

Гамільтонові цикли

Будь-який гіперкуб Q_n с n > 1 має гамільтонів цикл, що проходить через кожну вершину рівно один раз. В додаток, гамільтонів шлях між вершинами U, V існує тоді і тільки тоді, коли u и v мають різні кольори в двокольоровому розфарбуванні графа. Обидва факти легко перевірити по індукції по розмірності гіперграфа з побудовою графа гіперкуба шляхом з'єднання двох менших гіперкубів.

Вищеописані властивості гіперкуба тісно пов'язані з теорією кодів Грея. Більш точно, існує бієкційна відповідність між множиною n-бітних циклічних кодів Грея і множиною гамільтонових циклів в гіперкубі Q_n. Аналогічна властивість має місце для ациклічності n-бітних кодів Грея і гамільтонових шляхів.

Менш відомий факт, що будь-яке зроблене паросполучення в гіперкубі можна розширити до Гамільтона циклу. Питання, чи можна будь-яке паросполучення розширити до Гамільтона циклу, залишається відкритим.

Інші властивості

Граф гіперкуба Q_n (n > 1) :

• є діаграмою Хассе кінцевої булевої алгебри;

• є . Будь який медійний граф є ^[en] і може бути утворений шляхом усічення гіперкуба;

• має більш ніж 2^2n-2 зроблених паросполучень (це інший наслідок, наступне з індуктивного побудови);

• є транзитивним щодо дуг та симетричним. Симетрії графів гіперкубів можна представити як ^[en];

• містить всі цикли довжини 4, 6, …, 2n і тому є ;
• може бути намальований як граф одиничних відстаней на евклідовій площині шляхом вибору одиничного вектора для кожного елемента  множини і розміщення кожної вершини, відповідно множини S, як суму векторів із S;

• є вершинним n-зв'язковим графом за ^[en];

• є планарним (Може бути намальований без перетинів) в тому і тільки в тому випадку, коли n ≤ 3. Для великих значень n гіперкуб має рід ${\displaystyle (n-4)2^{n-3}+1}$;

• має в точності ${\displaystyle 2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$ — кістякове дерево;

• сімейство Q_n (n > 1) є ^[en];

• відомо, що (ахроматичне число) графа Q_n пропорційне ${\displaystyle {\sqrt {n2^{n}}}}$, але точна константа пропорційності невідома;

• ^[en] графа Q_n точно дорівнює ${\displaystyle \sum _{i=0}^{n}{\binom {n}{\lfloor n/2\rfloor }}}$.;

• власні значення матриці інцидентності рівні (-n, -n + 2, + 4 -n, …, п-4, п-2, п), а власні значення матриці Кірхгофа графа рівні (0,2, …, 2n);

• (Ізопериметричне число) дорівнює h(G)=1.

Завдання

Задача пошуку найдовшого шляху або циклу, що є породженим підграфом заданого графа гіперкуба, відома як задача (про змія в кубі).

^[en] стосується придатності гіперкуба як мережевої топології обміну даними. Гіпотеза стверджує, що як би не переставляли вершини графа, завжди існують такі (спрямовані) шляхи, які з'єднують вершини з їхніми образами, що ніякі два шляхи, які з'єднують різні вершини, не проходять по одному й тому ж ребру в тому ж напрямку.

Див. також

• ^[en]
• Куб Фібоначчі
• ^[en]
• ^[en]
• (Універсальний граф)
• (Граф Геммінга)

Примітки

1. Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, с. 68, ISBN .
2. W. H. Mills. Some complete cycles on the n-cube. — American Mathematical Society, 1963. — Т. 14, вип. 4. — С. 640–643. — DOI:10.2307/2034292.
3. J. Fink. Perfect matchings extend to Hamiltonian cycles in hypercubes. — Journal of Combinatorial Theory, Series B, 2007. — Т. 97. — С. 1074–1076. — DOI:10.1016/j.jctb.2007.02.007.
4. Ruskey, F. and Savage, C.
5. G. Ringe. ber drei kombinatorische Probleme am n-dimensionalen Wiirfel und Wiirfelgitter. — Abh. Math. Sere. Univ. Hamburg, 1955. — Т. 20. — С. 10-19.
6. 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:10.1016/0898-1221(88)90213-1.
7. Y. Roichman. On the Achromatic Number of Hypercubes. — Journal of Combinatorial Theory, Series B, 2000. — Т. 79, вип. 2. — С. 177–182. — DOI:10.1006/jctb.2000.1955.
8. Optimal Numberings and Isoperimetric Problems on Graphs, L.
9. 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.