Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

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

Граф гіперкуба
Вершин2n
Ребер2n−1n
Діаметрn
Обхват4, якщо n≥2
Автоморфізмn! 2n
Хроматичне число2
Спектр
Властивостісиметричний
клітка
граф Мура
дистанційно-регулярний граф
граф одиничних відстаней
гамільтонів граф
двочастковий граф

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

Побудова

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

Граф гіперкуба 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] стосується придатності гіперкуба як мережевої топології обміну даними. Гіпотеза стверджує, що як би не переставляли вершини графа, завжди існують такі (спрямовані) шляхи, які з'єднують вершини з їхніми образами, що ніякі два шляхи, які з'єднують різні вершини, не проходять по одному й тому ж ребру в тому ж напрямку[9].

Див. також

ред.

Примітки

ред.
  1. Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, с. 68, ISBN 978-0-691-15498-5.
  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.