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

У теорії графів графом гіперкуба 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}^{(\genfrac{}{}{0ex}{}{n}{k})}$ — кістякове дерево;
• сімейство Q_n (n > 1) є Шаблон:Нп;
• відомо, що ахроматичне число графа Q_n пропорційне $\sqrt{n{2}^n}$, але точна константа пропорційності невідома;

• Шаблон:Нп графа Q_n точно дорівнює $\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })$.;
• власні значення матриці інцидентності рівні (-n, -n + 2, + 4 -n, …, п-4, п-2, п), а власні значення матриці Кірхгофа графа рівні (0,2, …, 2n);
• Ізопериметричне число дорівнює h(G)=1.

Завдання

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

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

Див. також

• Шаблон:Нп
• Куб Фібоначчі
• Шаблон:Нп
• Шаблон:Нп
• Універсальний граф
• Граф Геммінга