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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф гиперкуба
Изображение
Вершин

2n

Рёбер

2n−1n

Диаметр

n

Обхват

4 if n≥2

Автоморфизмы

n! 2n

Хроматическое число

2

Спектр

\{(n - 2 k)^{\binom{n}{k}}; k = 0, \ldots, n\}

Свойства

Симметричный
клетка
граф Мура[en]
дистанционно-регулярный
дистанционно-транзитивный
единичных расстояний
гамильтонов
двудольный

Обозначение

Qn

В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет[en] геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.

Графы гиперкубов не следует путать с кубическими графами, в которых в каждую вершину сходится ровно три ребра. Единственный гиперкуб, граф которого кубический — это Q3.

Построение[править | править вики-текст]

Построение Q3 путём соединения пар соответствующих вершин двух копий Q2

Граф гиперкуба Qn можно построить из семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом. Также граф можно построить, используя 2n вершин, пометив их n-битными двоичными числами и соединив пары вершин рёбрами, если расстояние Хэмминга между соответствующими им метками равно 1. Эти два построения тесно связаны — двоичные числа можно представлять как множества (множество позиций, где стоит единица), и два таких множества отличаются одним элементом, если расстояние Хэмминга между соответствующими двумя двоичными числами равно 1.

Qn+1 можно построить из несвязного объединения двух гиперкубов Qn путём добавления рёбер от каждой вершины одной копии Qn до соответствующей вершины другой копии, как показано на рисунке. Соединяющие рёбра образуют паросочетание.

Ещё одно определение Qnпрямое произведение n полных графов K2, содержащих две вершины.

Примеры[править | править вики-текст]

Граф Q0 состоит из единственной вершины, граф Q1 является полным графом с двумя вершинами, а Q2цикл длины 4.

Граф Q3 — это 1-скелет[en] куба, планарный граф с восьмью вершинами и двенадцатью рёбрами.

Граф Q4 — это граф Леви конфигурации Мёбиуса.

Свойства[править | править вики-текст]

Двудольность[править | править вики-текст]

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

Гамильтоновы циклы[править | править вики-текст]

Любой гиперкуб Qn с n > 1 имеет гамильтонов цикл, проходящий через каждую вершину ровно один раз. Вдобавок, гамильтонов путь между вершинами u,v существует тогда и только тогда, когда u и v имеют различные цвета в двухцветной раскраске графа. Оба факта легко проверить по индукции по размерности гиперграфа с построением графа гиперкуба путём соединения двух меньших гиперкубов.

Вышеописанные свойства гиперкуба тесно связаны с теорией кодов Грея. Более точно, существует биективное соответствие между множеством n-битных циклических кодов Грея и множеством гамильтоновых циклов в гиперкубе Qn.[1] Аналогичное свойство имеет место для ацикличных n-битных кодов Грея и гамильтоновых путей.

Меньше известен факт, что любое совершенное паросочетание в гиперкубе можно раширить до гамильтонова цикла.[2] Вопрос, можно ли любое паросочетание расширить до гамильтонова цикла, остаётся открытым.[3]

Другие свойства[править | править вики-текст]

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

  • имеет более чем 22n-2 совершенных паросочетаний (это другое следствие, следующее из индуктивного построения);
  • является планарным (может быть нарисован без пересечений) в том и только в том случае, когда n ≤ 3. Для больших значений n гиперкуб имеет род (n-4)2^{n-3}+1[4][5];
  • известно, что ахроматическое число графа Qn пропорционально \sqrt{n2^n}, но точная константа пропорциональности неизвестна[6];
  • собственные значения матрицы инцидентности равны (-n,-n+2,-n+4,...,n-4,n-2,n), а собственные значения матрицы Кирхгофа графа равны (0,2,...,2n);

Задачи[править | править вики-текст]

Задача поиска самого длинного пути[en] или цикла, являющегося порождённым подграфом заданного графа гиперкуба, известна как задача о змее в кубе[en].

Гипотеза Шиманского[en] касается пригодности гиперкуба в качестве сетевой топологии обмена данными. Гипотеза утверждает, что как бы ни переставляли вершины графа, всегда существует такие (направленные) пути, соединяющие вершины с их образами, что никакие два пути, соединяющие разные вершины, не проходят по одному и тому же ребру в том же направлении[8].

Смотрите также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Mills Some complete cycles on the n-cube // Proceedings of the American Mathematical Society. — American Mathematical Society, 1963. — В. 4. — Т. 14. — С. 640–643. — DOI:10.2307/2034292.
  2. 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.
  3. Ruskey, F. and Savage, C. Matchings extend to Hamiltonian cycles in hypercubes on Open Problem Garden. 2007.
  4. G. Ringel ber drei kombinatorische Probleme am n-dimensionalen Wiirfel und Wiirfelgitter // Abh. Math. Sere. Univ. Hamburg. — 1955. — Т. 20. — С. 10-19.
  5. 1 2 Frank Harary, John P. Hayes, Horng-Jyh Wu A survey of the theory of hypercube graphs // Computers & Mathematics with Applications. — 1988. — В. 4. — Т. 15. — С. 277–289. — DOI:10.1016/0898-1221(88)90213-1.
  6. Y. Roichman {{{заглавие}}} // Journal of Combinatorial Theory, Series B. — 2000. — В. 2. — Т. 79. — С. 177–182. — DOI:10.1006/jctb.2000.1955.
  7. Optimal Numberings and Isoperimetric Problems on Graphs, L.H. Harper, Journal of Combinatorial Theory, 1, 385–393, DOI:10.1016/S0021-9800(66)80059-5
  8. Ted H. Szymanski Proc. Internat. Conf. on Parallel Processing. — Silver Spring, MD: IEEE Computer Society Press, 1989. — Т. 1. — С. 103–110..

Ссылки[править | править вики-текст]

  • F. Harary, J. P. Hayes, H.-J. Wu A survey of the theory of hypercube graphs // Computers & Mathematics with Applications. — 1988. — В. 4. — Т. 15. — С. 277–289. — DOI:10.1016/0898-1221(88)90213-1.