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

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

У теорії графів графом гіперкуба Q_n називається регулярний граф з 2ⁿ вершинами, 2ⁿ⁻¹n ребрами і n ребрами, що сходяться в одній вершині. Його можна отримати як одновимірний кістяк геометричного гіперкуба. Наприклад, кубічний граф Q₃ — це граф, утворений 8 вершинами і 12 ребрами тривимірного куба. Граф можна отримати іншим чином, відштовхуючись від сімейства підмножин множини з 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₄ — це граф Леві конфігурації Мебіуса. Він також є графом ходів коня для тороїдальної шахівниці $4\times 4$.

Властивості

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

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

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

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

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

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

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

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

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

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

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

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

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

• є вершинним n-зв'язковим графом за теоремою Балинського;

• є планарним (Може бути намальований без перетинів) в тому і тільки в тому випадку, коли 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) є сімейством графів Леві;

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

• ширина смуги графа 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.

Завдання

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

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

Див. також

• Кубічно з'єднані цикли
• Куб Фібоначчі
• Складений граф куба
• Половинний граф куба
• Універсальний граф
• Граф Геммінга