У теорії графів графом гіперкуба Qn називається регулярний граф з 2n вершинами 2n 1n ребрами і n ребрами що сходяться в

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

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

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

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

Побудова

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

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

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

Приклади

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

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

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

Властивості

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Завдання

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

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

Див. також

Примітки

Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, с. 68, ISBN .
W. H. Mills. Some complete cycles on the n-cube. — American Mathematical Society, 1963. — Т. 14, вип. 4. — С. 640–643. — DOI:10.2307/2034292.
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.
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:10.1016/0898-1221(88)90213-1.
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.
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.

[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.

[ringel-5] G. Ringe. ber drei kombinatorische Probleme am n-dimensionalen Wiirfel und Wiirfelgitter. — Abh. Math. Sere. Univ. Hamburg, 1955. — Т. 20. — С. 10-19.

[hhw-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.