EssayAI
Блог
Блог
Естественные науки

Булев куб: вершины, рёбра и расстояние Хэмминга

8 ноября 2026Время чтения: 8 минут
#булев куб#дискретная математика#двоичные наборы#расстояние Хэмминга#булевы функции
Булев куб: вершины, рёбра и расстояние Хэмминга

Булев куб - это множество всех двоичных наборов одинаковой длины, в котором два набора соединены ребром, если отличаются ровно одним битом. Он превращает таблицу из нулей и единиц в наглядную карту: вершина обозначает состояние, а переход по ребру меняет одну координату. Такой язык помогает изучать булевы функции, коды и алгоритмы перебора.

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

Из битов в вершины

Пусть nn - число координат. Булев куб размерности nn обозначают {0,1}n\{0,1\}^n; каждая его вершина записывается как (x1,…,xn)(x_1,\ldots,x_n), где каждый xix_i равен нулю или единице. Порядок важен: 0101 и 1010 - разные вершины. Определение используют, например, в конспекте курса MIT по комбинаторике.

При n=1n=1 получаются два набора, 00 и 11, соединённые отрезком. При n=2n=2 четыре набора образуют квадрат: из 0000 можно попасть в 0101 или 1010, но не напрямую в 1111. При n=3n=3 восемь троек дают обычный каркас куба. Для четырёх и более координат определение остаётся тем же, хотя рисунок уже будет проекцией многомерного объекта на плоскость.

Маркер проходит от 000 к 111 по трём рёбрам и возвращается: на каждом шаге меняется ровно один бит.

На видео выбран путь 000→100→110→111000 \to 100 \to 110 \to 111. Он не единственный: можно менять три координаты в другом порядке. Важно, что каждое нарисованное ребро соответствует изменению одной координаты, а пересечение линий на проекции само по себе не создаёт новую вершину.

Для ручного построения полезно сначала выписать все наборы в фиксированном порядке и проверить соседство сравнением по позициям. Для каждой пары отметьте, сколько разрядам нужны изменения. Если различие одно, проведите ребро; если различий больше или нет вовсе, ребро не нужно. Такой способ не зависит от того, насколько близко точки оказались на рисунке. Геометрическая близость на листе может обмануть, поэтому подписи вершин важнее внешнего вида проекции.

Как посчитать вершины и рёбра

У каждой из nn координат два независимых варианта, поэтому число вершин равно

∣V∣=2n.|V|=2^n.

Из каждой вершины выходит ровно nn рёбер: можно переключить любую одну из nn координат. Если сложить степени всех вершин, получим n2nn2^n, но каждое ребро окажется посчитанным дважды, по одному разу с каждого конца. Поэтому при n≥1n\geq 1

∣E∣=n2n2=n2n−1.|E|=\frac{n2^n}{2}=n2^{n-1}.

Например, в Q3Q_3 восемь вершин, у каждой по три соседа, и рёбер 8⋅3/2=128\cdot3/2=12. В Q4Q_4 уже 16 вершин и 32 ребра. Для n=0n=0 отдельно получают одну пустую последовательность и ни одного ребра. Экспонента в числе вершин объясняет, почему полный перебор быстро становится дорогим: добавление одного бита удваивает число возможных входов.

Ещё один способ построить QnQ_n - взять две копии Qn−1Q_{n-1}, приписать всем вершинам одной копии ноль, другой - единицу, а затем соединить соответствующие пары. Внутри копии меняются старые координаты, между копиями - новая. Так два квадрата с четырьмя соединениями дают трёхмерный куб; два таких куба дают граф Q4Q_4.

Расстояние Хэмминга и кратчайший путь

Расстояние Хэмминга d(x,y)d(x,y) - количество позиций, в которых равные по длине наборы различаются. Например, 01010101 и 11101110 отличаются в первой, третьей и четвёртой позициях, поэтому d(0101,1110)=3d(0101,1110)=3. Один кратчайший путь:

0101→1101→1111→1110.0101\to1101\to1111\to1110.

Число шагов кратчайшего пути по рёбрам совпадает с расстоянием Хэмминга. Доказательство состоит из двух частей. Каждый из различающихся битов необходимо хотя бы раз изменить, значит, меньше dd шагов не хватит. С другой стороны, можно последовательно переключить ровно эти dd битов и прийти в цель за dd шагов. Для противоположных вершин 000000 и 111111 расстояние равно трём; больше трёх в Q3Q_3 быть не может.

Если различаются dd позиций, существует d!d! кратчайших путей: достаточно выбрать порядок переключения этих позиций. Для 000000 и 111111 их 3!=63!=6. Повторное переключение бита тоже даёт допустимый маршрут, но делает его длиннее кратчайшего.

Слои вокруг вершины

Зафиксируем вершину 00000000 в Q4Q_4. На расстоянии kk от неё лежат наборы с ровно kk единицами. Чтобы построить такой набор, нужно выбрать kk позиций из четырёх; число способов равно биномиальному коэффициенту (4k)\binom{4}{k}. Получаются слои 1,4,6,4,11,4,6,4,1 для расстояний от нуля до четырёх.

Пять слоёв четырёхмерного булева куба: на расстояниях от 0 до 4 находятся 1, 4, 6, 4 и 1 вершина
Пять слоёв четырёхмерного булева куба: на расстояниях от 0 до 4 находятся 1, 4, 6, 4 и 1 вершина

