4.7.1. Булев гиперкуб

Булево пространство М можно представить в виде графа, вершины которого соответствуют элементам пространства, а ребра представляют отношение соседства между элементами пространства. Два вектора являются соседними, если они отличаются друг от друга значением только одной компоненты. Например, векторы (1 0 0 1) и (1 1 0 1), значения одноименных компонент которых, кроме одной второй компоненты, совпадают, являются соседними. Данный граф, представляющий п-мерное булево пространство, имеет 2^п вершин и п2^п – 1 ребер. Он называется полным булевым графом, или п-мерным гиперкубом. Рассмотрим построение такого гиперкуба для различных значений размерности пространства.

Одномерный гиперкуб состоит из двух вершин, связанных ребром. Одной из этих вершин приписывается константа 0, другой – константа 1, которые являются кодами данных вершин. Чтобы получить двумерный гиперкуб, надо продублировать одномерный гиперкуб и каждую вершину исходного гиперкуба соединить ребром с ее дублем. Коды вершин построенного двумерного гиперкуба получаются добавлением нулей справа к кодам вершин исходного гиперкуба и единиц – к кодам дублей вершин. Аналогично получаются трехмерный гиперкуб, четырехмерный гиперкуб и т. д.

Сформулируем общее правило увеличения размерности гиперкуба: для перехода от т-мерного гиперкуба к (т + 1)-мерному надо исходный т-мерный гиперкуб продублировать и каждую вершину исходного гиперкуба соединить ребром с ее дублем. В полученном гиперкубе к кодам вершин исходного т-мерного гиперкуба добавляются справа нули, а к кодам их дублей – единицы.

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