Избранные задачи прикладной дискретной геометрии

Московский государственный технический университет
имени Н.Э. Баумана
Д.А. Жуков, П.Г. Ключарев
ИЗБРАННЫЕ ЗАДА
ЧИ
ПРИКЛАДНОЙ ДИСКРЕТНОЙ
ГЕОМЕТРИИ
Рекомендовано Научно-методическим советом
МГТУ им. Н.Э. Баумана
в качестве учебного пособия
Москва
Издательство МГТУ им. Н.Э. Баумана
2012

УДК 519.1(075.8)
ББК 22.176
Ж86
Рецензенты: А.Н. Велигура, А.Ю. Голубков
Ж86
Жуков Д. А.
Избранные задачи прикладной дискретной геометрии : учеб.
пособие / Д. А. Жуков, П. Г. Ключарев. — М.: Изд-во МГТУ
им. Н. Э. Баумана, 2012. — 53, [3] с. : ил.
Рассмотрены алгебраические и комбинаторные свойства различных подмножеств булева куба, нашедшие применение в теории булевых функций, теории сложности, защите информации и теории
кодирования. Приведены задачи с подробными решениями и упражнения различной степени сложности, предназначенные как для первоначального, так и для углубленного освоения методов дискретной
математики и комбинаторного анализа.
Для студентов первого курса, обучающихся специальностям «Компьютерная безопасность» и «Информационная безопасность автоматизированных систем».
Работа выполнена при финансовой поддержке РФФИ (проект
№11-01-00508).
УДК 519.1(075.8)
ББК 22.176
Учебное издание
Жуков Дмитрий Александрович
Ключарев Петр Георгиевич
ИЗБРАННЫЕ ЗАДА
ЧИ ПРИКЛАДНОЙ ДИСКРЕТНОЙ ГЕОМЕТРИИ
Редактор О.М. Королева
Корректор
О.В. Калашникова
Компьютерная верстка В.И. Товстоног
Подписано в печать 05.07.2012. Формат 60×84/16.
Усл. печ. л. 3,26. Тираж 100 экз. Изд. №47.
Заказ
Издательство МГТУ им. Н.Э. Баумана.
Типография МГТУ им. Н.Э. Баумана.
105005, Москва, 2-я Бауманская ул., 5.
c
⃝МГТУ им. Н.Э. Баумана, 2012

ВВЕДЕНИЕ
При изучении дискретной математики и программирования часто приходится сталкиваться с вопросами существования, генерирования и подсчета числа различных комбинаторных объектов.
Одним из наиболее замечательных объектов комбинаторики является многомерный булев куб. Комбинаторные свойства булева куба
находят многочисленные приложения при передаче и защите информации, в дискретной геометрии и теории алгоритмов, в теории
графов и комбинаторном анализе, в теории булевых функций и параллельных вычислениях и с развитием этих дисциплин становятся неотъемлемой частью обязательных университетских курсов.
Авторами пособия сделана попытка, не претендуя на полноту охвата материала, показать связь комбинаторики булева куба с
другими разделами дискретной математики, чтобы облегчить переход студентов к ее углубленному изучению на старших курсах.
На многочисленных примерах разобраны метрические свойства
подмножеств булева куба, рассмотрены код Хемминга и код Грея,
доказана теорема Шпернера. Все примеры в тексте снабжены подробными решениями, а в конце пособия приведено несколько
задач для самостоятельного решения.
Углубленные сведения о предмете можно найти в работах
[1 — 14].
Авторы рассчитывают, что читатель знает элементарные понятия комбинаторики и алгебры в пределах первого семестра, и
рекомендуют обратиться к учебникам [1, 2, 3] в случае затруднений.
В
пособии
использованы
стандартные
обозначения:
N =
= {1, 2, . . . } — множество натуральных чисел; Z = {0, ±1, ±2, . . . }
3

— множество целых чисел; Zm = {0, 1, . . . , m −1} — множество
вычетов по модулю m; R — множество действительных чисел;
Am = A × . . . × A — декартова степень множества A; |A| — его
мощность (число элементов).