Например, на расстоянии два находятся 11001100, 10101010, 10011001, 01100110, 01010101 и 00110011. Их шесть; сумма размеров всех пяти слоёв равна 1616. В общем случае на расстоянии kk от любой выбранной вершины находится (nk)\binom{n}{k} вершин: надо выбрать координаты, которые будут отличаться от исходных. Симметрия слоёв следует из равенства (nk)=(nn−k)\binom{n}{k}=\binom{n}{n-k}.

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

Размер слоя можно получить и последовательно. Начинаем с одной исходной вершины. Следующий слой состоит из наборов, отличающихся одной координатой, и содержит столько элементов, сколько есть координат. Чтобы перейти к слою с двумя отличиями, выбираем уже не порядок шагов, а пару позиций: поэтому пути, меняющие одну и ту же пару в разном порядке, ведут в одну вершину. Если считать пути вместо конечных вершин, получится другой ответ.

Булева функция как разметка куба

Булева функция от nn переменных сопоставляет каждой вершине значение 00 или 11. Например, функция x1∧x2x_1\land x_2 на квадрате равна единице только в вершине 1111. Это та же информация, что и в таблице истинности, но рёбра дополнительно показывают, какие входы отличаются одним битом. Сами операции разобраны в статье про логические элементы И, ИЛИ, НЕ.

Разметка помогает заметить, где переключение одной переменной меняет результат. Для конъюнкции переход от 1010 к 1111 меняет значение с нуля на единицу, а от 0000 к 0101 оставляет его нулевым. Вершины со значением единица можно перечислить и построить по ним совершенную дизъюнктивную нормальную форму. Сам куб при этом описывает пространство входов; функция - лишь выбранная разметка его вершин.

Зачем это нужно в информатике

В теории кодирования двоичные слова удобно представлять вершинами, а число искажённых битов - расстоянием между ними. Чем больше минимальное расстояние между допустимыми словами кода, тем больше ошибок можно обнаружить или исправить при подходящем декодировании. Например, код из слов 000000 и 111111 имеет минимальное расстояние три: если передан 000000, а получен 010010, ближайшее кодовое слово - 000000. Более сложный пример конструкции рассмотрен в статье про код Рида–Маллера.

Куб также описывает пространство конфигураций из nn независимых двоичных решений: включён или выключен флаг, выбран или не выбран элемент. Каждая вершина соответствует подмножеству множества из nn элементов, а переход по ребру добавляет либо удаляет один элемент. Такой взгляд полезен при переборе подмножеств и связан с подсчётом пересечений в принципе включения-исключения.

Однако сам рисунок не решает задачу автоматически. В большом кубе трудно перечислить даже вершины: при n=8n=8 их 256, а при n=20n=20 - уже 1 048 576. Поэтому алгоритм обычно использует свойства задачи, а не строит всю картинку. Куб здесь служит точной моделью соседства и расстояния.

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

Частые ошибки

  • Соединять любые разные наборы. Ребро есть только при различии ровно в одной позиции; для 0000 и 1111 расстояние равно двум.
  • Путать размерность и число вершин. Размерность - число битов nn, а число наборов - 2n2^n.
  • Считать каждое ребро дважды. Сумма степеней равна 2∣E∣2|E|, поэтому при подсчёте по соседям нужно делить на два.
  • Считать пересечение линий вершиной. На плоской проекции графа пересекающиеся рёбра не обязательно имеют общий конец.
  • Принимать разметку функции за сам куб. Одна и та же структура вершин и рёбер подходит для множества разных функций.

FAQ

Почему куб называют булевым?
Его координаты принимают два значения, обычно 00 и 11, как переменные булевой логики. Само название не требует, чтобы вершинам уже была сопоставлена конкретная функция.

Сколько соседей у вершины в QnQ_n?
Ровно nn: каждый сосед получается переключением одной выбранной координаты. При n=0n=0 соседей нет.

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

Коротко

Булев куб QnQ_n состоит из всех nn-битовых наборов; соседние вершины отличаются одним битом. У него 2n2^n вершин и n2n−1n2^{n-1} рёбер при n≥1n\geq1. Расстояние по рёбрам равно числу различных координат, а слой на расстоянии kk содержит (nk)\binom{n}{k} вершин. Эти свойства связывают логику, комбинаторику и двоичные коды.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Число булевых функций от n переменных: формула

Число булевых функций от n переменных: формула

Сколько существует булевых функций от n переменных и почему ответ равен 2 в степени 2ⁿ? Вывод по таблице истинности, примеры и задачи с ограничениями.

8 ноября 20269 минут
Частично упорядоченное множество: примеры и диаграмма

Частично упорядоченное множество: примеры и диаграмма

Разбираем частично упорядоченное множество: свойства отношения, сравнимые элементы, диаграмму Хассе и отличие максимального элемента от наибольшего на примерах.

8 ноября 20269 минут
Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

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

8 ноября 20268 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

8 ноября 20268 минут
Исчисление предикатов: язык, формулы и правила вывода

Исчисление предикатов: язык, формулы и правила вывода

Исчисление предикатов описывает свойства объектов и отношения между ними. Разбираем устройство формул, пошаговый пример доказательства и поиск контрмодели.

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях связывает сумму степеней вершин и число рёбер графа. Разбираем доказательство, нечётные степени, петли и типовые задачи на примерах.

8 ноября 20267 минут