WikiSort.ru - Не сортированное

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

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

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

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

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

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

Другие свойства

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

• является диаграммой Хассе конечной булевой алгебры;
• является медианным графом. Любой медианный граф является изометричным подграфом гиперкуба и может быть образован путём усечения гиперкуба;
• имеет более чем 2^2n-2 совершенных паросочетаний (это другое следствие, следующее из индуктивного построения);
• является транзитивным относительно дуг и симметричным. Симметрии графов гиперкубов можно представить как знаковые перестановки^[en];
• содержит все циклы длины 4, 6, …, 2ⁿ и поэтому является бипанциклическим графом;
• может быть нарисован как граф единичных расстояний на евклидовой плоскости путём выбора единичного вестора для каждого элемента множества и размещения каждой вершины, соответствующей множеству S, как сумму^[что?] векторов из S;
• является вершинно n-связным графом по теореме Балинского;
• является планарным (может быть нарисован без пересечений) в том и только в том случае, когда n ≤ 3. Для больших значений n гиперкуб имеет род ${\displaystyle (n-4)2^{n-3}+1}$ ^[4][5];

• имеет в точности ${\displaystyle 2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$ остовных дерева^[5];
• семейство Q_n (n > 1) является семейством графов Леви^[en];
• известно, что ахроматическое число графа Q_n пропорционально ${\displaystyle {\sqrt {n2^{n}}}}$ , но точная константа пропорциональности неизвестна^[6];

• ширина полосы^[en] графа Q_n в точности равна ${\displaystyle \sum _{i=0}^{n}{\binom {n}{\lfloor n/2\rfloor }}}$ .^[7];
• собственные значения матрицы инцидентности равны (-n,-n+2,-n+4,…,n-4,n-2,n), а собственные значения матрицы Кирхгофа графа равны (0,2,…,2n);
• изопериметрическое число равно h(G)=1.