1. БУЛЕВ КУБ КАК МЕТРИЧЕСКОЕ ПРОСТРАНСТВО
Множество Zn
2 = {0, 1}n = Z2 × . . . × Z2, состоящее из всех
упорядоченных наборов нулей и единиц длины n, называется булевым кубом размерности n. Его элементы — двоичные наборы —
будем обозначать греческими буквами: ˜
α, ˜
β, ˜
γ, . . . В качестве примера приведем список всех двоичных наборов длины три:
Z3
2 = {000, 001, 010, 011, 100, 101, 110, 111}.
Наборы в этом списке идут в так называемом лексикографическом порядке, т. е. в порядке следования всех трехбуквенных слов
в словаре слов двухбуквенного алфавита (0 — первая буква этого
алфавита, 1 — вторая). Очевидно, что |Zn
2| = 2n при всех n ∈N.
Пусть X — произвольное множество и ρ : X × X 7→R — некоторая функция, определенная на упорядоченных парах элементов
множества X и принимающая действительные значения. Функция ρ называется метрикой, или расстоянием, на множестве X,
если она удовлетворяет трем свойствам, которые называются аксиомами метрики:
1) симметричность: ∀x, y ∈X ρ(x, y) = ρ(y, x);
2) неотрицательность: ∀x, y ∈X ρ(x, y) ≥0, причем ρ(x, y) =
= 0 ⇔x = y;
3) неравенство треугольника: ∀x, y, z ∈X ρ(x, z) ≤ρ(x, y) +
+ ρ(y, z).
Пара (X, ρ) называется в этом случае метрическим пространством. Элементы множества X принято называть точками соответствующего пространства. Аксиомы метрики являются естественным обобщением свойств обычного евклидова расстояния на
плоскости R2 и в пространстве R3. Поэтому функция ρ и в более
5

общем случае часто называется расстоянием. Аксиома 3 (неравенство треугольника), если говорить неформально, утверждает, что
из точки x до точки z нельзя добраться транзитом через точку y
быстрее, чем напрямую (длина любой стороны треугольника не
превосходит суммы длин двух других сторон). Другими словами,
если точка x близка к точке y, а точка y близка к точке z, то точки
x и z тоже близки.
Пусть ˜
α = (α1, . . . , αn) и ˜
β = (β1, . . . , βn) ∈Zn
2 — произвольные двоичные наборы длины n. Назовем расстоянием между наборами ˜
α и ˜
β число разрядов, которыми они различаются. Обозначим
это расстояние d(˜
α, ˜
β):
d(˜
α, ˜
β) =
{i : αi ̸= βi}
.
(1)
Например, расстояние между наборами ˜
α = 01011 и ˜
β = 10010
равно 3, что можно записать в виде d(01011, 10010) = 3, так как
у наборов 01011 и 10010 не совпадают первый, второй и пятый
разряды. Нетрудно убедиться1, что
d(˜
α, ˜
β) =
i=1
|αi −βi|.
(2)
n
X
Равенство (2) можно принять за второе эквивалентное определение расстояния между наборами. Таким образом, нами получена
функция d : Zn
2 × Zn
2 7→Z, определенная на всех парах двоичных
наборов одинаковой длины и принимающая целые неотрицательные значения. Функция d называется метрикой Хемминга, или
расстоянием Хемминга. Далее везде в тексте за ней сохранено
обозначение d. Покажем, что функция d действительно является
метрикой.
Задача 1. Доказать, что функция d(˜
α, ˜
β) — метрика на булевом
кубе Zn
2.
Доказательство. Необходимо проверить выполнение всех трех
аксиом метрики. Очевидно, что свойства симметричности и неотрицательности функции d следуют из формулы (1). Для доказательства неравенства треугольника используем равенство (2).
1 Действительно, величина |αi −βi| равна нулю, когда разряды αi и βi
совпадают, и равна единице, когда αi ̸= βi, в силу того, что αi, βi ∈Z2.
6