Н. П. РЕДЬКИН
ДИСКРЕТНАЯ
МАТЕ М АТИ КА
КУРС ЛЕКЦИЙ
ДЛЯ СТУДЕНТОВ-МЕХАНИКОВ
УЧЕБНОЕ ПОСОБИЕ
Допущено Министерством образования
Российской Федерации
в качестве учебного пособия
для студентов высших учебных заведений,
обучающихся по специальностям
•Математика», •Прикладная математика»
ь
Санкт-Петербург • Москва • Краснодар
2003
БЫ< 22.18
РЗЗ
Редькин II. П.
Р 33 Дискретная матемагика: Курс лекций для студентов-механи-
ков. — СПб.: Издательство «Лань», 2003. — 96 с., ил. — (Учебники
для вузов, специальная литерагура).
ISBN 5-8114-0522-7
Учебное пособие содержит основной магериал обязательного курса
«Дискретная математика», включающего 34 часа лекций и столько же прак-
тических занятий и читающеюся на отделении механики механико-мате-
матического факультета МГУ с 1998 г. В нем в сжатой форме представле-
ны для первоначального ознакомления несколько важных разделов диск-
ретной математики: комбинаторный анализ; графы и сети; важнейшие
классы управляющих систем — формулы алгебры логики, схемы из функ-
циональных элементов, конечные автоматы; кодирование; примеры дис-
кретных экстремальных задач и способов их решения. К каждой главе
прилагаются задачи, самостоятельное решение которых, несомненно, бу-
дет способствовать более глубокому усвоению теоретического материала
и лучшей подготовке к экзамену.
Для студентов и аспирантов.
ББК 22,18
Обложка:
С. Л. Шапиро, А. Ю. Лапшин
Гигиенический сертификат 78.01.07.953.П.001665.03.02
от 18.03.02, выдан ЦГСЭН в СПб.
Издательство «ЛАНЬ»
lan@lpbl.spb.ru www.lanpbl.spb.ru
193012, Санкт-Петербург, пр. Обуховской обороны,277,
издательство: тел./факс: (812) 262-24-95, тел.: (812) 262-11-78;
pbl@lpbl.spb.ru, print@lpbl.spb.ru
торговый отдел: 193029, ул. Крупской, 13, тел./факс: (812) 567-54-93,
тел.: (812) 567-85-78, (812) 567-14-45, 567-85-82, 567-85-91; trade@lanpbl.spb.ru;
Филиал в Москве:
109263, Москва, 7-я ул. Текстильщиков, 5,
тел.: (095) 787-59-47, 787-59-48; lanmsk@gpress.ru
Филиал в Краснодаре:
350072, Краснодар, ул. Жлобы, 1/1, тел.: (8612) 74-10-35.
Подписано в печать 20.10.03.
Бумага газетная. Формат 60X90 ‘/|6.
Гарнитура Школьная. Печать офсетная. Усл. псч. л. 6.
Тираж 3000 экз. Заказ № 1061.
Отпечатано с готовых диапозитивов
в ФГУП «Печатный двор»
Министерства РФ по делам печати, телерадиовещания
и средств массовых коммуникаций.
197110, Санкт-Петербург, Чкаловский пр., 15.
Охраняется законом РФ об авторском праве.
Воспроизведение всей книги или любой ее час г и
запрещается без письменного разрешения изцягсля.
Любые попытки нарушения закона
будут преследоваться в судебном порядке.
Издательство «Лань», 2003
(О Н. И. Редькин, 2003
'О Издагельсгво «Лань»,
художественное оформление, 2003
ОГЛАВЛЕНИЕ
Глава I. Элементы комбинаторики.......................  5
§ 1.	Комбинаторные объекты и комбинаторные числа........5
§ 2.	Формула включения-исключения.
Производящие функции и возвратные последовательности... 7
Глава II. Графы и сети..............................   13
§ 1.	Элементы графа. Подграфы. Способы задания графов.. 13
§ 2.	Геометрическая реализация графов. Верхняя оценка числа
неизоморфных графов с т рёбрами....................... 16
§ 3.	Деревья. Характеристические свойства деревьев.... 17
§ 4.	Верхняя оценка числа неизоморфных
корневых деревьев с т рёбрами......................... 19
§ 5.	Теорема Кэли о числе деревьев
с занумерованными вершинами............................20
§ 6.	Двудольные графы. Паросочетания и трансверсали.
Критерий существования трансверсали (теорема Холла).... 22
§ 7.	Сети. Потоки в сетях. Теорема Форда и Флакерсона о
максимальной величине потока в сети....................24
Глава III. Булевы функции и формулы....................30
§ 1.	Булевы функции. Табличное задание булевых функций.
Существенные и фиктивные переменные булевых функций.
Элементарные булевы функции......................  30
§ 2.	Формулы и функции, реализуемые формулами.
Простейшие эквивалентности.............................32
§ 3.	Разложение булевых функций по переменным.
Дизъюнктивные нормальные формы.........................34
§ 4.	Полнота систем булевых функций. Примеры полных систем.
Представление булевых функций полиномами Жегалкина... 36
§ 5. Функции Л-значной лш ики..........................37
Глава (V. Схемы из функциональных элементов.
Синтез и оценки сложности схем.....................39
§ 1.	Схемы и« функциональных элементов в базисе {&, V, . 39
§ 2.	Синтез схем с использованием д.н.ф................41
§ 3.	Метод Шеннона...................................  43
§ 4.	Асимптотически оптимальный метод синтеза схем
(метод Лупанова).......................................45
§ 5.	Мошностной метод получения нижней оценки
для сложности схем.....................................47
Глава V. Ограниченно-детерминированные функции
и реализация их автоматами..........................50
§ 1.	Детерминированные и ограниченно-детерминированные
функции............................................... 50
§ 2.	Способы задания о.-д. функций.....................54
§ 3.	Схемы автоматов из функциональных элементов
и элементов задержки...................................56
Глава VI. Кодирование .................................57
§ 1.	Алфавитное кодирование............................57
§ 2.	Неравенство Крафта-Макмиллана.....................60
§ 3.	Коды с минимальной избыточностью. Оптимальное
кодирование Хаффмена...................................62
§ 4.	Самокорректирующиеся коды. Коды Хэмминга..........67
§ 5.	Геометрические свойства кодов Хэмминга. Оценки числа
кодовых слов в коде, исправляющем р ошибок.............69
Глава VII. Дискретные экстремальные задачи.............72
§ 1.	Задача на покрытие. Точное решение задачи на покрытие ... 72
§ 2. Градиентный алгоритм поиска приближённого решения
задачи на покрытие. Оценка сложности градиентного
покрытия. Отклонение градиентного покрытия от
минимального......................................73
§ 3.	Задача о минимальном остовном	дереве..........77
§ 4.	Поиск кратчайшего и	надёжного	путей в графе......78
Задачи................................................82
Список литературы.....................................96
Глава I
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
§ 1. Комбинаторные объекты и комбинаторные числа
В комбинаторном анализе изучаются различные объекты, порож-
даемые элементами из конечного множества А = {аи...,ап}, и чис-
ловые характеристики этих объектов. Часто рассматриваются, на-
пример, упорядоченные или неупорядоченные подмножества множе-
ства А, подмножества с повторяющимися элементами из множест-
ва А и т. д. Вместе с классами таких комбинаторных объектов есте-
ственным образом вводятся и так называемые комбинаторные числа,
задающие число объектов в том или ином классе и зависящие от
некоторых параметров, например, от мощности исходного множест-
ва А и мощности рассматриваемых подмножеств множества А.
Размещения элементов. Пусть А = {ап..ап}. Размещением
элементов из А по к (или размещением из п элементов по к) назы-
вается упорядоченное подмножество из к элементов множества А.
Для А = {aj, 02, Оз, а4} размещениями из А по 3 будут, например,
{а^аз,^}, {а^а^а,},
Обозначим число размещений из п элементов по к через (n)fc.
При построении конкретного размещения первым элементом в нём
можно взять любой из п элементов множества А, вторым элемен-
том — любой из п — 1 оставшихся в А элементов и т. д. Поэтому
(n)fc = п(п — l)...(n — fc + 1) при 1 к п.
При к > п не существует размещений из п по к, следовательно,
(n)k = 0 при к > п; при к = 0 полагаем (О)о = (n)0 = 1. Нетрудно
заметить, что для чисел (п)к выполняются тождества
(п)й=п(п-1)*_1,
(«)* =00*-| (n-fc + 1).
Перестановки элементов. Перестановками элементов мно-
жества А = ап} (или перестановками из п элементов) на-
зываются всевозможные упорядоченные множества из п элементов
Для А ={а1,а2,а3} перестановками будут, например, {^,03,
Перестановки из п элементов — частный случай размещений
из п элементов по п. Поэтому
(п)п = п(п — 1)... 2 • 1 “ п\
Как обычно, полагаем 0! - 1.
5
Сочетания элементов. Сочетанием элементов из А = {ар...
.,.,ап} по к (или сочетанием из п элементов по к) называется
неупорядоченное подмножество из к элементов множества А.
Для А =	всевозможными сочетаниями по 2 элемента
будут	{«1,^}, {°2, °з}-
В сочетании, в отличие от размещения, порядок следования эле-
ментов не учитывается. Поэтому из одного сочетания (из п элемен-
тов по к) получается к! размещений. Отсюда для числа (£) сочета-
ний из п элементов по к получается формула
( п \ __ (п)к _ п(п — 1)... (п — & 4-1) „ п\
к\ “	к\	~ к\(п-к)[
(0^ к п; вместо (£) часто используется также обозначение С*).
Из последней формулы следует
(S)=(;)=o->" <;)=(-»)
Для случая к > п обычно полагают (£) =0, поскольку при к > п
не существует сочетаний из п элементов по к.
Числа (£) фигурируют в функциональном тождестве, называе-
мом формулой для бинома Ньютона:
(i+®r=(S) + (?)x+.-+(*)^+...+C)®“- а)
В правой части данного тождества коэффициент при хк получает-
ся всевозможными выборами из к скобок (1 4- х) переменной х,
а из остальных скобок 1, что даёт ровно (£) слагаемых.
Полагая в (1)	1, получим тождество
(S) + (?) + - + (D + - + C)=2";	(2)
при х = -1 получим
(S)-(?) + - + (-ir(£)=o.	(3)
Из соотношений (2) и (3) следуют тождества
при чётном п и
при нечётном п.
Сочетания с повторениями элементов. Сочетанием с по-
вторениями элементов из А ~ {ап...,ап} по к (или сочетанием
с повторениями из п элементов по к) называется неупорядочен-
ный набор из k элементов, в котором элементы могут повторяться и
каждый элемент сочетания встречается в А.
Для А = {aj, «2» °h} всевозможными сочетаниями с повторениями
по 2 элемента будут	(аз»аз)-
Обозначим через Н* число сочетаний с повторениями из п эле-
ментов по к\ найдём это число.
Пусть а — произвольное сочетание с повторениями элементов
из А = {аи...,ап} по к. Этому сочетанию поставим в соответствие
набор а (а) длины п 4- к - 1 из п - 1 нулей и к единиц. В наборе
а(а) число единиц, находящихся между (г ~ 1)-м и г-м нулями, равно
числу элементов а4, входящих в сочетание а (г =2,...,п — 1), а чи-
сло единиц, стоящих перед первым нулём (после последнего нуля),
равно числу элементов а, (соответственно элементов ап), входящих
в сочетание а. Указанное соответствие между сочетаниями а и набо-
рами а (а) взаимно однозначно. Наборов длины п+к-1, содержащих
п - 1 нулей и к единиц, имеется ровно ( п + ~ 1) ШТУК» посколь-
ку каждому такому набору можно взаимно однозначно сопоставить
сочетание из п 4- к — 1 элементов по А?. В итоге получаем
§ 2. Формула включения-исключения. Производящие
ФУНКЦИИ И ВОЗВРАТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ
Рассмотрим — главным образом с иллюстративной целью —
несколько способов подсчёта комбинаторных чисел.
Формула включения-исключения. Пусть имеется т пред-
метов и п различных свойств, которыми могут обладать эти предме-
ты. Пусть	—число предметов, обладающих
свойствами. В таком случае число предметов, не обладающих ни
одним из свойств, определяется по следующей формуле включения-
исключения:
тЪ = т-'£)т(г) + 52 МА > Ъ) ~ • • •+
1 = 1	1 <	< П
+(-!)' 52	->А) + - +	2,(1)
Формулу (1) можно получить, например, индукцией по п.
При n = 1 имеем	т. е. формула (1), очевидно, справед-
лива. Предположим, что формула (1) справедлива для п - 1 свойств.
Пусть	— число предметов, не обладающих ни одним
из свойств	По предположению индукции имеем
п - 1
“ т(1 ,...,п — 1)~ т - ^т(г)+
* --1
4-	m(i1,i2)-... + (-l)n"1m(l,2,...,n~ 1).	(2)
1 < tj < I, < п -1
7
Эта формула справедлива и для отдельно взятой совокупности пред-
метов, обладающих n-м свойством, т. е.
п, — 1
— 1,п) = т(п) —	п)+
t-i
4-	— ... 4- (—1)” "^/1(1,2,...,п — 1,п), (3)
где тп(1,...,п - 1,п)—число предметов, обладающих свойством п,
но не обладающих ни одним из свойств - 1. Как нетрудно
заметить,
m(l,...,n — l,n) — m(l,...,n — 1) — m(l,...,n — 1,п).
Отсюда следует, что формула (1) получается вычитанием форму-
лы (3) из (2).
Замечание. Формулу включения-исключения можно проин-
терпретировать ещё и таким образом. Множество всех т предметов
обозначим через А, а через Аг обозначим подмножество всех тех
предметов, каждый из которых обладает i-м свойством (г =
понятно, что подмножества AH...,An могут быть совершенно про-
извольными). В этом случае формула включения-исключения запи-
шется так:
|А\(Л1и...иАп)| = И1-1>«1+ Е
* - 1	1 <	< п
+(-1)'	52 IA, Пп... n A.J +... + (- 1)П|Л П...П Ап|.
1 < »1 <	< I, < п
Производящие функции. Часто используются при нахожде-
нии комбинаторных чисел и при установлении комбинаторных тож-
деств.
Пусть имеется последовательность	Этой после-
довательности сопоставим ряд
оо
Ем*
*•=0
(для конечной последовательности {а^}, т. е. при 0 k < п, указан-
ный ряд превращается в многочлен). В ряде случаев, например, при
определённых ограничениях данный ряд может оказаться сходящим-
ся и задавать некоторую функцию A(t):
оо
л(*)=Ем*-
*=0
8
Эта функция A(t) называется производящей для последовательно-
сти {аЛ}. Если производящая функция A(t) известна и допускает
разложение в ряд Маклорена, причём единственным образом, то
этим обстоятельством можно воспользоваться для нахождения ком-
бинаторных чисел
Проиллюстрируем сказанное на следующем простом примере.
Предположим, что нужно найти (£). Нетрудно заметить, что из пра-
вил возведения в степень и определения числа сочетаний из п эле-
ментов по k следует равенство
(1 +t)"-! +	Г;
правую часть данного равенства формально можно рассматривать как
некоторый ряд, а выражение в левой части равенства — как произ-
водящую функцию для данного ряда. Легко заметить, что функция
(1 -Ь t)” допускает разложение в ряд Маклорена, причём единствен-
ным образом:
(1 + О"=1 + ^е4- w^p^t2 + ...+
. n(n-l)-... (n-A? + l)	n(n- !)• .-2 1 fn
-1-	jfe!	С	с .
В силу единственности разложения коэффициенты при tk в обоих
полученных выражениях для (1 4- t)n должны быть равны, т. е.
/ п \ _ п-(п — !)-... (п — fe-1-l)
U/ ~	Л!
Второй пример. С помощью производящих функций установим
тождество
(2„”) = ±С)’-
*=0
Для этого возьмём тождество
(1 ч- е)2гг -- (1 + t)"(i м)"
и разложим функции (1 4- t)2n и (1 4- t)n в левой и в правой частях
этого тождества в ряды:
2п	/ п	\ / п	\
Е(’> Е0'‘ ЕС)'- 
!-=1	\А,=0 / \z7i-0	/
Сравнивая коэффициенты при tn в левой и в правой частях послед-
него тождества, получаем
9
(г;)=t (i) (»-"*)=±«)'-
Л-0	Л=0
Возвратные последовательности. При решении многих за-
дач (и не только комбинаторного характера) возникают рекуррент-
ные соотношения. Рассмотрим те из них, которые приводят к так
называемым возвратным последовательностям.
Последовательность ао,ап...,ап,... называется возвратной по-
следовательностью степени к, если для некоторого к и всех п
выполняется соотношение
а„+4	+••• + ₽* а„ = 0,
(4)
где коэффициенты рг (г = не зависят от п. Многочлен
Р(х)~хк +Р1Хк~' + ... + рк	(5)
называется характеристическим для возвратной последовательно-
сти (4). Сформулируем и докажем несколько утверждений, в сово-
купности позволяющих находить решения рекуррентных соотноше-
ний вида (4).
Утверждение 1. Возвратная последовательность сте-
пени к полностью определяется заданием её первых к членов и
соотношением (4).
Доказательство легко получается индукцией по п. Пер-
вые к членов известны по условию. Далее согласно (4) каждый по-
следующий член последовательности однозначно находится по к пре-
дыдущим:
Утверждение 2. Если А является корнем характери-
стического многочлена, то последовательность {Ап} удовлетво-
ряет соотношению (4).
Доказательство. Требуется доказать, что Аа+* 4-
4-p1An + fc“14-...4-р^Ап = 0, или, что то же самое An(Ak4“PlAfc~14-...
...4-рЛ) = 0. По условию А является корнем многочлена (5) и выра-
жение в скобках обращается в 0.
Утверждение 3. Если АAfe — простые корни харак-
теристического многочлена (5), то общее решение рекуррентно-
го соотношения (4) представимо в виде
где cn...,cfc — произвольные константы.
Доказательство. Заметим, что если последовательно-
сти {ап} и {Ьп} удовлетворяют соотношению (4), то тогда и последо-
вательность {dn}, где d„ - ап 4- удовлетворяет соотношению (4).
Отсюда и из предыдущего утверждения следует, что ап ~ qAf 4- ...
...4-ckXk удовлетворяет соотношению (4).
f()
Убедимся теперь, что любая последовательность {ап}, удовлет-
воряющая (4), может быть представлена в виде ап ~-elA1n-H..4-cfcA£,
где	— подходящие константы. Согласно утверждению 1 лю-
бую последовательность {ап}, удовлетворяющую соотношению (4),
можно указать первыми к членами Oq, Oj ,..ак Р Но в таком случае
остаётся лишь показать, что для любых	_i существуют
си..пск такие, что
С1 +	+ • • • + Ск — °о»
С] Aj 4~ С2А2 4-... + сА АЛ = й|,
цА* 1 4-CgAj 1 4-... 4-cfcA£ 1==afc_|.
Определитель системы уравнений (6) является определителем Ван-
дермонда. Известно, что он равен П (А{ ~ А ) и не обращается
в нуль, если At / Ау при г / j. Следовательно система (6) имеет
решение и притом единственное. Утверждение доказано полностью.
Утверждение 4. Если Aj,...,Ав — корни характеристи-
ческого многочлена (5) кратности соответственно, то
общее решение рекуррентного соотношения (4) имеет вид
я
а» = Eta' + <\2n + --- + ci,r< п'‘" ')А.">
* = 1
где cid (г = 1,..., a; j == 1,..., rt) —• произвольные константы.
Доказательство. Убедимся, что всякая последователь-
ность указанного в утверждении вида удовлетворяет (4). Для этого
покажем, что если ап == nwArts где А -—корень кратности г многоч-
лена (5), а г > т, то последовательность {ап} удовлетворяет (4).
Обозначим через Л (А) выражение в левой части (4). Подставляя
= lmXl (I = п,...,п4- k) в Л (А) и полагая 1, получим
Л(А) = (п4-Л:)тАп + *+р1(п +-А: - ipA^*"1 4 ...
... + pknmXn —Хп (	+	=
\j=0	/
(km	\
j=Q	i=0	/
(m	k	\
4=0	J=-0	/
(m	\
£(”l)n-^(A) ,
i -=0	/
k
где Р{(х)~т^р.(к - jyxk~J; отметим, что PQ(x) есть харя^теристи-
7-0
//
ческий многочлен Р(х). По условию Л — корень кратности г мно-
гочлена PQ и потому PQ(x) можно представить в виде
^(r) = (a;- A)rQ0(z),
где Qo — некоторый многочлен. Очевидно,
при 0 < i < г. Из последних двух соотношений получаем
Р<(х) = (х- A)r“‘Q4.(x),
где Qt — какой-то многочлен, и Р{(Х) обращается в нуль при всех i <
< г. Значит, А(А) = 0, т. е. соотношение (4) для рассматриваемой
последовательности {ап} выполняется.
С другой стороны, докажем, что если At — корень кратности
rt (г = 1многочлена (5), то любая последовательность {ап},
удовлетворяющая (4), может быть задана в виде, указанном в утвер-
ждении. Без ограничения общности будем считать, что рк / 0, т. е.
что корни характеристического многочлена отличны от нуля (если
рк = 0, то соотношение (4) можно упростить). Для доказательства
достаточно показать (как и в соответствующем месте доказательст-
ва предыдущего утверждения), что для любых ,..., ак _j система
(с1,1 + с1,2 •+•••+	4-... 4 (с,! 4- cg2 4- ... 4-<\г )А, = а15
(7)
К. + с1Л(к - 1) + ... + с11Г1(Л -	+ ...
-	+ С"2(к - l)+... + cJir(fc - 1)г'"!)А,*-‘
имеет единственное решение (относительно неизвестных с^). Для
этого, в свою очередь, достаточно показать, что определитель си-
стемы (7) не равен нулю, или что векторы Ао,An...,AJb„l, где At =
= (A?,iA' ...,ir«"1A;,...,A‘,iA*,...,r--1AO(i==O,l,...,fc--l), линей-
но независимы.
Предположим противное, т. е. предположим, что существуют
константы	bj,..., bk _ !, не все равные нулю, такие, что А = Ао4-...
к -1
...4- Ьк _1Аа_1 =0. Пусть Q(x)^^^bixi и Д — оператор такой, что
1=0
Д/(х) = как обычно, считаем Д*/ = Д(ДА"1/). В таком случае
А-(б?(А1)7Д(?(А1),...,Д1^(А1)>...
Отметим, что Q(A) = Дф(А) = ... = ДГ-1<Э(А) — 0 в том и только
в том случае, когда А является корнем кратности не меньше чем г
12
многочлена Q(x)> Следовательно, А = 0 означает, что Aj является
корнем кратности не меньше чем А2 является корнем кратности
не меньше чем г2 и т, д., наконец, Аа является корнем кратности не
меньше чем тз многочлена Q(x). Но ^4- т2 + ...4- т3~ k, a Q (х) явля-
ется многочленом степени меньше чем к и потому не может иметь к
корней. Полученное противоречие исключает наше предположение.
Значит, система (7) имеет и притом единственное решение. Утверж-
дение доказано.
Глава II
ГРАФЫ И СЕТИ
§ 1.	Элементы графа. Подграфы. Способы задания графов
Множество V ~ , v2,...} вместе с набором Е = (^, ...) пар
элементов из V называется графом G (через ег обозначаем г-ю па-
ру vfc(i)) в Е); элементы множества V называются вершинами
графа G, а пары набора Е — рёбрами графа G. В наборе Е допуска-
ются пары вида (ч,ч) и одинаковые пары. Ребро (vov.) соединяет
вершины г/, и vj9 которые инцидентны данному ребру. Граф G —
конечный, если множество V и набор Е конечны, и бесконечный в
противном случае.
Если (ц, Vj) — упорядоченная пара вершин (т. е.	и
/ (%->ч)), то Ребро (vo Vj) считается ориентированным реб-
ром или дугой, исходящей из вершины vi и входящей в вершину vf,
vi называется началом, a — концом дуги (v4.,Vy). Если (vovy) —
неупорядоченная пара, то ребро (vov.) считается неориентирован-
ным; вершины являются концами неориентированного ребра
Вершина графа, не инцидентная ни одному ребру, называется
изолированной.
Вершина, инцидентная ровно одному ребру, и само это ребро
называются концевыми (или висячими).
Ребро с совпадающими концами называется петлёй.
Две вершины, инцидентные одному и тому же ребру, называются
соседними (или смежными).
Два ребра, инцидентные одной и той же вершине, называются
смежными.
Одинаковые пары вида (ir, Vj) в наборе Е графа G задают крат-
ные или параллельные рёбра.
Весьма часто требуется уточнить, какие графы считаются раз-
личными, а какие не различаются. Это уточнение обычно связывает-
ся с понятием изоморфизма графов. Два графа называются изоморф-
ными, если существуют взаимно однозначное соответствие между их
вершинами и взаимно однозначное соответствие между их рёбрами
13
такие, что соответствующие рёбра соединяют соответствующие вер-
шины.
Граф G{ (VJ у Е{) называется подграфом графа G ~ (V1 E)t если
^СГи^СЕ’.
Некоторые разновидности графов (и подграфов) встречаются
очень часто и носят специальные названия. Укажем некоторые
из них.
Последовательность вершин и рёбер графа G - (У,Е) вида
...(1)
где все ц € V и все (^ , ^ ) G £7, называется путём из вершины
v^ в вершину vi. Вершина v^ называется началом, з vi — концом
пути; число п называется длиной пути.
В общем случае среди вершин и рёбер последовательности (1)
могут быть повторения. Каждое ребро пути может быть ориентиро-
ванным (обязательно из v^ в v^ или, как ещё говорят, от ц к vt- )
или неориентированным. Будем говорить, что путь (1) проходит че-
рез вершины	Vi по рёбрам (t^, v^), (v^, v^),...,(v. , v. ).
Цепь — это путь без повторяющихся рёбер. Цепь без повторяю-
щихся вершин называется простой цепью.
Если в последовательности (1) v^ == v^(n >0), то такой путь счи-
тается замкнутым. Замкнутый путь без повторяющихся рёбер (дуг)
называется циклом. Простой цикл — это цикл без повторяющихся
вершин (не считая последней вершины в записи цикла (1)). Простой
цикл с ориентированными рёбрами будем называть также контуром.
Для графа на рис. 1 имеем: и,, %, v4, в4, ц, eg, v4, %, v3 —
путь из вершины в вершину v3; v4, е4, vlt ep v2, eg, v4, eg, —
цепь; v4, e4, v,, еи v% — простая цепь; v4,	v3, e?, v4, e4, en
eg, v4—цикл; v4, %, v3, e7t v4 — простой цикл.
Существуют различные способы задания графов. Укажем неко-
торые из них.
1)	Указанием множества вершин и списка концов всех рёбер,
в котором для каждого ребра указывается пара (упорядоченная для
ориентированных графов) вершин, являющихся концами этого ребра.
Такое задание, очевидно, отвечает приведённому определению графа.
2)	Перечислением (списком) рёбер графа с указанием их концов
с добавлением списка изолированных вершин.
Н
3)	Матрицей инциденций графа с п вершинами v^...,v кт
рёбрами ,..., ет — прямоугольной матрицей А = || || с п строками
и т столбцами:
г 0, если вершина не инцидентна ребру еу;
1,	если v- является концом дуги
или неориентированного ребра
-1, если Vi является началом дуги
(у неориентированных рёбер
k обоим концам соответствует 4-1).
В каждом столбце матрицы — два ненулевых элемента (если ребро
не петля).
4)	Матрицей соседства вершин — квадратной матрицей В ==
= || ЬJI размера п, в которой равно числу рёбер, идущих из вер-
шины v. в вершину Vj (Ь^ не равно, вообще говоря, однако для
неориентированных графов = &yi).
Матрица инциденций задаёт граф однозначно; матрица соседст-
ва вершин определяет граф с точностью до замены любого неориен-
тированного ребра парой противоположно направленных дуг между
теми же вершинами. Однако для графов без кратных рёбер задание
графа и матрицей соседства однозначно.
На рисунках графы изображаются так. Вершины изображаются
точками (или кружочками), а каждое ребро (дуга) (vo vy) 6 Е —ли-
нией, соединяющей вершины (точки) и Если (vt,vy)— дуга, то
на соответствующей этой дуге линии указывается стрелка от ц к
Приведённый на рис. 1 граф G в соответствии с перечисленными
выше способами можно задать так.
1)	G: V = {4,4» •••>4}; ^ = ((4,4), (4,4), (4,4), (4,4),
<4>Ч>» («4>4)> (4>4>)-
2)	G: £ = ((4,4), (4,4), (4, 4), («4,4), (4,4), (4,4)> (4.4»:
3)	G: матрица инциденций
-1	0	0	1	1	0	0'
1	1	-1	0	0	0	0
л_	0-1 0 0 0 1 -1
л~	0 0 1-1-1-11
0	0	0	0	0	0	0
.0	0	0	0	0	0	0.
4)	G: матрица соседства вершин
'О 1 О О О О’
0	0	0	1	0	0
„„010100
° ~ 2	0	1	0	0	0 •
0	0	0	0	0	0
0	0	0	0	0	0
§ 2. Геометрическая реализация графов. Верхняя
ОЦЕНКА ЧИСЛА НЕИЗОМОРФНЫХ ГРАФОВ С т РЁБРАМИ
Пусть задан граф G = (V,E) с множеством вершин V и множе-
ством рёбер Е. Пусть каждой вершине vi (г = 1,...,п) из V взаим-
но однозначно соответствует точка а, в некотором евклидовом про-
странстве, а каждому ребру e = (vt,vJ.) из Е взаимно однозначно
соответствует непрерывная кривая L, соединяющая точки и и
не проходящая через другие точки ак. Если все кривые, соответству-
ющие рёбрам, не имеют общих точек, кроме, быть может, концевых,
то это множество точек и кривых называется геометрической реа-
лизацией графа G в евклидовом пространстве.
Теорема 1. Каждый конечный граф можно реализовать
в трёхмерном евклидовом пространстве.
Доказательство. Пусть граф G — (V^E) содержит п вер-
шин и т рёбер. Возьмём прямую и проведём через неё т плоскостей.
На прямой выделим п точек ап...,ап и сопоставим их соответст-
венно вершинам графа	Каждому ребру графа G поставим
в соответствие одну из проведённых плоскостей. Пусть е = (vo v-) —
ребро графа G. В плоскости, соответствующей ребру е, соединим
точки и дугой окружности. Выполнив такое построение для
всех рёбер графа G, получим (из точек ао...,ап и дуг окружностей)
геометрическую реализацию графа G. Теорема доказана.
Обозначим через 'у(тп) число попарно неизолированных графов
без изолированных вершин с т рёбрами.
Теорема 2. Для любого натурального т
'у(т) < (ст)т,
где с — некоторая константа.
Доказательство. Очевидно, что число вершин в каждом
из рассматриваемых графов не превосходит 2m. Занумеруем их чис-
лами 1,2,..., 2m. Каждое ребро определяется двумя вершинами (кон-
цами), не обязательно различными, так что для каждого ребра име-
ется не более (2m)2 возможностей выбора концов, а для т рёбер —
не более, чем число сочетаний с повторениями из 4m2 элементов
по т, т. е. не более, чем	Следовательно,
Используя неравенство
т!>(у) ,
получаем
7(т)<^5^^ = (стГ1
где с — 15. Теорема доказана.
16
§ 3. Деревья. Характеристические свойства деревьев
Будем рассматривать неориентированные графы.
Граф G = (VJ2?) называется связным, если для любых двух вер-
шин v, v' € V в G существует путь из v в V.
Две вершины v и v’ графа G связаны, если в G существует
путь из v в v'.
Легко видеть, что отношение между вершинами графа «быть свя-
занными» рефлексивно (и связана с v для любой вершины v G V),
симметрично (если v связана с и1, то и v' связана с v) и транзитивно
(если v связана с v', a v' связана с v", то v связана с v"), т. е. явля-
ется отношением эквивалентности. Вершины графа G разбиваются
на классы эквивалентности V — VJ U V2 и... U Vk, где Т< n Vj = 0 при
i j и любые две связанные вершины v, v’ принадлежат некоторому
одному подмножеству Ц. Обозначим через множество всех тех
рёбер е = (v, г/)» для которых концы v, v' е • Подграф Gi = (Vi, Д) на-
зывается связной компонентой графа G. Например, граф на рис. 2
имеет 3 связных компоненты.
Рис. 2
7
О
Лемма 1. Если G = (V,E) — связный граф, то при добав-
лении к G любого ребра (v, v'), где eV, в полученном графе
будет простой цикл.
Доказательство. Поскольку G — связный граф, то в нём
найдётся путь Р из v в V. Если этот путь не является простой
цепью, то в нём повторяется некоторая вершина vt, т. е. он име-
ет вид Р = уР^^у^у' . В этом случае путь Р сократим, выбросив
из него Р2, и получим путь Р‘ = уР{yiР3у'. Поскольку Р — конечный
путь, то повторяя при необходимости указанную операцию сокраще-
ния, получим простую цепь Z из у в v' (соединяющую у с у'). После
добавления к Z первоначально отсутствовавшего в G ребра (у>у‘)
получим простой цикл. Лемма доказана.
Лемма 2. Граф из п вершин и т рёбер содержит не менее
п - т связных компонент, а если в этом графе нет циклов, то
он содержит ровно п - т связных компонент.
Доказательство. При добавлении к произвольному графу,
содержащему вершины у и у', одного ребра е = (v, v') число связ-
ных компонент может только уменьшиться, но не более чем на 1.
При добавлении тп рёбер число связных компонент в графе может
уменьшиться не более чем на т. Граф G — (V^E) с п вершинами
и т рёбрами получается из графа G' = (VJ0), имеющего п связных
компонент, добавлением т рёбер и согласно вышесказанному в G
будет не менее п — т связных компонент.
17
Предположим теперь, что в G нет циклов. Допустим, что в про-
цессе получения G из G' добавляется ребро (v, v'). Если бы верши-
ны v и V* принадлежали одной связной компоненте, то в G, согласно
лемме 1, появился бы цикл. Следовательно, v и v' принадлежат двум
разным связным компонентам и при добавлении ребра (v, vz) число
связных компонент уменьшается ровно на 1. Это означает, что в G
окажется ровно п - т связных компонент. Лемма доказана.
Следствие. Любой граф Gen вершинами и т рёбрами
при т ^п~ 2 не связен.
Доказательство. Из леммы 2 и условия m < п-2 следует,
что G содержит не менее двух связных компонент.
Граф G = (V,E) называется деревом, если он связный и не со-
держит циклов.
Если G = (V, Е) — связный граф, е € Е и е входит в некоторый
цикл, т. е. е — циклическое ребро, то граф G{, полученный из G уда-
лением ребра е (но с сохранением вершин, инцидентных е) остаётся,
как нетрудно заметить, связным. Удаляя из G в произвольной после-
довательности циклические рёбра, можно получить связный подграф
графа G с множеством вершин V, но без циклов, т. е. дерево; это
дерево называется остовным деревом (или остовом) графа G, Та-
ким образом, всякий связный граф G = (VJ Е) содержит хотя бы один
подграф D’ = (VjEf) с тем же множеством вершин, являющийся де-
ревом.
Теорема 3. Пусть G = (VtE) — граф с п вершинами и т
рёбрами. Тогда следующие 6 условий эквивалентны:
1)	G —дерево;
2)	любые две вершины G связаны ровно одной простой цепью;
3)	G не содержит циклов и т~п - 1;
4)	G —связный граф и т — п- 1;
5)	G —связный граф, но при удалении любого ребра стано-
вится несвязным;
6)	G не содержит циклов, но при добавлении любого нового
ребра с концами из V появляется цикл.
Доказательство. Докажем переходы 1)=>2)=>...=>6)=>
=> 1), откуда будет следовать, что из любого условия вытекает любое
другое, т. е. перечисленные условия представляют характеристиче-
ские свойства дерева.
Переход 1)=>2). Предположим, что данный переход не выполня-
ется, и в дереве G существуют две простые цепи z, и Z2, связываю-
щие v и v'. В этом случае хотя бы одно какое-то ребро е принадлежит
одной из этих цепей, например, Я,, и не принадлежит другой. Пойдём
по Zi в обе стороны от ребра е до первой встречи со второй цепью
в вершинах и vjt т. е. возьмём максимальную (по включению) под-
цепь Z{ первой цепи, содержащую ребро е и не содержащую внутри
себя вершин второй цепи. Подцепь Z' вместе с подцепью Z2 второй
цепи, ведущей из о, в v3 образует цикл. Следовательно, G не есть
дерево. Получаем противоречие. Значит переход 1)=>2) выполняет-
ся.
Переход 2) -> 3). Условие 2) означает, что в G отсутствуют цик-
лы, поскольку концы любого ребра из цикла связаны, по крайней
мере, двумя простыми цепями, одну из которых составляет само реб-
!8
ро (вместе со своими концами), а вторую—дополнение этого ребра
до цикла. Из условия 2) следует также, что граф G представляет со-
бой связную компоненту. Поэтому из леммы 2 получаем т = п - 1.
Переход 3) => 4). Из условия 3) и леммы 2 следует, что число
связных компонент в G равно п - т = 1, т. е. G — связный граф и
т — п — 1.
Переход 4) => 5). Вытекает из следствия к лемме 2.
Переход 5) => 6). Если бы в G был цикл, то при удалении реб-
ра из этого цикла граф G остался бы связным, а это противоречит
условию 5). Значит, G не содержит циклов. Вторая часть условия 6)
вытекает, согласно лемме 1, из того, что G — связный граф.
Переход 6) => 1). Если G не связный граф и вершины v' при-
надлежат разным связным компонентам графа G, то добавление к G
ребра очевидно, не порождает циклов, что противоречит 6).
Значит, G — связный граф, не содержащий циклов (по условию 6),
т. е. G —дерево. Теорема доказана.
Условия 5) и 6) показывают, что множество всех деревьев с п
вершинами — это множество всех минимальных (по числу рёбер)
связных графов и, в то же время, множество всех максимальных
графов без циклов.
§ 4.	Верхняя оценка числа неизоморфных
КОРНЕВЫХ ДЕРЕВЬЕВ С т РЁБРАМИ
Выделим в дереве какую-нибудь одну вершину, которую назо-
вём корнем; полученное дерево с выделенной вершиной называется
деревом с корнем или корневым деревом.
Теорема 4. Число неизоморфных корневых деревьев с т
рёбрами не превосходит 4т,
Доказательство. Будем кодировать корневые деревья сло-
вами (наборами) из нулей и единиц по следующему индуктивному
правилу:
1.	Кодом дерева из одного ребра является слово 01.
2.	а) Если дерево имеет одно корневое ребро (т. е. ребро, ин-
цидентное корню), то его кодом является слово 0А1, где А —код
дерева, получающегося при удалении корневого ребра и объявлении
корнем его второго конца.
2.	б) Если корневых деревьев несколько, скажем, к (см. рис. 3,а),
то можно считать, что дерево получено склеиванием в корне к тц~
деревьев с меньшим числом рёбер (см. рис. 3,6). Если An...,Afc —
коды этих поддеревьев, то слово ... Ал является кодом всего де-
рева.
Очевидно, что код дерева с т рёбрами есть слово длины 2m,
содержащее поровну нулей и единиц, причём в любом начальном
отрезке этого слова нулей не меньше, чем единиц (формально это
можно установить индукцией по m в соответствии с сформулиро-
ванным выше индуктивным правилом построения слов). Например,
кодом дерева, изображённого на рис. 4, является слово 0010110011.
Заметим, что в случае применения правила 2.6) слово Aj яв-
ляется наименьшим непустым начальным отрезком слова А,... Ак,
19
Q
О
содержащим поровну нулей и единиц; то же самое верно для А2
по отношению к слову А2... Ак и т. д. Поэтому по своему коду
дерево восстанавливается однозначно. Таким образом, число неизо-
морфных корневых деревьев с т рёбрами не превосходит числа слов
длины 2 m из нулей и единиц, т. е. 4т, Теорема доказана.
§ 5.	Теорема Кэли о числе деревьев
С ЗАНУМЕРОВАННЫМИ ВЕРШИНАМИ
Будем рассматривать деревья с занумерованными вершинами;
в дереве с п вершинами эти вершины нумеруются числами 1,2,..., п.
Различными будем считать деревья, не переводимые друг в друга изо-
морфизмом, сохраняющим нумерацию вершин. Докажем следующее
утверждение.
Теорема 5 (Кэли). Число деревьев с п занумерованными
вершинами равно пп~2.
Доказательство. Рассмотрим дерево с п вершинами, зану-
мерованными числами 1,2,..., п. Условимся обозначать через г вер-
шину с номером г. В (конечном) дереве существует самая длинная
простая цепь — иначе в нём были бы циклы; начальная и конечная
вершины этой цепи будут концевыми вершинами в дереве. Следова-
тельно, в любом дереве (содержащем хотя бы одно ребро) найдутся
по крайней мере две концевые вершины. Пусть — концевая вер-
шина дерева с наименьшим номером, — единственная вершина,
20
соседняя с Удалим из D вершину и ребро (г\, jj), в результате
получим (см. условие 4) теоремы 3) дерево Dv Пусть г2— конце-
вая вершина с наименьшим номером в Д, а О2,У2)— инцидентное
ей ребро; удалим его, и т. д. до тех пор, пока после удаления реб-
ра (гп_2>Ул-2) не останется дерево Dn_2 из одного ребра. Положим
7 — (А>*2>---> гп-2)» 7 = (yt,	Л-г)- Для дерева, изображённого на
рис. 5, 1 = (3,5,6,1,2,7), .7 = (2,4,1,2,4,4).
Набор 7 = (ij,^,...,^^), а вместе с ним и набор J — (Уи
...,jn_2) определяются по данному дереву D однозначно, причём
в первом наборе все вершины различны, а во втором не обязательно
различны. Убедимся» что любой набор J =	..., jn_2), где 1 jk п
для fc = 1,2,...,п - 2, соответствует некоторому дереву; оно может
быть построено следующим образом.
Пусть ij —наименьшее число из N = {1,2,...,п}, отсутствую-
щее в наборе J (такое число обязательно существует, так как J
содержит п-2 чисел). Соединим ребром вершины и jlt вычерк-
нем число из набора J, число из N и повторим процесс, выби-
рая из N{ --наименьшее число 4» отсутствующее в наборе
«А = 02>7з> •••)./«-г)> соединяя i2 с j2 и вычёркивая j2 из набора Д
и £2 из N1 и т. д. Последними соединяются ребром две вершины,
оставшиеся в TVn_2.
Нетрудно заметить, что для любого А; = 1,2,...,п—2 среди рёбер,
построенных после к-го шага, нет рёбер, инцидентных вершине гА, и
имеется хотя бы одно ребро, инцидентное вершине jk. Учитывая это
и рассматривая процесс построения в обратном порядке, нетрудно
показать индукцией по к, что действительно получается дерево, так
как теперь на каждом шаге присоединяется ребро с новой верши-
ной, т. е. концевое. Аналогичным образом, по индукции, но уже при
рассмотрении процесса построения в прямом направлении доказыва-
ется, что этому дереву соответствует как раз набор J. Получается,
что число деревьев не меньше числа наборов, т. е. не меньше чем
пп~2 (элементом набора J может быть любое число из 7V).
21
Наконец, различным деревьям, очевидно, не может соответство-
вать одна и та же пара наборов (7, J), т. к. по паре (/, J) дерево вос-
станавливается однозначно. Но если Г^Г, то J' / J". Действитель-
но, пусть к — наименьший номер, при котором скажем i'k < ik
(отсюда, в частности, следует, что ik не может быть концевой верши-
ной у дерева (jk,..j”_2) и поэтому ik войдёт в (jk,..в таком
случае ik не входит в набор	но входит в (У7,--ч-'/п-з)-
Поэтому разным деревьям соответствуют разные наборы J; значит,
число деревьев не превосходит числа наборов, равного пЛ"2.
В итоге получаем, что искомое число деревьев равно пп~2. Тео-
рема доказана.
§ 6.	Двудольные графы. Паросочетания и трансверсали.
Критерий существования трансверсали (теорема Холла)
Граф называется двудольным, если существует такое разбие-
ние множества его вершин на два непересекающихся подмножества
(на две доли), что концы каждого ребра принадлежат разным под-
множествам (разным долям; как и при рассмотрении деревьев здесь
мы ограничиваемся неориентированными графами).
Произвольное подмножество попарно несмежных рёбер графа
(взятых вместе со своими вершинами) называется паросочетанием
(или независимым множеством рёбер).
Отметим, что паросочетания могут рассматриваться в произ-
вольных графах (не обязательно двудольных). Но весьма часто па-
росочетания естественным образом возникают и рассматриваются
в двудольных графах. (С построением паросочетаний в двудольном
графе связано много самых разных задач. Типичный пример — задача
о назначении на должности.)
Установим критерий существования паросочетания, покрываю-
щего долю вершин в двудольном графе.
Пусть v — некоторая вершина графа G = (!<£). Через N(v)
обозначим множество вершин графа G, соседних с вершиной v. Для
произвольного подмножества V' вершин графа G положим
Ne(V')= U N(v)\V;
veV
множество iVG(V') назовём окружением подмножества V в гра-
22
Теорема 6. Для существования в двудольном графе
G — (V UW,E) паросочетания, покрывающего долю вершин V,
необходимо и достаточно, чтобы любое подмножество V мно-
жества V удовлетворяло условию
Доказательство. Необходимость. Очевидно, что если
в графе G ~(VuW,E) существует паросочетание, покрывающее V,
то для любого подмножества V' в V число вершин, смежных с вер-
шинами из V', не меньше, чем число вершин в V, т. е. NG(V) | И'|.
Достаточность докажем индукцией по числу вершин в У. Пусть
G(V U W,Е) —двудольный граф с | У| — т > 0, удовлетворяющий
условию теоремы. При т ~ 1 единственная вершина из V инцидент-
на хотя бы одному ребру, которое (вместе со своими концами) и
является нужным паросочетанием. Основание индукции выполнено.
Индуктивный переход. Пусть теорема верна для графов с числом
вершин в доле V равным 1,2,...,к - 1; докажем её для произволь-
ного графа G = (V U W,E), для которого |У| = к, к > 1. Отдельно
рассмотрим два следующих случая.
Случай 1. Для каждого собственного подмножества V' в V
выполняется строгое неравенство | У'| < \NG(У')| (условие теоремы
выполняется «с запасом»). Возьмём в G произвольную вершину v и
ребро е' = (v, w), соединяющее вершину v из V с некоторой верши-
ной w из W. Удалим из G вершины v, w и все рёбра, инцидентные
этим вершинам; в результате получим некоторый двудольный граф
Gj = (^0^,^), у которого V; = V\{v}, W\ = W\{w} и Ех= Е\{е:
е инцидентно хотя бы одной из вершин v,w}, a |V[| = к - 1. Пусть
VJ' — произвольное подмножество множества VJ. Так как для исход-
ного графа G выполняется условие | VJ'| < |TVG(V[')| («с запасом»!),
а из ТУ удалена только одна вершина, то для полученного графа G{
выполняется условие | VJ'I < |7VG(V7)I и по индуктивному предполо-
жению в графе Gx существует паросочетание F, покрывающее
Добавив к Р ребро е', получим нужное паросочетание для исходно-
го графа G.
Случай 2. В множестве V существует такое собственное
подмножество Vo (Vo с V), для которого верно равенство
|v0| = pvo(K)l-	(♦)
Пусть G' и G" — подграфы графа G, порождённые множествами вер-
шин VqUNg(Vq) и (УиТУ)\(^ои2Ус(Т^)) соответственно (если V'—
подмножество вершин графа G, то подграф данного графа, порож-
дённый множеством вершин V', есть подграф графа G, содержащий
в качестве вершин все вершины из У', а в качестве рёбер — все рёб-
ра исходного графа G, концами которых являются вершины из V').
Рассмотрим подграф G'. Для любого подмножества V С VQ име-
ем Ng(V') = Ngi(V') и, следовательно, |У'| |7VG,(y')|. По индук-
тивному предположению в G' существует паросочетание, покрываю-
щее 1^; построим его.
Обратимся к подграфу G". Для любого подмножества V'C V\V0
выполняются соотношения
|Vol + lv'l = lv«U V'l < 1ВДОИ1 = |NC(VO)| + |ATg,(V')I
и верно равенство (*). Следовательно, | V'| \NG„( V')l и по индуктив-
ному предположению в графе G" существует паросочетание, покры-
вающее V \ VQ. Объединяя это паросочетание с построенным выше,
получим паросочетание в графе G, покрывающее V. Теорема дока-
зана.
Пусть А — {а15.ап} конечное непустое множество, a S =
— Sk) — /с-членное семейство его подмножеств (необязатель-
но непересекающихся и необязательно различных). Всякое подмно-
жество Т = {аг ,...,аг } элементов из А называется трансверсалью
(или системой различных представителей) семейства S, если
ai} eSjt 1 О' О. ij ± при j /
Теорема 7 (Холла). Пусть А —- непустое конечное множе-
ство, S = (S{, Sk) — семейство его подмножеств. Для суще-
ствования трансверсали семейства S необходимо и достаточно,
чтобы для каждого у = 1,..., fc объединение S^US^U.. .US- любых j
подмножеств S{ содержало не менее j различных элементов.
Если теперь сравнить теорему (критерий) о существовании па-
росочетания, покрывающего долю вершин в двудольном графе, с тео-
ремой Холла, то нетрудно заметить, что первая является переформу-
лировкой второй на языке графов (элементы множества А образуют
одну долю W вершин графа, подмножества семейства S образуют
другую долю V — покрываемую паросочетанием).
§ 7.	Сети. Потоки в сетях. Теорема Форда и
Фалкерсона о максимальной величине потока в сети
Граф, некоторые вершины которого выделены, называется
сетью. Выделенные вершины называются полюсами сети. Напри-
мер, дерево с корнем можно рассматривать как однополюсную сеть.
Вершины, отличные от полюсов, называются внутренними вер-
шинами сети. Ребро, инцидентное хотя бы одному полюсу, называ-
ется полюсным ребром; остальные рёбра называются внутренними.
Для удобства изложения в этом параграфе введём и будем ис-
пользовать понятие псевдоцепи.
Всякому ориентированному (или частично ориентированному)
графу G = (V,E) поставим в соответствие соотнесённый неориен-
тированный граф G = (V,E), в котором набор Е содержит все те же
пары вершин, что и Е, но все пары в Е неупорядоченные (G по-
лучается из G «стиранием» ориентации всех ориентированных в G
рёбер).
Псевдоцепью (простой псевдоцепью) графа G будем считать
всякую последовательность вершин и рёбер графа G, образующую
путь без повторяющихся рёбер (соответственно без повторяющихся
вершин) в соотнесённом графе G. Например, рёбра е1 и графа,
изображённого на рис. 6, вместе со своими концами образуют псев-
доцепь, связывающую вершины v{ и v3.
Две вершины ориентированного графа G связаны, если они свя-
заны в соотнесённом графе G. В соответствии с таким определением
24
ex	v2	62 v3
О-------------.................О
Рис. 6
связанных вершин (в ориентированном графе G) осуществляется и
разбиение G на компоненты связности.
Ниже будем рассматривать двухполюсные сети без петель и без
изолированных внутренних вершин (кратные рёбра допускаются).
Один из полюсов будем считать входным (или входом), второй —
выходным (или выходом).
Пусть S — произвольная частично ориентированная сеть, каж-
дому ребру е которой приписано неотрицательное число с(е) — про-
пускная способность. Потоком в сети S называется пара (функ-
ций) (/, ш), где — некоторая ориентация всех неориентированных
рёбер сети, а Де) — заданная на множестве всех рёбер функция
с неотрицательными значениями, не превосходящими пропускных
способностей, и такая, что в каждой внутренней вершине v выпол-
няется закон Киргофа, согласно которому сумма значений потока
по рёбрам, исходящим из вершины, равна сумме значений потока
по рёбрам, входящим в вершину. Другими словами, для Де) выпол-
нены условия:
1) 0 < Де) с(е) для всех рёбер сети;
2) R(v) — 0 для всех внутренних вершин, где
й(«)= £ Де>- Е
е е Г(и)	е е Г(«)
а Г(г>) (соответственно Г(г;)) — множество всех рёбер, исходящих
из v (соответственно входящих в v) при ориентации ы.
Пусть as и /38 —входной и выходной полюсы сети S. Посколь-
ку сумма значений R(v) по всем вершинам сети, включая полюсы,
равна нулю (каждое ребро является исходящим для одной вершины
и входящим для другой), то
Значение R =R(as) называется величиной потока. Из таких же
рассуждений следует, что если сеть допускает поток ненулевой ве-
личины, то полюсы сети находятся в одной компоненте связности.
Если сеть изображает какую-либо проводящую систему (сеть дорог,
трубопроводов и т. д.), то R определяет величину потока, входяще-
го в одном полюсе и выходящего из другого, т. е. величину потока,
проходящего через сеть.
Добавим к сети S дополнительное, источниковое ребро, связы-
вающее полюсы и ориентированное от выхода (3S к входу as сети S;
на этом добавленном ребре положим f — R (допуская, что для этого
ребра f может быть меньше нуля). В таком случае закон Киргофа
будет выполняться для всех вершин сети, a R будет определять ве-
личину циркуляции через сеть.
Поставим задачу определения максимальной величины /?тах по-
тока через сеть S при заданных значениях пропускных способностей
рёбер. Ответ может быть получен в терминах сечений сети.
25
Сечением сети называется множество рёбер, при удалении кото-
рого сеть становится несвязной, причём полюсы попадают в разные
компоненты связности. Ясно, что каждая простая псевдоцепь, соеди-
няющая as и (а тем более каждый путь из as в /35), проходит хотя
бы через одно ребро сечения. В сети на рис. 7 примерами сечений
являются {d, е,/}, {6, с, е, д, h}, {d, д, h, г}.
Сечение будем называть простым, если при удалении любого
его ребра оно перестаёт быть сечением. Так {d, е,/} и {Ь,с,е,^, h}
являются простыми сечениями, тогда как {d,#, Д, i} не является та-
ковым. Очевидно, что для каждого ребра простого сечения можно
указать простую псевдоцепь соединяющую as и /3S, которая про-
ходит через это ребро, но не проходит через другие рёбра данного
сечения.
Лемма 3. Если в связной сети удаляется простое сече-
ние, то сеть распадается ровно на две части (несвязные): левую
часть, содержащую as, и правую часть, содержащую /3S.
Доказательство. Действительно, то, что сеть S распа-
дается на несвязные компоненты и что полюса as и /3S окажутся
в разных компонентах связности при удалении рёбер простого се-
чения W — ясно (из определения простого сечения). Убедимся, что
этих компонент будет две — левая и правая.
Пусть v — произвольная вершина. Покажем, что она останется
связанной псевдоцепью либо с as, либо с (3S. Возьмём (в исходной
сети S) псевдоцепь Z, связывающую v с концом v' какого-нибудь
ребра е из простого сечения и не содержащую в качестве внутрен-
них вершин (отличных от концов v и и') концов рёбер из простого
сечения (в силу связности сети указанная псевдоцепь существует).
Поскольку е принадлежит простому сечению, то существует простая
псевдоцепь Z', соединяющая as и /3S и содержащая только данное
ребро е из простого сечения. Отрезок Z" этой цепи, соединяющий
либо v' с as, либо v' с /3S, не содержит рёбер из простого сечения. Но
в таком случае из Z и Z” можно составить, очевидно, псевдоцепь,
связывающую v с одним из полюсов и остающуюся в одной из ком-
понент связности после удаления рёбер простого сечения. Лемма
доказана.
Согласно лемме 3 каждое ребро простого сечения связывает вер-
шины из двух разных частей: левой и правой. Будем называть ребро
сечения прямым, если оно в сети не ориентировано или ориентиро-
вано слева направо, и обратным в противном случае. Будет ли ори-
26
ентированное ребро прямым или обратным, вообще говоря зависит
от выбора сечения. Так, в последнем примере (рис. 7) ребро е в се-
чениях {d, е, f} и {6, с, е, д, h} — обратное, а в сечении {а, с, е, д, г} —
прямое.
Каждому простому сечению W припишем пропускную способ-
ность равную сумме пропускных способностей всех его пря-
мых рёбер. В примере (рис. 7) сечение {d, е,/} имеет пропускную
способность 5|1 — 6, а сечение	Л} имеет пропускную спо-
собность 3+2 + 3 +2=10. Если сеть несвязна и её полюсы находятся
в разных компонентах связности, то естественно считать (единствен-
ным) простым сечением сети пустое множество, а его пропускную
способность нулевой.
Теорема 8 (Форда и Фалкерсона). Максимальная величи-
на потока Rmsx через сеть S равна минимальной из пропускных
способностей cmin её простых сечений.
Доказательство. Докажем сначала, что Rmui < crai0. Для
этого достаточно показать, что для любого потока и любого сече-
ния R < с(1У) (из физических соображений это неравенство доста-
точно очевидно).
Просуммируем R(а) по всем вершинам а левой (относительно
простого сечения W) компоненты сети. Эта сумма, с одной стороны,
равна R — R(as) (с учётом выполнения закона Киргофа для вну-
тренних вершин сети), а с другой стороны она равна алгебраической
сумме величин потоков, идущих через сечение слева направо (пото-
ки по рёбрам, идущим из левой компоненты в правую, суммируются
со знаком плюс, а по рёбрам, идущим в обратном направлении —
со знаком минус; последнее утверждение усматривается легко, ес-
ли учесть, что по каждому ребру из одной его вершины «вытекает»
некоторая часть потока, а в другую его вершину «втекает» точно та-
кая же часть потока). Поскольку /(е) с(е), то отсюда и следует
требуемое неравенство. Ясно также, что равенство R = c(W) может
достигаться только в случае, когда все прямые рёбра сечения ориен-
тированы слева направо (при ориентации о?) и для них /(е) = с(е),
а для всех обратных рёбер /(е) = 0.
Докажем теперь, что в сети S можно создать поток величи-
ны cmln. Доказательство проведём индукцией по числу рёбер в сети S,
Если число рёбер равно нулю, т. е. S состоит из двух изолированных
полюсов, то очевидно, R = стш = 0.
Предположим, что для всякой сети S, содержащей менее т рё-
бер, утверждение уже доказано.
В таком случае имеет место следующее утверждение:
в сети S можно создать поток	, ч
(*)
любой меньшей (чем ст1п) величины.
Действительно, пусть R — произвольное число, удовлетворяю-
щее условию:
0<R<cmin.
Отыскав в сети S простое сечение с пропускной способностью cmin и
снизив её до R (уменьшая цля этого пропускные способности неко-
торых прямых рёбер сечения), мы получим сеть, в которой соглас-
но индуктивному предположению можно создать поток величины R.
Но этот же самый поток будет потоком и в сети S.
27
Используя данное утверждение (*) докажем утверждение для
произвольной сети S с т рёбрами. Простые сечения сети, имею-
щие пропускную способность cmin, будем называть минимальными,
В сети S можно уменьшить пропускные способности некоторых рё-
бер так, что в изменённой сети — назовём её приведённой — будут
выполнены следующие условия:
1) пропускная способность каждого простого сечения не мень-
ше cmin;
2) каждое ребро является прямым в некотором минимальном
сечении или имеет нулевую пропускную способность.
Для получения приведённой сети следует в каком-либо порядке
просматривать все рёбра сети S и уменьшать (быть может, до ну-
ля) пропускные способности тех из них, которые не удовлетворяют
условию 2), но с таким расчётом, чтобы условие 1) не нарушалось.
(Вообще говоря, в зависимости от выбранного порядка могут полу-
чаться различные приведённые сети.)
Очевидно, что любой поток в приведённой сети является пото-
ком и в исходной сети S. Поэтому достаточно установить, что поток
величины cmin можно создать в приведённой сети.
Если приведённая сеть содержит рёбра с нулевой пропускной
способностью, то, удалив их, мы придём к сети, содержащей менее
чем т рёбер и допускающей те же самые потоки. Очевидно (по по-
строению), что в этой сети каждое простое сечение имеет пропуск-
ную способность не меньше cmin. Используя предположение индук-
ции, а при необходимости — и утверждение (*), создадим в полу-
ченной сети поток величины cmin; он же будет потоком и в самой
приведённой сети.
Будем считать теперь, что в приведённой сети нет рёбер с нуле-
вой пропускной способностью, т. е. каждое её ребро является пря-
мым в некотором минимальном сечении (свойство 2)) и, следователь-
но, принадлежит некоторой простой псевдоцепи, соединяющей as
и /З3 (иначе сечение не простое, а тем самым и не минимальное).
Рассмотрим два случая:
а)	каждая простая псевдоцепь, соединяющая as и в приве-
дённой сети, содержит не более двух рёбер;
б)	в приведённой сети имеется простая псевдоцепь, связываю-
щая as и 0S и содержащая не менее трёх рёбер.
Если имеет место случай а), то, очевидно, все рёбра сети полюс-
ные, т. е. каждое ребро инцидентно хотя бы одному полюсу, и либо
не ориентированы, либо ориентированы слева направо (в противном
случае получили бы ребро, которое было бы обратными в любом се-
чении — из-за того, что оно полюсное, — а потому его пропускная
способность была бы уменьшена до нуля в соответствии с услови-
ем 2) и это ребро было бы выброшено при построении приведённой
сети). При этом приведённая сеть представляет собой параллельное
соединение некоторого числа сквозных рёбер, каждое из которых со-
единяет полюсы, и некоторого числа подсетей (по одной на каждую
внутреннюю вершину) весьма простой конструкции: каждая из них
является последовательным соединением двух своих частей, в кото-
рых все рёбра соединены параллельно (см. рис. 8).
Легко видеть, что простыми сечениями этой сети являются такие
и только такие множества, которые содержат все сквозные рёбра, а
28
из каждой подсети либо все рёбра из её левой части и ни одного реб-
ра из правой, либо наоборот. Отсюда уже нетрудно заключить, что
для каждой подсети сумма пропускных способностей рёбер из её ле-
вой части равна сумме пропускных способностей рёбер из её правой
части. (Действительно, если бы какая-нибудь из этих сумм, скажем,
первая была бы меньше, то, взяв минимальное сечение, содержащее
какое-либо ребро из правой части подсети, и заменив в нём все рёбра
из правой части рёбрами из левой части, мы получили бы простое
сечение с пропускной способностью, меньшей cmin, что в силу свойст-
ва 1) невозможно.) Но тогда пропускные способности всех простых
сечений одинаковы и равны cmin. Поэтому в приведённой сети мож-
но создать поток величины cmin — следует только загрузить каждое
ребро вплоть до его пропускной способности.
Если имеет место случай б), то, очевидно, приведённая сеть со-
держит внутреннее ребро (не инцидентное ни одному из полюсов).
Рассмотрим следующее преобразование приведённой сети. Выделим
минимальное сечение, содержащее внутреннее ребро. Заметим, что
ни входная звезда Zas (т. е. подсеть, образованная полюсом as и
инцидентными ему рёбрами), ни выходная звезда не содержат-
ся целиком в этом сечении (поскольку указанные звёзды сами — без
внутреннего ребра — составляют сечения). Каждое ребро ei = (аг, Д.)
этого сечения заменим двумя последовательно соединёнными рёбра-
ми (ао7{) и (7ОД) (все 7i —новые вершины), имеющими ту же
пропускную способность, что и ребро е-. Отождествив теперь все
вершины 7О т. е. склеив их в одну вершину, мы получим сеть, пред-
ставляющую собой последовательное соединение двух сетей Sx и S2.
Это следует из леммы 3, так как согласно этой лемме при удалении
всех рёбер (а., Д) выделенного минимального сечения исходная сеть
распадается на две связные компоненты: левую подсеть 5/, содержа-
щую as, и правую подсеть S2', содержащую /38. Левая подсеть Sj
получается из 5/ добавлением рёбер (ao7f), а правая подсеть S2
получается из S2 добавлением рёбер (7., Д).
Каждая из сетей Sx и S2 содержит менее т рёбер. Например, Sj
не может содержать все рёбра из Zp . Действительно, как сказано
выше, в Zpg входит некоторое ребро е, отсутствующее в выделенном
минимальном сечении. Не может это ребро е входить и в S/, по-
скольку концом его является полюс /3S, принадлежащий S2, Из ана-
логичных рассуждений следует, что и в S2 отсутствует хотя бы одно
ребро из Zas. Всякое простое сечение каждой из подсетей Sx и 52
имеет пропускную способность не меньше cmin (так же, как прообраз
этого сечения в приведённой сети). Поэтому согласно индуктивно-
му предположению в каждой из этих подсетей можно создать поток
величины ст1П.
Поскольку выбранное сечение минимальное, то его пропускная
способность равна cmin, и чтобы получить величину потока стш надо
загрузить все прямые рёбра до их пропускных способностей — толь-
ко тогда величина потока сравняется с пропускной способностью
рассматриваемого минимального сечения. Следовательно, получен-
ные по индуктивному предположению потоки загружает все прямые
рёбра и (7», А) Д° их пропускных способностей. Более того,
каждое ребро нашей приведённой сети является прямым в некото-
ром минимальном сечении и потому — согласно приведённым выше
рассуждениям применительно к произвольному минимальному сече-
нию — окажется загруженным до пропускной способности его. От-
сюда ясно, что прообраз полученных потоков (в Si и в S2) в исходной
приведённой сети также является потоком и его величина равна cmln.
Теорема доказана.
Глава III
БУЛЕВЫ ФУНКЦИИ И ФОРМУЛЫ
§ 1. Булевы функции. Табличное задание булевых
функций. Существенные и фиктивные переменные
БУЛЕВЫХ ФУНКЦИЙ. ЭЛЕМЕНТАРНЫЕ БУЛЕВЫ ФУНКЦИИ
Функция	называется булевой (или булевской, или
функцией алгебры логики, или логической), если её переменные и
сама функция принимают значения из множества Е2 = {0,1}.
Булева функция от п переменных может быть задана таблицей,
в которой перечислены всевозможные булевы наборы из нулей и
единиц длины п и для каждого набора указано значение функции
на этом наборе (табл. 1).
В этой таблице обычно употребляется естественное расположе-
ние наборов: если набор рассматривать как двоичную запись числа,
то расположение наборов сверху вниз соответствует расположению
Таблица 1
Ж1		Хп	/(ж,,...	Л.)
0	0	0	ДО,...	.0)
0	0	1	/(О,-	,1)
Т	Т	0	/(!,"• •	,0)
1	1	1		.1)
30
чисел 0, l,...,2?l — 1. Таблицы, задающие булевы функции от п пере-
менных, отличаются лишь последним столбцом. Поскольку имеется
ровно 22" различных булевых столбцов высоты 2П, то и число буле-
вых функций от п переменных равно 22\
Булева функция f(x{,..х;,) существенно зависит от перемен-
ной xit если существуют такие значения	+ пе-
ременных	+ что /(^...^..рО, а/ + 1,...,ап)/
f(a},..t, 1, а, +,,..ап); переменная х{ в этом случае называ-
ется существенной. Если переменная не является существенной,
то она называется несущественной или фиктивной.
Пусть для функции	переменная xt является фик-
тивной. Возьмём таблицу, задающую /(жи...,жп). Вычеркнем из неё
все строки вида	+
...,ап)), а также столбец, отвечающий переменной х{. Получен-
ная таблица будет определять некоторую булеву функцию д(х{,...
...,0^, л< + 1,...,жп). Говорят, что функция g(xl,...1xi_{,xi + l,...ixn)
получается из функции f(x{,..., хп) путём удаления фиктивной пе-
ременной хг, а также, что функция f(xr,..., хп) получается из д(х{,...
путём введения фиктивной переменной х{.
Булевы функции и /2 называются равными, если функцию Д
можно получить из функции /2 путём введения и (или) удаления
фиктивных переменных.
Далее предполагаем, что с заданием некоторой булевой функ-
ции / заданы все равные ей функции, и для обозначения равных
функций будем использовать один и тот же функциональный сим-
вол.
Приведём булевы функции от одной переменной и некоторые
функции от двух переменных, которые будем часто использовать да-
лее; это функции (от одной и от двух переменных) обычно называют
элементарными. Имеется четыре булевы функции от одной перемен-
ной (см. табл. 2).
Таблица 2
X	0	1	. *	X
0	0	1	0	1
1	0	1	1	0
Этими функциями являются константы 0 и 1, значения которых
не зависит от значений переменной, тождественная функция х, по-
вторяющая значение переменной, и функция ж, принимающая значе-
ние, противоположное значению переменной. Функция х называется
отрицанием (или инверсией).
Приведённые в табл. 3 булевы функции от двух переменных на-
зываются соответственно конъюнкцией, дизъюнкцией, импликаци-
ей, суммой по модулю два и эквивалентностью.
31
Таблица 3
Х1	Х2		я?! Vag	х\ —^2	Ф $2	*^2
0	0	0	0	1	0	1
0	1	0	1	1	1	0
1	0	0	1	0	1	0
1	1	1	1	1	0	1
§ 2. Формулы и функции, реализуемые
формулами. Простейшие эквивалентности
Так же как и в элементарной алгебре, исходя из элементарных
булевых функций, можно строить формулы. Обозначим через Р2 мно-
жество всех булевых функций.
Пусть В — некоторое (не обязательно конечное) подмножество
функций из Р2. Дадим индуктивное определение формулы над В.
а)	Базис индукции. Каждое выражение f(x^.. .,жп), где f € В,
называется формулой над В.
б)	Индуктивный переход. Пусть	хт) — функция из В и
Фп...,Фт — выражения, являющиеся либо формулами над В, либо
символами переменных. Тогда выражение /0(Ф1?...,Фт) называется
формулой над В.
Примеры формул над множеством элементарных функций:
1)	(((^ Ажг)®
2)	(Яд & (Д^2 ® Дз))»______
3)	(х{ V ((Xj —> ^) & (#3 —> я^))).
Сопоставим каждой формуле Ф(жи..хп) (в скобках указаны пе-
ременные, входящие в формулу) над В функцию /(ж,,...,^), опира-
ясь на индуктивное определение формулы.
а)	Базис индукции. Если Ф^,...,хп) совпадает с /(я^,...,^),
где /еВ, то формуле Ф(ж1?...,жп) сопоставим функцию /(жи...,хя).
б)	Индуктивный переход. Если Ф^,..., хп) совпадает с fQ(Aj,...
...,Am), где /0 — символ функции из В, Л.(г — 1,...,тп) — либо
формула над В, либо символ переменной xy(i), то тогда в пер-
вом случае, по предположению индукции, сопоставляется функ-
ция /• из Р2, а во втором случае Лг сопоставляется тождествен-
ная функция fi = xj{iy Сопоставим формуле Ф(ж1?...,жп) функцию
/(^,...,20 = /o(/u-.->/m); значение функции f на каждом наборе
(а15...,ап) находится как значение функции fQ на наборе
Если функция f сопоставлена формуле Ф, то говорят, что фор-
мула Ф реализует функцию f.
Приведенные выше в качестве примера формулы реализуют, как
не трудно убедиться, функции f^x^x^), Л^п^Дз),
приведённые в табл. 4 и 5.
Формулы Ф! и Ф2 над В называются эквивалентными, если они
реализуют равные функции j\ и /2.
В приведённом выше примере вторая и третья формулы эквива-
лентны.
32
Таблица 4
Таблица 5
		ж2	Л	f3
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	0
1	0	0	0	0
1	0	1	0	0
1	1	0	о.	0
1	1	1	0	0
Приведём некоторые эквивалентности, характеризующие свой-
ства элементарных функций. Обозначим через (х, о х%) любую
из функций (ж1 & х?), V £3), (rrt ф Ж2).
1.	Функция (хх 0X2) обладает свойством ассоциативности:
((®1 ° ®г) °	= (®i ° (^ ° «<))•
2.	Функция (ж, о х%) обладает свойством коммутативности:
(®1 ожг) = (^оя;1).
3.	Для конъюнкции и дизъюнкции выполняются дистрибутивные
законы:
((«1 V ®i) & Х3) =((«!& Хз) V (я^ & Яд)) —
дистрибутивность конъюнкции относительно дизъюнкции;
((®1 & ®2) V Хз) = ((х( V я^) & (хз V ж,)) —
дистрибутивность дизъюнкции относительно конъюнкции.
4.	х — — закон двойного отрицания.
— (®1	~= V I	**
5.	__ __	>—законы де Моргана.
(ж, & Жз) = (я?! V ж2) J
_ (ж & (ж V у)) ~х, 1
6.	в ' г—закон поглощения.
(ж V (ж & у)) — x J
7.	(ж & ж) = 0 — закон противоречия.
8.	(ж \/ж)~ 1 —закон исключённого третьего.
(X &. х} X I
9.	'	’ > — идемпотентность.
(ж\/ж)”Ж J
(ж&0) = 0, '
Ю (ж & 1) = ж, > — законы умножения на константу
(ж V 0) — ж,	и сложения с константой.
(жУ1)-1	>
33
Все перечисленные равенства 1-10 легко проверяются путём
вычисления значений функций в левой и в правой частях равенства
на каждом наборе значений переменных.
С целью упрощения записи формул условимся, что опера-
ция «&», сильнее операции «V», то есть если нет скобок, то сна-
чала выполняется операция «&>>, а затем операция «V». Кроме того,
в силу закона ассоциативности для оа^) можно вместо формул
((#! о о х3), (х{ о(ж2 о ®j)) использовать выражение оа^о а^).
В формулах, в которых внешняя операция (функция) являет-
ся либо конъюнкцией, либо дизъюнкцией, либо сложением по мо-
дулю два, либо импликацией, либо эквивалентностью (либо другой
элементарной функцией от двух переменных), внешние скобки бу-
дем опускать. Опускаются внешние скобки также в выражении, над
которым стоит знак «-», например, пишем х^ вместо (ж/—> .7^).
В дальнейшем будем употреблять также следующие обозначения:
&xi = xl&x2&...&xm,
1 = 1
т
\/ Xi — хх У Х2 V ... V хт,
1 = 1
Х% * Хс^ — «Е| Х% »
Очевидно, справедливо следующее
Утверждение. Если Ф; — подформула формулы Ф, то при
замене любого её вхождения на эквивалентную формулу Ф' фор-
мула Ф перейдёт в формулу Ф, которая эквивалентна Ф.
(Формально данное утверждение можно доказать индукцией
по числу функциональных символов в формуле.)
Данное утверждение позволяет вместе с тождествами для эле-
ментарных функций, к которым присоединяются все тождества, по-
лучаемые подстановкой вместо переменных xiix2,x3,x1y любых пе-
ременных и формул, осуществлять эквивалентные преобразования и,
в частности, упрощать исходные формулы.
Примеры:
1) Xi V х{ Х2 = х{ • I V Х2 = X}(1 V Жг) — х{ • 1 = ж,;
2) х1х2Ух1х2 = (х1Ух1)х2=1-х2 = х2.
§ 3. Разложение булевых функций по
переменным. Дизъюнктивные нормальные формы
Введём обозначение:
° _ ( х при а - 0,
\ X При <7=1.
Очевидно, ха ~ 1 тогда и только тогда, когда х = сг.
Теорема 9 (о разложении функций по переменным). Каж-
дую булеву функцию У(жн...,жп) при любом т(1 т п) можно
представить в форме:
/ (.^,...,	+жп) =
=• V	Xmj	(*)
(а,. ,(тт)
34
где дизъюнкция берётся по всевозможным наборам значений пе-
ременных ,..., хт.
Доказательство. Возьмём произвольный набор значений
переменных (аи...,ап) и покажем, что левая и правая часть соот-
ношения (*) принимают на нём одно и то же значение. Левая часть
даёт /(«!,...,ап). Правая —
v af'	+	=
(*!»•••>'J
= af' &	,am>a,n+1,...,a„) = /(a,,...,a„).
Теорема доказана.
Представление (*) называется разложением функции по пере-
менным xlf...,xm. Выражение /((?{,...,сгт,хт+1,...)Хт) естествен-
ным образом можно рассматривать как формулу над множеством
булевых функций {0,1,/(«!,...,«п)}; реализуемую этой формулой
функцию обычно считают подфункцией функции /(жр...,^), полу-
чающейся из f(xx,..., жп) подстановкой констант ,..., ат вместо пе-
ременных
В качестве следствий из последней теоремы получаем два спе-
циальных случая разложения.
1) Разложение по переменной:
f(xl,...,Xn) = Xn&f(xl,...,Xn_l,l)VXn&f(xl,...,Xn_l,O).
2) Разложение по всем п переменным:
V X?'&...&x'*&f(<Ti,...,(7n).
При хп)^0 оно может быть преобразовано к виду:
V *Г'&...&<••	(♦*)
Последнее разложение называется совершенной дизъюнктив-
ной нормальной формой (с.д.н.ф.). Дизъюнкция в (**) берётся
по всем наборам значений переменных, на которых	об-
ращается в 1.
Теорема 10. Каждая булева функция может быть выра-
жена в виде формулы через отрицание, дизъюнкцию и конъюнк-
цию.
Доказательство.
1) Пусть /(х1,...,жп) “0. Тогда, очевидно, f(xl,...ixn) — xi&xl.
2) Пусть	^0. Представим f в виде с.д.н.ф.:
f(xt>...,Xn) = V Жр
В обоих случаях функция f выражается в виде формулы через
отрицание, дизъюнкцию и конъюнкцию. Теорема доказана.
35
§ 4. Полнота систем булевых функций.
Примеры полных систем. Представление
БУЛЕВЫХ ФУНКЦИЙ ПОЛИНОМАМИ ЖЕГАЛКИНА
Система булевых функций	Л,---} из Д называется
(функционально) полной, если любая булева функция может быть
реализована формулой над этой системой.
Теорема 11 (о полноте двух систем). Пусть даны две
системы функций из Р2:
= (/)
(Я)
относительно которых известно, что первая система полна и
каждая её функция реализуется формулой над второй системой.
Тогда вторая система также является полной.
Доказательство. Для доказательства теоремы покажем,
что для любой формулы над В{ существует эквивалентная ей фор-
мула над В2. Доказательство последнего утверждения проведём ин-
дукцией по сложности формул, понимая под сложностью формулы
число функциональных символов в ней.
Базис индукции. Пусть Ф — формула сложности один над В{,
т. е. Ф =	9...,х- ). По условию теоремы /t можно реализовать
формулой над В2, а значит можно построить формулу над В2, экви-
валентную Ф (говоря об эквивалентности формул в данном случае
формально можно иметь в виду формулы над В, U В2).
Индуктивный переход. Пусть утверждение верно для всех фор-
мул над Вх сложности 1,2,..к; докажем его для произвольной фор-
мулы Ф над Bj сложности к 4-1. Пусть Ф =	,..., Ат), где А}- —
либо формула над Ви либо символ переменной (j = l,...,m).
Возьмём формулу над Вг вида /г(ж15..., хт), по условию теоремы
существует эквивалентная ей формула ^(xi9...9xm) над В2. Подста-
вим в и в Ф вместо Xj всюду Aj (в ft переменная Xj входит только
один раз, а Ф может содержать несколько вхождений яД В результа-
те fi и Ф перейдут в некоторые формулы, которые опять же будут эк-
вивалентными — с учётом определения функций, реализуемых фор-
мулами. Такую подстановку проделаем сразу для всех j = l,...,m.
В итоге вместо /Дж15...,жт) получим формулу Ф над Ви реализу-
ющую	а вместо Ф(гэ1,..хт) — некоторую формулу Ф'
над В{ UB2, также реализующую f(xx,...,xn). В формуле Ф' каждую
подформулу А. (отличную от переменной) над Д заменим эквива-
лентной ей подформулой Фу над В2 — такую замену можно проделать
по предположению индукции, поскольку сложность Ajt очевидно,
по крайней мере на единицу меньше сложности формулы Ф. В итоге
вместо Ф' получим формулу Ф" над В2, реализующую f(x{9...,xn) —
согласно ранее приведённому утверждению о замене в формуле неко-
торой подформулы эквивалентной ей подформулой. Теорема доказа-
на.
Приведём примеры полных систем.
1.	Система Р2 — множество всех булевых функций — является,
очевидно, полной.
2.	Система Вх -- {х, хх & x2i хх V т2} полна по теореме 10.
3.	Система В2 = {х,хх&х2} является полной. Для доказательст-
ва достаточно воспользоваться тождеством х} V х2 — хх & х2 и теоре-
мой 11.
4.	Система В3 == {ж, х1Ух2} является полной. Для доказательства
этого утверждения достаточно воспользоваться тождеством хх & дх, =
= х\/х2 и теоремой 11.
5.	Система В4 = {0,1, хх & хх ф ж2} является полной. Для дока-
зательства этого факта достаточно заметить, что жф 1 — х и восполь-
зоваться теоремой 11 (взяв в качестве первой системы {х,хх
а в качестве второй — систему В4.
Формула, построенная из констант 0, 1 и функций xi&x2, ж,фа^,
после раскрытия скобок и несложных алгебраических преобразова-
ний переходит в выражение вида
Е
которое является полиномом по mod 2 и называется полиномом Же-
галкина.
Теорема 12 (Жегалкина). Каждая булева функция мо-
жет быть представлена и притом единственным образом своим
полиномом Жегалкина.
Доказательство. Возможность реализации любой булевой
функции полиномом Жегалкина уже установлена выше — такая воз-
можность следует из полноты системы {0, lixi&x2,xl^x2}. Докажем
единственность.
Подсчитаем число полиномов Жегалкина от переменных яп...
...,жп, т. е. число выражений вида
<•>.<.)
Число членов х^ ...х, равно количеству подмножеств	из
п чисел 1,...,п, т. е. 2п. Поскольку а. { равно 0 или 1, то искомое
число полиномов равно 22", т. е. числу булевых функций от тех же п
переменных. Отсюда получаем единственность представления функ-
ций посредством полиномов Жегалкина. Теорема доказана.
§ 5. Функции ьзначной логики
Функция /(хи...,хп) называется функцией k-значной логики,
если переменные этой функции принимают значения из множества
Ek = {0,l,...,k - 1} и /(«!,...,<*„)€Ек при a(eEk(i =
Функции &-значной логики можно задавать с помощью таблиц
(аналогично табличному заданию булевых функций). Из табличного
задания функций fc-значной логики легко усмотреть, что число всех
функций fc-значной логики от п переменных равно kk”.
Аналогично тому, как это делалось для булевых функций, для
функций fc-значной логики вводятся понятия существенной и фик-
37
тивной переменных, равенства функций, формул над множеством
функций, реализуемых формулами функций, эквивалентности фор-
мул.
В качестве элементарных функций в /с-значной логике часто рас-
сматриваются, например, также функции.
1)	х = х 4-1 (mod к) — отрицание Поста;
2)	Лх ~к — \ — х — отрицание Лукашевича;
г / х f fc — 1 при ж =
3)Ь(ж)=<	r	—характери-
J (0 при ж/j (j = 0,	1)
стическая функция (второго рода) числа j;
\ Г 1 при х — г,
= L	j — характеристиче-
(0 при х^ г (г =0, l,...,fc - 1)	г
ская функция числа г;
5)	— минимум хг и а^;
6)	х{ • X} (modк) — произведение по модулю к;
7)	тах(ж1,ж2)— максимум xt и
8)	хх 4- х% (modк) — сумма по модулю к;
9)	14(ж1,ж^) = тах(ж1,ж2)4' 1 (modfc) — функция Вебба.
Функция min(xna^) является обобщением конъюнкции и часто
обозначается как хх &^. Функция тах(ж1,жг) является обобщением
дизъюнкции и часто обозначается как х1 V
Наряду с очевидными элементами сходства между булевыми
функциями и функциями fc-значной логики имеются и существен-
ные различия между этими функциями. Например, отрицания По-
ста и Лукашевича можно рассматривать как некоторые обобщения
инверсии булевой функции; вместе с тем при fc > 3 для отрицания
Поста в fc-значной логике х. Или, скажем, для булевых функций
простейшие эквивалентности можно было доказывать тривиальным
образом — перебирая всевозможные наборы значений переменных
и убеждаясь, что во всех случаях значения эквивалентных формул
(или, точнее, функций, отвечающих эквивалентным формулам) в ле-
вой и в правой частях соответствующих равенств при одних и тех же
значениях переменных совпадают. В fc-значной логике перебор все-
возможных наборов значений переменных исключается, поскольку к
может быть, вообще говоря, каким угодно натуральным числом (боль-
шим двух).
Для функций fc-значной логики возможны представления, ко-
торые можно рассматривать как некоторые аналоги совершенной
д.н.ф., например:
(^р..-^n)
где х &у — min(x, у), х V у ~ тах(х, у). Доказывается это тождество
(как и разложение булевой функции по всем переменным) непосред-
ственной проверкой того факта, что при любом наборе (ар...,^)
значений переменных в левой и в правой частях тождества полу-
чаем /(аи...,ап). Из этого представления следует, в частности,
что система функций &-значной логики {0,1,..., к — 1,10(х), (ж),...
...,1А;_1(х),тт(ж1,Ж2),тах(ж1,ж2)} полна в Рк (через Рк обозначаем
множество всех функций Aj-значной логики при заданном к).
38
Глава IV
СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ.
СИНТЕЗ И ОЦЕНКИ СЛОЖНОСТИ СХЕМ
§ 1.	Схемы из функциональных элементов в базисе {&, v,-}
Схема из функциональных элементов в базисе {&, V, —} есть
помеченный ориентированный граф G = (V,E) без контуров, удов-
летворяющий следующим условиям.
1)	Все вершины этого графа разбиваются на три непересекаю-
щихся подмножества Vlf V2, V3 так, что:
a)	v = v;u v2u у3, т<пу;. = 0при г/У;
б)	в каждую вершину из V[ не входит ни одной дуги;
в)	в каждую вершину из V2 входит по одной дуге;
г)	в каждую вершину из V3 входят по две дуги.
2)	Каждой вершине из Vt приписана некоторая переменная xit
причём разным вершинам приписаны разные переменные.
3)	Каждой вершине v' из V2 приписан символ — (функция х).
4)	Каждой вершине v" из V3 приписан один из символов &, V
(одна из функций х1 & х^ xt V я^).
5)	Выделено некоторое подмножество V* (V* С V) вершин.
Вершины из VJ (в которые не входят дуги) называются входами
схемы; если вершине v из VJ приписана переменная ж£, то говорят,
что на вход v подаётся переменная я£.
Вершины из V2 и V3 (в которые входят дуги) называются функ-
циональными элементами схемы. Каждая вершина из V2 (с припи-
санным ей символом —) называется инвертором. Каждая вершина
из V3 с приписанным ей символом & называется конъюнктором,
а каждая вершина из V3 с приписанным ей символом V называется
дизъюнктором.
Выделенные вершины из V* называются выходами схемы.
На рис. 9,а приведена некоторая схема из функциональных эле-
ментов, имеющая два входа, один выход и четыре функциональных
элемента.
39
Пусть G = (V,E)— ориентированный граф, вершины которого
занумерованы натуральными числами. Нумерацию вершин графа G
будем считать монотонной, если для любой дуги (v, v') g Е номер
вершины v меньше номера вершины vf.
Лемма 4. Любой (конечный) ориентированный граф без
контуров допускает монотонную нумерацию вершин.
Доказательство. Пусть G — (V, Е) — ориентированный
граф без контуров. Возьмём в графе G произвольный путь Z мак-
симальной длины (т. е. с максимальным числом рёбер) без повто-
ряющихся рёбер; поскольку G — конечный граф и контуры в нём
отсутствуют, то указанный путь Z найдётся. В вершину и, являющу-
юся началом пути Z, дуги не входят — иначе путь Z не являлся бы
максимальным. Вершине v припишем номер 1 и удалим из G эту
вершину вместе с выходящими из неё дугами.
Точно так же в оставшемся ориентированном графе без конту-
ров Gx найдём вершину, в которую не входят дуги, и припишем этой
вершине номер 2. И так далее. Полученная нумерация вершин по
построению будет монотонной для исходного графа G. Лемма дока-
зана.
Рассмотрим теперь произвольную схему S из функциональных
элементов с п входами, на которые подаются переменные х19,..9хп.
Согласно лемме 4 все вершины схемы S занумеруем так, чтобы полу-
ченная нумерация вершин была монотонной. Далее всем вершинам
схемы S в порядке возрастания номеров этих вершин сопоставим
булевы функции по следующим правилам.
Вершина vr имеет наименьший номер и является, очевидно, вхо-
дом схемы, на который подаётся некоторая переменная хх. Тождест-
венную функцию хх сопоставим вершине
Рассмотрим k-ю вершину vk. Вершина vk либо является входом
схемы, либо в vk входит ровно одна дуга, либо, наконец, в vk входят
две дуги. В первом случае вершине vk как входу схемы приписа-
на некоторая переменная xf, в этом случае вершине vk сопоставим
тождественную функцию х-.
Во втором случае в вершину vk входит ровно одна дуга, выходя-
щая из некоторой вершины v. В силу монотонной нумерации вершин
схемы вершине v уже сопоставлена некоторая булева функция Д;
отрицание этой функции, т. е. fv сопоставим вершине vk.
В третьем случае в вершину vk входят две дуги, выходящие
из некоторых вершин v', v", которым уже сопоставлены (в силу мо-
нотонной нумерации вершин схемы) булевы функции fv, и fv„ соот-
ветственно. В этом случае вершине vk сопоставим булеву функцию
fv, если vk —конъюнктор, или Д, V fv„, если vk —дизъюнктор.
Если вершине v схемы из функциональных элементов сопостав-
лена булева функция /, то будем говорить, что в вершине v реализу-
ется булева функция /. Схема по определению реализует упорядо-
ченную систему булевых функций, сопоставленных выходам данной
схемы.
Лемма 5. Булевы функции, реализуемые в вершинах схемы,
полностью определяются самой схемой независимо от монотон-
ной нумерации вершин схемы.
Доказательство проведём индукцией по числу элементов
в схемах.
40
Основание индукции. Для схем без элементов (такие схемы со-
держат только входы и некоторые из этих входов являются одновре-
менно и выходами схемы) утверждение леммы, очевидно, выполня-
ется.
Индуктивный переход. Пусть утверждение леммы выполняется
для всех схем, содержащих не более к элементов; докажем, это
утверждение для схемы 5, содержащей к +1 элементов. Рассмотрим
две монотонные нумерации вершин схемы 5. Входом схемы, очевид-
но, сопоставляются одни и те же (тождественные) булевы функции
как при первой нумерации, так и при второй.
Пусть v — элемент схемы 5, получивший наименьший (среди
номеров элементов) номер при первой нумерации, и этому элементу
при первой нумерации сопоставлена булева функция fv. Поскольку
в вершину v могут входить только дуги, выходящие из входов схемы,
то и при второй нумерации элементу v будет сопоставлена та же
самая функция Д.
Схеме S сопоставим схему S', получающуюся из S удалени-
ем всех дуг, входящих в v; вершину v в схеме S' объявим входом,
на который подаётся y~fv. Очевидно, что всякая монотонная для S
нумерация вершин останется монотонной и для S'. Ясно, что при
первой нумерации одноимённым вершинам в схемах S и S' будут
сопоставлены одни и те же функции; точно так же при второй нуме-
рации одноимёнными вершинами в S и в S' будут сопоставлены одни
и те же функции. Но по предположению индукции в схеме S' каждой
вершине окажется сопоставленной одна и та же булева функция как
при первой нумерации, так и при второй. Лемма доказана.
Согласно лемме 5 функции, реализуемые схемой из функцио-
нальных элементов, определяются единственным образом. Часто
функциональные элементы схем изображают в виде треугольников.
Например, схему, приведённую на рис. 9,а можно изобразить ещё и
так, как показано на рис. 9,6; на последнем рисунке указаны также
функции, реализуемые в вершинах схемы (на «выходах» элементов
схемы).
Две схемы называются изоморфными, если они получены из изо-
морфных графов так, что:
1)	соответствующим входам приписаны одинаковые переменные;
2)	соответствующим элементам приписаны одинаковые символы
функций;
3)	выходам одной схемы соответствуют выходы другой и наобо-
рот.
Ясно, что любые две изоморфные схемы реализуют одну и ту же
(неупорядоченную) систему булевых функций.
§ 2. Синтез схем с использованием днф
Сложность произвольной схемы S определим как число эле-
ментов в этой схеме и обозначим через L(S). Положим L(f) —
= minL(5), где минимум берётся по всем схемам, реализующим
булеву функцию /. Аналогично для системы функций F положим
L(F) ~ minL (5), где минимум берётся по всем схемам, реализую-
щим систему функций F. Число L(f) называется сложностью реа-
лизации функции f или просто сложностью функции f. Аналогич-
но, L(F)— сложность системы функций (оператора) F.
Пусть Qn(x^,,^xn)— система всех 2” конъюнкций вида хх' ...
Теорема 13. L(Qn) < 2'111 + п - 4.
Доказательство проведём индукцией по п. При п = 1
утверждение очевидно — достаточно лишь с помощью одного инвер-
тора реализовать хх, Предположим, что утверждение справедливо
при п = 1,..к; докажем его для п — k -Ь 1.
Опираясь на предположение индукции, построим схему Sx
из 2к +1 + k —4 элементов, реализующую все 2к конъюнкций х? ...хкк.
Добавим к S{ инвертор Е~, с помощью которого реализуем xfc + 1. За-
тем добавим ещё 2к и конъюнкторов, на выходах которых получим
требуемые конъюнкции хх' ... х%кхк^{. При реализации конъюнкции
xx' ...хккхккЛ на выходе конъюнктора Е& один вход этого конъюнкто-
ра соединим с выходом на котором реализуется хр...х%к, а второй
вход элемента Е& соединим со входом схемы, соответствующим хк + р
если сгк +1 = 1, или с выходом инвертора Е~, если ак + i = 0; здесь и да-
лее под входом элемента подразумеваем дугу, входящую в вершину,
изображающую данный элемент, а под выходом элемента подразуме-
вается сам этот элемент.
В итоге получим схему, содержащую 2*+2 + fc + l- 4 элементов.
Теорема доказана.
Укажем теперь простой метод синтеза схем для реализации про-
извольной булевой функции.
Теорема 14. Любую булеву функцию от п переменных
можно реализовать схемой, содержащей не более чем 3 • 2п + п — 5
элементов.
Доказательство. Пусть дана произвольная булева функ-
ция f (x{,..., я^). Если f(xx,..хп) “0, то реализуем / схемой из двух
элементов, указанной на рис. 10.

Рис. 10
Пусть /(«j,...,хп) =£0. Представим f в виде совершенной д.н.ф.:
/(#,,...,Zn)- V ХХ1,.,Х^.	(*)
(«Гр. м«Гп)
/(<Л >• ,<0^1
42
Опираясь на утверждение теоремы 13, реализуем все элемен-
тарные конъюнкции вида «f* ... схемой S, содержащей не более
чем 2П*И -h п - 4 элементов. К S добавим цепочку Z из дизъюнкто-
ров, с помощью которой реализуем логическую сумму из (*); входы
цепочки Z соединим с теми выходами схемы 5, на которых реали-
зуются слагаемые из (*). В Z войдут, очевидно, не более чем 2п - 1
дизъюнкторов (см. рис. 11).
В итоге получим схему, удовлетворяющую требованию теоремы.
Теорема доказана.
fe-1 «.
элемент
Рис. И
При конструктивном доказательстве теоремы 14 строилась схе-
ма, в понятном смысле «моделирующая» совершенную д.н.ф. реали-
зуемой булевой функции.
§ 3. Метод Шеннона
Пусть L(n) = maxL(f), где максимум берётся по всем буле-
вым функциям от п переменных; функцию Цп) обычно называют
функцией Шеннона. Содержательный смысл функции Шеннона про-
стой — это наименьшее возможное число элементов, достаточное
для реализации любой булевой функции от п переменных. Из те-
оремы 14, очевидно, следует оценка L (п) < 3 • 2П + п — 5. Эту оценку
можно существенно улучшить, если воспользоваться методом синте-
за схем, предложенным Шенноном. С использованием этого метода
получим оценку
М”)<Цг-
Пусть /(^15...,хп) — произвольная булева функция от п пере-
менных. Разложим функцию f по п - к переменным
V х"'	(1)
Схема S для функции f строится из трёх блоков (подсхем), ука-
занных на рис. 12:
1)	блока, реализующего Qn_fc(a:l,...,a:n_Jfc);
2)	блока, реализующего систему Vk(xn__k и,...,хп) всех 22* бу-
левых функций от к переменных хп__к
3)	блока, осуществляющего соединение первых двух блоков в со-
ответствии с представлением (1).
В третьем блоке на каждое слагаемое из (1) приходится не более
одного конъюнктора и не более одного дизъюнктора. Следовательно,
L(S)<L(Qn_k) + L(Vt) + 2-2-*.	(2)
Реализуя каждую функцию из Vk отдельной подсхемой и исполь-
зуя теорему 14, получаем оценку
L(VJ<2*^-22‘.	(3)
Из (2), (3) и теоремы 13 имеем
L(S) < 4 2n~fe + 2k+222* 4- п - к - 4.	(4)
Положим (при достаточно больших п)
fc = [log(n - 31ogn)j.
(Здесь и далее используются обозначения: [а] — целая часть
числа; log а — двоичный логарифм а.)
Тогда
log(n — 31ogn) - 1 < k log(n - 31ogn),
2^^<2^n-31ogn,
22 < K.
n6
Из (4) и последних оценок следует, как нетрудно убедиться, требуе-
мая оценка
г / S-2n
L(n)~
44
§ 4. Асимптотически оптимальный
МЕТОД СИНТЕЗА СХЕМ (МЕТОД ЛУПАНОВА)
Вначале введём специальное представление булевых функций.
Пусть	-»п) — произвольная булева функция; зададим её таб-
лицей (см. табл. 6).
В этой таблице значение функции f на наборе (а1?...
...,an_fc,an_fc + i,...,an) помещается на пересечении столбца, соот-
ветствующего (<^i,• •и строки, соответствующей (<7л_* + 1,...
...,ап). Разобьём строки таблицы на полосы Alit..yAp по з строк
в полосе (последняя полоса может содержать меньшее число строк).
Ясно, что
Пусть f. —функция, совпадающая с f на полосе Аг и равная 0 вне
этой полосы. Очевидно, что
/(®1,..Ш„) = V ffa,..Х„) =
1 = 1
= .v v X1 •••<"-* Л to..........(*)
Заметим, что каждая из функций Л(^,...,<7П_Л,яп_Л + 1,...,яп)
задаётся одним столбцом таблицы для функции ft и поэтому прини-
мает значение 1 не более чем на з наборах; число различных функ-
ций Л(^1,...,огп_а,жп_а! + 1,...,жп) (при фиксированном г) не превос-
ходит 2е.
Опишем теперь метод синтеза, основанный на специальном
представлении (*). Схема S для функции f составляется из 6 бло-
ков (соединение блоков условно показано на рис. 13; двойной линией
очерчен блок, содержащий «почти все» элементы схемы, что будет
видно из дальнейшего).
45
1.	Блок А реализует систему р„_А(Х].®п-*) всех конъюнк-
ций переменных Хр...,хп_к; по теореме 13
L(A) 2"-* + 1 + п - к - 4.
2.	Блок В реализует систему Р(хп_* + 1,...,хп) всех конъюнкций
переменных ®п_* + 1,...,®п); по теореме 13
L(B)«$2* + 1 + fc -4.
3.	Блок С реализует все различные функции
...,ап_к,хп_к + к...,х„). Из сказанного выше следует, что для реа-
лизации одной такой функции (с использованием конъюнкций, реа-
лизованных блоком В) требуется не более чем з дизъюнкторов (или
один конъюнктор, если функция равна 0). А в целом
L(C)<pa2'.
4.	Блок D реализует все функции
V'fAVl,---,Хп_к + 1....Х„) =
=	> • • •> ffn - * » Хп - к + 1 > • • •> Жп)>
L(D) 2п~'!.
5.	Блок G осуществляет умножение
Ж/ ...	+
L(G)^2"-‘.
46
6.	Наконец, блок F реализует функцию f(xx^t^xn) как дизъ-
юнкцию функций, реализованных блоком G;
L(F)<2nk,
Таким образом,
L(S)^ L(A) 4- L(B) + L(C) + L(D) + L (G)4- L(F)<
< 2"-* + 1 4-n — fc — 4 4-2A + 1 4- & — 4 4-p.s2e 4-p2n"fe 4-2n“fc + l C
< 5 • 2n~k + 3 • 2n~k 4- (~ 4- 1) (2W-A + a • 2е).
Положим к = [3 log nJ, s = [n - 5 log nJ. Непосредственной про-
веркой нетрудно убедиться, что при таком выборе параметров к и з
X(S)< ^(1 + 0(1^)),
и, следовательно, имеет место
Теорема 15. L(n) < £(1 + О(^)).
§ 5. Мощностной МЕТОД ПОЛУЧЕНИЯ
НИЖНЕЙ ОЦЕНКИ ДЛЯ СЛОЖНОСТИ СХЕМ
Общий приём, с использованием которого можно получить ниж-
нюю оценку для L(n) был предложен К. Шенноном. Этот приём
основан на том соображении, что схем малой сложности мало и их
не хватает для реализации всех функций от п переменных, в связи
с чем существуют функции, требующие схем большей сложности.
Обозначим через N(n, к) число различных (неизоморфных) схем
из функциональных элементов в рассматриваемом базисе {&, V, —
имеющих не более п полюсов (входов), соответствующих некоторым
переменным из множества {х19...,хп}9 один выход и не более к эле-
ментов. Кроме того будем рассматривать схемы, у которых каждый
полюс и каждый элемент, не являющийся выходным элементом (вы-
ходом) схемы, соединены выходящими из них дугами с некоторыми
элементами (иначе полюс или элемент можно из схемы удалить и
реализовать заданную функцию более «простой» схемой с меньшим
числом входов или с меньшим числом элементов). Получение ниж-
ней оценки основано на следующем утверждении.
Лемма 6 (о нижней оценке). Если для некоторой функ-
ции к(п) при п —> оо выполнено условие
^^-0,	(*)
то, начиная с некоторого п, имеет место оценка
L(n) > &(п),
причём доля тех функций /(a?j,...,xn), для которых L(f) к(п),
стремится к 0 с ростом п.
47
Доказательство. Каждая функция f(x{,..хп) такая, что
L(/) к(п), реализуется некоторой схемой, содержащей не более п
полюсов и не более к(п) элементов, причём разные функции требу-
ют разных схем. Поэтому число таких функций / не превосходит
7V(n, fc(n)), и в силу условия леммы (*) их доля среди всех функ-
ций от п переменных стремится к 0 с ростом п. Тем самым вторая
часть утверждения леммы доказана.
Из (*) следует, что, начиная с некоторого п, выполняется нера-
венство
N(ntk(n)) . 1
-2’
т. е. при этих п по крайней мере половина всех функций от п пере-
менных имеет сложность выше к(п), а потому L(n) > к(п). Лемма
доказана.
Таким образом, задача получения нижней оценки для функции
Шеннона L(n) свелась к оценке величины N(n, к(п)) и к подбору
по возможности большей функции к(п), удовлетворяющей условию
леммы.
Оценим число схем N(n, к(п)).
Лемма 7. N(n, к) < (32(п 4- А0)п+Л+3.
Доказательство. Рассмотрим схему, содержащую п' п
входов, кх инверторов и к% конъюнкторов и дизъюнкторов. Эта схема
обладает следующими свойствами:
1)	она имеет п' 4-	4- к% вершин, причём некоторые из этих
вершин отмечены символами переменных х^..чх%1 из множества
{жи...,.тп}, а остальные — символами &,V,-, кроме того, вершине,
из которой не выходит ни одна дуга (такая вершина единственна),
приписана метка *;
2)	она имеет ^4-2/^ дуг, причём в каждую вершину, отмеченную
символом ~, входит одна дуга, а в каждую вершину, отмеченную
символом & или V, входят две дуги;
3)	для каждой вершины существует путь, ведущий из этой вер-
шины в вершину, помеченную символом * (поскольку из каждого
входа и из каждого элемента, отличного от выходного, выходят дуги,
а контуры отсутствуют).
Обозначим через 5(n,n',k^kz) множество всех схем, обладаю-
щих перечисленными тремя свойствами, а через 2V(n, п', к{, к^) — их
число. Ясно, что
N(n,k)^	(1)
n',fcj,k2
(n' < n,	4 < fc)
Оценим величину N(n, n‘, k{1 fc>).
Для произвольной схемы из 5(n, n', kt, к%) возьмём соотнесённый
граф; очевидно, что в этом графе можно выделить дерево с корнем
в вершине *, содержащее все вершины графа (такое дерево можно
получить, удаляя из исходного связного соотнесённого графа в произ-
вольной последовательности циклические рёбра). Исходя из сказан-
ного, каждую схему из S(n, n',	А-2) можно построить следующим
образом.
1)	Выбирается дерево с корнем, содержащее п14- к{ 4* к% вершин
и п 4- к{ -t- к2 ~ I рёбер; согласно верхней оценке для числа корневых
48
деревьев (теорема 4) это можно сделать не более чем 4™'*4
^4п+*» + ^ способами.
2)	Корню приписывается символ *, а дуги ориентируются; это
делается не более чем 2n + ki + kz способами.
3)	Из множества я,,} выбираются ri переменных ж,,...
для этого имеется С”' 2п возможностей.
4)	Одна из вершин отмечается символом xt, другая — символом
и т. д., некоторая n'-я вершина отмечается символом xlt; для
выбора каждой вершины имеется не более ri 4- 4- А^ возможностей,
поэтому вариантов выбора всех вершин не больше (ri 4- к{ -h
(n 4~ Aij 4~ Ai2)n.
5)	Среди к{ 4- А^ вершин, не отмеченных символами переменных,
выбираются А?! вершин и отмечаются символом это можно сделать
С^+ < 2*1 + способами. Каждая из остальных А^ вершин отмечается
одним из символов & и V; для этого имеется 2** возможностей.
6)	Полученный граф (ориентированное дерево) содержит ri 4-
4- Ajj 4- А^ — 1 дуг (на одну меньше числа вершин), а всего в графе
должно быть к{ 4- 2А^ дуг. Для недостающих А^ 4- 2А, ~ (ri 4- к{ 4-
4~/с2~1) = /с2 — тг' 4-1 дуг известны вершины, в которые они вхо-
дят (поскольку в каждую вершину, помеченную & или V, должны
входить две дуги, а в каждую вершину, помеченную -, одна ду-
га). Вторые концы каждой из этих дуг можно выбрать не более чем
ri 4- 4- А^ способами; при этом всего вариантов выбора не больше
(ri 4-^4- А^)** (п 4- fcj 4- &2)\ После этого шага схема полностью
построена.
Величина 2V(n, А?и А^) не превосходит произведения оценок
из пунктов 1-6:
N(nyri, Aip&j) <
4"+*i + *».. 2п(п 4- 4- А^)п • 2*> + к> • 2^(п 4- кх 4-
< (32(п 4- А?! 4- А^))п+*‘ + = (32(п 4- к))п+к.
При суммировании в (1) по п\к{ и А^ для вычисления N(nyk) ин-
декс ri может принимать не более п значений (от 1 до п), а каждый
из индексов А^ и А^ — не более к 4-1 значений (от 0 до к). Поэтому
N(n, к) < п(к 4- 1)2(32(п 4- к))п+к.
Отсюда, поскольку n > 1, окончательно получаем
N(n,k)^(32(n + к))п + к + 3.
«Лемма доказана.
С использованием последних двух лемм докажем теперь следу-
ющее утверждение.
Теорема 16 (нижняя оценка сложности схем). При всех
достаточно больших п
2п
и доля тех функций f(x^...>xn), для которых L(f)^ —, стре-
мится к 0 с ростом п.
49
Доказательство. Для доказательства теоремы достаточно
проверить выполнимость условия (*) леммы 6 (о нижней оценке) и
применить затем эту лемму при fc(n) = Условие (*), очевидно,
эквивалентно при этом условию
logW(ri, - 2"-►-оо.	(2)
Используя лемму 7, получаем цепочку соотношений
logiV(n, £) - 2" < (п + £ + 3) (5 + log(n + £)) - 2П <
, 9П ч /	9*4-2 .
<(« + y + 3)(5 + logV)-2n=-
= (п + — + 3) (п 4- 7 - log п) - 2П =
= logn 4- 7~- 4- п2 — nlogn 4- Юп — 31ogn 4- 21 =
= -?logn(l-o(l)).
Последняя величина стремится к -оо и условие (2), а с ним и
условие (*) леммы 6 оказывается выполненным. Теорема доказана.
Сопоставляя верхнюю и нижнюю оценки для L(n) (теоремы 15
и 16), получаем следующее утверждение.
Теорема 17 (Лупанова О. Б.). Имеет место асимптоти-
ческое равенство
о*
9*
причём доля тех функций	для которых L(f)^ —,
стремится к 0 с ростом п.
Таким образом, почти все булевы функции являются асимптоти-
чески самыми сложными, и метод Лупанова строит для почти всех
функций почти наилучшие (асимптотически наилучшие) схемы.
Глава V
ОГРАНИЧЕННО-ДЕТЕРМИНИРОВАННЫЕ
ФУНКЦИИ И РЕАЛИЗАЦИЯ ИХ АВТОМАТАМИ
§ 1. Детерминированные и
ОГРАНИЧЕННО-ДЕТЕРМИНИРОВАННЫЕ ФУНКЦИИ
Возьмём множество Ef всех двузначных последовательно-
стей 6, где 6 = {6(1),5(2),...,6(г),...} и 8(г)еЕ2, Е2 = {0,1}. Обо-
значим через множество всех функций f(x{,..., хп), определённых
на наборах (а15...,ап), где 6 Ef (i - 1,...,п), и принимающих
значения из Ef. Таким образом, функции из Рс преобразуют дву-
значные последовательности в двузначные последовательности.
50
Пример. Рассмотрим функцию f(x) такую, что /(а) =
=/({а(1),а(2),...}) = {а(1),а(3),а(5),...}. Очевидно, что f(x)G
еРс.
Набор переменных (х{,...,хп) в векторной записи обозначим
через X и вместо /(о?!,...,®п) будем писать также /(X). При
этом переменная X принимает значение а из множества набо-
ров {(ап...,ап)}, компонентами которых являются двузначные по-
следовательности: a< = {at(l),at(2),...,a<(m),...}, г = 1,...,п. Вме-
сте с тем а можно рассматривать как последовательность векто-
ров (наборов из нулей и единиц длины п) а = {а(1),а(2),...},
где а(» = (a^J),...,^^)), > = 1,2,... В последнем случае мож-
но считать, что последовательность а = {а(1),а(2),...} описыва-
ет значения последовательности переменных {Х(1),Х(2),...}, где
Х(т) = (ж1(т),...,жп(т)).
Функция f(X) из Рс называется детерминированной, если ка-
ково бы ни было натуральное число т и каковы бы ни были по-
следовательности а и /3 такие, что а(1) =/3(1),..., а(тп) =/3(тп),
в последовательностях 7 = f(a) и 6 = /(4) первые т членов также
совпадают, т. е. 7(1)= 5(1),..., 7(771) = 6(т).
Множество всех детерминированных функций обозначим че-
рез Рд.
Для детерминированной функции значения 7(771) тп-го чле-
на (тп = 1,2,...) последовательности 7 полностью определяет-
ся значениями т членов последовательности а, т. е. 7т =
=/ш(а(1),...,а(т)). Поэтому детерминированную функцию f(X)
можно определить с помощью последовательности булевых функций
/ДХ(1))72(Х(1),Х(2)),...,/^Х(1),Х(2),...,Х(т)),...,где
JC(l)=(o;1(l),ax2(l),...,a:n(l)),
Х(2)=(ж1(2),жг(2),...,а?п(2)),
X (т) =(2?! (тп), х2(т)).... хп(т)).
Детерминированная функция /(х^...,хп) может быть проинтер-
претирована как функция, описывающая работу дискретного преоб-
разователя с п входами и одним выходом (см. рис. 14).

д. п.
Рис. 14
На входы этого преобразователя в моменты времени £ = 1,2,...
...,тп,... подаются последовательности
«1
а2 ={а2( 1), а2(2),..a2(m),...},
а» ={<*»( 1 )> «,.(2), ап(т),...}.
В эти же моменты времени на выходе возникает последовательность
7 = {7(1),7(2),...,7(т),...}. Тем самым мы имеем дело с некото-
рой функцией /(жи...,жп) из Рл. Очевидно, что в дискретном пре-
образователе значение у(т) зависит только от значений входных
последовательностей в моменты времени t = 1,..., т. Поэтому функ-
ция f на выходе дискретного преобразования суть детерминирован-
ная функция. Дискретный преобразователь указанного вида обычно
называют автоматом, реализующим функцию f(xx,...,xn).
Пусть f(X) — функция из Р*. Рассмотрим бесконечное корневое
ориентированное дерево, представленное на рис. 15.
Из корня £0 этого дерева исходит пучок из N — 2п дуг, образу-
ющих первый ярус. Каждая из дуг первого яруса ведёт в вершину,
из которой в свою очередь исходит пучок из N дуг, образующих 2-й
ярус, и т. д. Вершины, являющиеся концами дуг m-го яруса, причи-
сляются также к m-му ярусу. Вершина £0 считается вершиной нуле-
вого яруса. Дуги каждого пучка нумеруются слева направо числами
0,- 1 или их записями в двоичной системе счисления.
Бесконечный простой путь с началом в корне £0 будем называть
ветвью рассматриваемого дерева. Очевидно, что каждой ветви дерева
можно сопоставить последовательность а = {а(1), а(2),...} номеров
дуг, входящих в эту ветвь, если идти по ней, начиная от корня. И на-
оборот, любой бесконечной последовательности чисел из множества
{0,1,...,ЛГ- 1} однозначно соответствует некоторая ветвь дерева.
Таким образом, существует взаимно-однозначное соответствие меж-
ду множеством всех ветвей дерева и множеством всех бесконечных
последовательностей чисел из множества {0,1}, которые
мы естественным образом можем занумеровать наборами из нулей и
единиц длины п.
Как отмечалось выше, детерминированная функция f(X) мо-
жет быть задана с помощью последовательности булевых функций
/1(X(l))J2(X(l),X(2)),...Jm(X(l),X(2),...,X(m)),... Используя
эту последовательность, каждой дуге дерева можно однозначно при-
писать либо 0, либо 1. Возьмём произвольную дугу m-го яруса
52
(т = 1,2,...) и рассмотрим путь, ведущий из корня дерева к этой
дуге. Очевидно, этот путь определён однозначным образом и характе-
ризуется набором (а(1),...,а(т)) номеров дуг пути, отсчитываемых
от корня. Исходной дуге припишем число у(т) — /т(а(1),..., а(т)).
Полученное дерево будем называть занумерованным деревом.
Таким образом, имея произвольную детерминированную функ-
цию, можно построить соответствующее ей занумерованное дере-
во. С другой стороны, возьмём бесконечное ориентированное дерево
с корнем, из каждой вершины которого исходят ровно 2П дуг. За-
нумеруем его произвольным образом, т. е. каждой дуге припишем
либо 0, либо 1. Ясно, что полученное занумерованное дерево опре-
делит, причём однозначным образом, некоторую детерминированную
функцию, зависящую от переменных х{,..., хп.
Пусть f(x{,..., хп) — произвольная детерминированная функция.
Рассмотрим соответствующее ей занумерованное дерево. Пусть £ —
произвольная его вершина из m-го яруса. В неё ведёт из корня £0
путь а(1),...,а(тп). Совокупность всех ветвей, исходящих из £, по-
рождает некоторое дерево с корнем £ (являющееся поддеревом ис-
ходного дерева). Так как исходное дерево занумеровано, то поддерево
с корнем £ также является занумерованным и, если в этом поддере-
ве ввести нумерацию ярусов, начиная с первого, то поддереву будет
соответствовать детерминированная функция р(Х). Эту функцию
можно определить и с помощью последовательности булевых функ-
ций следующим образом.
Пусть /1(Х(1)),/2(Х(1),Х(2)),... — последовательность буле-
вых функций, задающая детерминированную функцию f(X). Тогда
последовательность /1е(Х(1)),//(Х(1), Х(2)),... задаёт детермини-
рованную функцию /^(Х), если для любого г = 1,2,...
Два поддерева с корнями и £2 исходного дерева называются
эквивалентными, если f^(X) = f^(X).
Это отношение эквивалентности позволяет в исходном дереве
множество всех вершин, а тем самым и множество всех поддеревьев
разбить на классы эквивалентности.
Число т классов эквивалентности, на которые разбивается мно-
жество всех поддеревьев данного занумерованного дерева, называ-
ется весом дерева и, соответственно, весом детерминированной
функции.
Для занумерованных деревьев можно ввести нумерацию вершин.
Сначала перенумеруем классы эквивалентности числами 0,1,... так,
чтобы класс, в который попадает исходное дерево, имел номер 0.
Далее, взяв произвольную вершину £, определяем класс, в который
попадает дерево с корнем £, Пусть х — номер этого класса. Тогда
вершине £ приписывается номер х.
Рассмотрим дерево с занумерованными дугами и вершинами.
Возьмём произвольную ветвь; она проходит через вершины £0,£15...
£^,... Пусть этим вершинам приписаны соответственно но-
мера 0,x1,...,xt,...,xp... Допустим хг — (i j) и для всех пар
(i,j) (i j), для которых хг — х7, индекс j является наименьшим.
Произведём усечение данной ветви, сохранив её начальный отрезок
53
до вершины Производя эту операцию усечения для каждой вет-
ви, получим усечённое дерево. Для случая функции конечного веса т
на каждой ветви происходит повторение номеров вершин и индекс >,
определяющий усечение, удовлетворяет неравенству j < г. Поэтому
для этих функций усечённое дерево будет конечным.
Легко видеть, что усечённое дерево с занумерованными дугами
и вершинами позволяет полностью восстановить исходное дерево.
Детерминированная функция называется ограниченно-детер-
минированной (или о.-д. функцией), если она имеет конечный вес.
Класс всех о.-д. функций обозначим через Р0А.
В случае о.-д. функций полное (бесконечное) занумерованное
дерево можно всегда свести к конечному дереву с занумерованны-
ми дугами и вершинами. Если в этом усечённом дереве произвести
отождествление вершин с одинаковыми номерами, то получим так
называемую диаграмму переходов или, как её ещё называют, диа-
грамму Мура,
Для о.-д. функций f(X) веса т диаграмма переходов имеет г
вершин; из каждой вершины исходит N (N = 2n) дуг, дугам приписа-
ны пары (0,7'), (1,7"),..(N-1,7(N)), выделена начальная вершина.
Очевидно, по диаграмме переходов о.-д. функция восстанавливается
однозначно.
Теорема 18. Число pin, г) о. -д, функций из P0Jk, зависящих
от переменных ,..., хп и имеющих вес г, не превосходит (2г)г г.
Доказательство. Возьмём диаграмму Мура для о.-д. функ-
ции /(a?j,...,a:n) веса г. В ней из каждой вершины исходит 2П дуг,
причём г-я дуга входит в одну из г вершин и ей приписана пара (г, 7),
где 7 € {0,1}. Таким образом, р(п, г) не превосходит числа диаграмм
Мура вышеуказанного вида. Данные диаграммы могут быть получены
следующим образом.
Возьмём г вершин, занумерованных числами 0,1,...,т 1 (0 —
выделенная вершина), из каждой из которых исходит N = 2П дуг
занумерованных числами 0,1,..., N - 1. Всего имеем tN дуг. Каждая
дуга может входить в любую из г вершин и ей может быть приписано
любое из двух чисел (0 или 1). Поэтому p(n,r) < (2r)rN = (2г)гГ,
Теорема доказана.
§ 2. Способы задания о.-д. функций
Пусть f(X)=^	) — произвольная о.-д. функция. Как
уже отмечалось, областью определения этой функции является мно-
жество всех бесконечных последовательностей вида {а(1),а(2),...
...,а(£),...}, где a(t) для любого t == 1,2,... суть двоичная запись
некоторого числа из множества {0,1,...,2П - 1}. Множеством значе-
ний о.-д. функции f(X) является множество всех бесконечных по-
следовательностей вида {7(1),7(2),...,y(t),...}, где y(t)е{0,1} для
любого t = 1,2,...
Используя то обстоятельство, что о.-д. функция f(X) являет-
ся математической моделью функционирования реального дискрет-
ного пpeoбpaзoвaтeл5^ (автомата), последовательность {а(1), а(2),...
,,,,ot(t),...} будем называть входной последовательностью, а после-
довательность {7(1),7(2),...,7(2),...} — выходной последователь-
54
ностью автомата (реализующего /(X)); числа a(t) и будем
называть сигналами, поступившими в момент времени t соответст-
венно на входы и на выход рассматриваемого автомата, а вершины
диаграммы Мура для функции f(X) — состояниями автомата.
Рассмотрим диаграмму Мура для о.-д. функции /(X), реализу-
емой автоматом А. Предположим, что в момент времени t - 1 ав-
томат находился в состоянии - 1); тогда при поступлении в мо-
мент времени t на входы автомата сигнала a(t) автомат перейдёт
по дуге a(t), выходящей из вершины — 1) в диаграмме Мура, в
состояние z(i) и выдаст на выходе сигнал ^(t) (см. рис. 16). Таким
образом, величины (a(t), x(t -1)) однозначно определяют величины
(7(0,х(О).
(«(0,7(0)
x(t — 1) Рис. 16
Пусть в момент времени t переменная X(t) описывает значение
входного сигнала a(t), переменная Q(t) описывает значения состо-
яния x(t), переменная Z(t) описывает значение выходного сигна-
ла 7(t). Мы приходим к следующим уравнениям:
(Z(t)= F(X(t),Q(t-l)),
\Q(t)= G(X(t),Q(*-l)),
где Q(0) = 0.
Данные уравнения называются каноническими уравнениями.
Можно перейти от векторной записи канонических уравнений к ска-
лярной. Пусть I =] logг[ (здесь и далее через ]а[ обозначаем наимень-
шее целое число, не меньшее а); тогда
{z(t)= F'(®1(<),--,M*),«1(< - 1),---,9|(* - 1)),
9i(0 =	Qi<* - l),---,9i(i ~ О),
9<(*)= <?t(^t(t),...,^„(t),9i(t -	- 1)),
9i(0) = ... = ft(0) = 0.
Здесь F', Gi,..., Gl — булевы функции, определённые на множе-
стве 8 из г2п наборов длины n + Z, поскольку переменные ж15...,жп
пробегают значения из Е2, а вектор (двоичное число) (g15...,gj при-
нимает г значений (например, двоичные записи чисел 0,1,..., г — 1).
Доопределив функции F'> Gt на всём множестве булевых на-
боров длины п-Н, мы получим соответственно функции
из Р2, и канонические уравнения примут вид
' z(t)=	<p(xx(t),...,xn(t),qx(t -	- 1)),
91(0 = 9i(®i(0>---,z„(0,9i(* - l)>---,9i(i ~ 0),
< ... (*)
9<(0 = 9i(x\t),...,xn(t),qx(t -	- 1)),
U(0)= ... = 9,(0)-0.
Доопределение частичных (недоопределённых) булевых функ-
ций F',до (полностью определённых) булевых функций
<р, д{ ,..., gt обычно осуществляется так, чтобы правые части в послед-
ней системе (*) канонических уравнений имели наиболее простой
вид, т, е. чтобы сложность реализации булевых функций
была, по возможности, наименьшей.
Поскольку для булевых функций имеется возможность таблич-
ного представления, то и о.-д. функции допускают табличное зада-
ние с помощью так называемых таблиц переходов. Таблица перехо-
дов для о.-д. функции /(X), задаваемой каноническими уравнения-
ми (*), — это таблица 7. В левой части этой таблицы (левые п + I
столбцов) указываются всевозможные наборы значений переменных
хх(t),...,хп(t), q{(t ~ 1),...,qt(t - 1), а в правой части (правые I -h 1
столбцов) указаны соответствующие значения z(t), q{(t),...,qt(t)
булевых функций д{,..., gL.
Таблица 7
®1(О ..	•	*П<4)	gi(t-l) ..	.. 9i(i-l)	г(4)			- чМ	
0	..	,.	0	0	0		«1(0,..	.,0) ..	- «1(0,-	.,0)
1	1	1	1		«1(1,-	.,1) ..	- «1(1-	-.1)
§ 3. Схемы автоматов из функциональных
ЭЛЕМЕНТОВ И ЭЛЕМЕНТОВ ЗАДЕРЖКИ
При построении схем автоматов (или просто автоматов) пред-
полагается возможным использование функциональных элементов и
так называемых элементов задержки.
Элементом единичной задержки (или просто элементом задерж-
ки) называется автомат с одним входом и одним выходом (рис. 17),
который реализует о.-д. функцию, задаваемую системой канониче-
ских уравнений
z(t) = g(* -1),
< q(t) = x(t),
U(0)=0.
Из канонических уравнений видно, что элемент задержки представ-
ляет собой автомат с двумя состояниями, в котором сигнал, подан-
ный на вход в момент времени t, появляется на выходе в следующий
момент времени t 4-1 (t — 1,2,...).
x(t) ► z	z(t)
Рис 17
Возьмём произвольную о.-д. функцию /(X), задаваемую систе-
мой канонических уравнений (*). Построим вначале схему из функ-
бв
циональных элементов (конъюнкторов, дизъюнкторов и инверторов),
имеющую п + I входов, I 4-1 выходов и реализующую булевы функ-
- !),...,%(* - 1)),..- 1)) из пра-
вых частей системы (*). На первые п входов этой схемы пода-
ются переменные a:1(i),...,a;n(t), на последние I входов подаются
qt(t - !),...,$(* - 0 (рис. 18).
Рис. 18
Далее добавим в схему I элементов задержки	соединив
их входы с соответствующими выходами схемы S, на которых ре-
ализуется	Выходы элементов задержки, на которых
реализуются qx(t - 1 ),...,$($ - 1), соединим с соответствующими
входами схемы S. В результате и получим схему автомата А, реа-
лизующего о.-д. функцию /(X); на (внешние) входы этого автомата
подаются	на выходе получаем z(t) — значение о.-д.
функции /(X).
Глава VI
КОДИРОВАНИЕ
§ 1.	Алфавитное кодирование.
Разделимые коды. Свойство префикса
Теория кодирования представляет собой один из разделов дис-
кретной математики, в котором исследуются отображения конечных
или счётных множеств объектов произвольной природы в множества
последовательностей из чисел 0,1,..., q — 1, где q — некоторое нату-
ральное число (в частности q = 2). Такие отображения обычно назы-
вают кодированиями. Многие задачи теории кодирования сводятся
к отысканию кодирования, обладающего определёнными свойствами
57
и оптимального в некотором заранее заданном смысле. Критерий оп-
тимальности кодирования обычно связывается с минимизацией дли-
ны образов объектов, тогда как требуемые свойства кодирования мо-
гут быть достаточно разнообразными. В частности, такими свойст-
вами могут быть существование однозначного обратного отображе-
ния (декодирования), возможность исправления при декодировании
различного рода ошибок, возможность простой реализации кодиро-
вания и декодирования и т. д. Указанные задачи теории кодирования
и некоторые подходы к решению этих задач рассматриваются ниже.
Пусть задан алфавит сообщений А = {аи...,аг}, состоящий
из конечного числа букв (символов). Конечная последовательность
символов из А
а= а{ а, ... а,-
h h гп
называется словом в алфавите А, а число п — длиной слова а. Длину
слова а будем обозначать через 1(a). Пусть S — S(A) — множество
всех непустых слов в алфавите А, a S' — некоторое подмножество
множества S. Объект порождающий слова из S', называется источ-
ником сообщений, а слова из S' — сообщениями.
Пусть задан (кодирующий) алфавит В = {Ь{,..., bq}. Через b обо-
значим слово в алфавите В и через S(B)— множество всех непус-
тых слов в алфавите В.
Пусть задано отображение F, которое каждому слову а из S'(A)
однозначно ставит в соответствие слово b = F(a), b € S(B). Слово b
будем называть кодом сообщения а, а переход от слова а к его коду,
т. е. отображение F — кодированием.
Кодирование F называется взаимно однозначным, если каждый
код сообщения является кодом ровно одного сообщения.
Пусть задано отображение Е букв алфавита А в множест-
во S(B) вида
Е:
G1 —> bj,
°2 —* &2>
, аг —» Ьг
(bpb2,...,Ьг —некоторые слова в алфавите В). Указанное отобра-
жение называется схемой (кодирования). Эта схема Е определяет
алфавитное кодирование следующим образом: каждому слову а =
= а^...а{ из S' (А) — S (А) ставится в соответствие слово b =	,
называемое кодом слова а. Слова ...,Ьг называются элементар-
ными кодами. _	_
Множество {b15...,Ьг} элементарных кодов называется алфа-
витным кодом и обозначается через Е(А).
Алфавитное кодирование и соответствующий алфавитный код
называются разделимыми, если из каждого равенства
г1 Ъ гк J1 J2
(между словами кодирующего алфавита) следует, что I = к и jt = it,
t = 1,2,..., к.
58
Легко заметить, что алфавитное кодирование является взаимно
однозначным тогда и только тогда, когда оно задаётся с помощью раз-
делимого кода. Ясно также, что все слова разделимого кода различны
и непусты.
Приведём простой достаточный признак взаимной однозначно-
сти алфавитного кодирования.
Пусть слово b имеет вид
b==b'b".
Тогда слово 6'~называется началом или префиксом слова Ь, а Ь" —
концом слова Ь. При этом пустое слово А и само слово b считаются
началами и концами слова 6. Все начала и концы слова Ь, отличные
от него самого, называются собственными.
Схема Е обладает свойством префикса, если для любых i и j
(1 j < г; i / j) слово не является префиксом слова соот-
ветствующий такой схеме код называется префиксным.
Теорема 19. Если схема Е обладает свойством префик-
са, то определяемое этой схемой алфавитное кодирование будет
взаимно однозначным.
Доказательство. Поскольку схема Е обладает свойством
префикса, то все элементарные коды в ней попарно различны, т. е.
bf 0 bj при г = у. Предположим, что некоторое слово b является кодом
двух различных сообщений, т. е. допускает два разбиения на элемен-
тарные коды
3\ • Л
Пусть	= b. , 6.. / Ь. . В таком случае одно
из слов b{ , bj является префиксом другого. Получаем противоречие.
Теорема доказана.
Отметим, что условие теоремы 19 не является необходимым и
существуют разделимые коды, не обладающие свойством префикса.
Об этом свидетельствует, в частности, такой пример.
Пусть А ~ {an Og} и В — {615 Ь2}. Рассмотрим схему
Е:
I ^2 * И
Очевидно, схема Е свойством префикса не обладает. Но тем не менее
задаваемое этой схемой алфавитное кодирование является взаимно
однозначным. Декодирование (т. е. нахождение по коду сообщения
самого сообщения) осуществляется так. Код сообщения b разобьём
на элементарные коды. Отметим, что непосредственно перед каждым
вхождением буквы Ь2 в слове b находится буква Это позволяет
выделить все пары (Ь{Ь2). Оставшаяся часть слова b будет состоять
из букв Ь{. Если теперь заменить каждую пару (bxb2) на а каждую
из оставшихся букв Ь{ —на ах, то получим слово а, являющееся
прообразом слова Ь.
59
§ 2.	Неравенство Крафта-Макмиллана
Пусть задано алфавитное кодирование схемой L
S:
at
аг->6г.
Пусть алфавит А содержит q букв и Z. = 1(Ь{) — длина слова (г =
= 1,..г).
Теорема 20 (неравенство Крафта-Макмиллана). Если алфа-
витное кодирование со схемой £ обладает свойством взаимной
однозначности, то
(')
г = 1
Доказательство. Рассмотрим всевозможные слова в ал-
фавите А, имеющие длину п. Все они могут быть порождены выра-
жением
(gj + ... + аг)п,
если перемножить скобки (например, слева) без применения закона
коммутативности и рассматривать произведение а^... аг как за-
пись слова в алфавите А. Здесь, очевидно, символ будет принад-
лежать первой скобке, —второй и т. д.,	— n-й скобке. Имеем
(«1 +... + аг)п= 52 аьач
Соответствующие этим словам коды получаются, если осуществить
замену символов аг на элементарные коды Ъх,..., Ьг, используя
схему алфавитного кодирования. Получим
(Ь1 + ... + Ьг)"= £	(2)
(»1*2 •••*»)
Тождеству (2) соответствует тождество
(3)
Очевидно, что здесь членам с одинаковым знаменателем из правой
суммы соответствуют в (2) слова
дём обозначения: t = I- +... 4-I- ,
Ь,- Ь-... одинаковой длины. Вве-
‘1	*2	*п
I = шах и t) — число слов
Ь{Ь^ ...Ьг из (2), имеющих длину t t) = 0, если слов длины t
в (2) нет). Получим
nl
(4)
60
В силу взаимной однозначности алфавитного кодирования, если
т- е- а;| =4аЛ ...aJn, то \
отсюда вытекает i/(n, t) qf и, следовательно,
nf
Из последнего неравенства и соотношений (3), (4) получаем
yfnl.
Это неравенство справедливо при любом п. Поэтому оно справедли-
во и при переходе к пределу при п —> оо. Окончательно имеем
Теорема доказана.
Последнюю теорему дополняет
Теорема 21. Если натуральные числа удовлетво-
ряют неравенству (1) (неравенству Крафта-Макмиллана), то
существует алфавитное кодирование со схемой
Е':
ai ,
аг Ц,
обладающей свойством префикса и удовлетворяющей равенст-
вам	_
Доказательство. Разобьём параметры 1Х,..., 1Г на классы
так, что и lj принадлежат одному классу тогда и только тогда,
когда l{ = lj. Пусть т (1 т г) — число классов, а А1,...,Ат
и	обозначают соответственно представителей и мощности
классов. Можно считать, что
Aj < А2 < ... < Хт.
Неравенство Крафта-Макмиллана можно переписать в виде
Это неравенство порождает серию вспомогательных неравенств
1 или дА>,	1 или р2 ЯХ* ~ У\ЯХ2 \
Рассмотрим слова в алфавите В, имеющие длину ЛР Так как
ц дА‘, то можно выбрать из них ц слов длины А,. Обозначим их
через . Исключим из дальнейших рассмотрений слова, начи-
нающихся с Ь[ ... 6'. Далее, возьмём множество слов в алфавите В,
имеющих длину А2, которые не начинаются со слов Ь[,...,Ь'. Оче-
видно, что таких слов будет дАа - цдА2 "А>. Так как р2 У*2 - цдЛ2“А*,
то из этого множества можно выбрать i/2 слов — обозначим их через
ВД +1,..., 6Д + . Исключим из дальнейшего рассмотрения слова, начи-
нающиеся также и с +	6' +l/j и т. д. Используя последователь-
но вспомогательные неравенства, в итоге построим слова
(г = 22 ц)« Если их взять в качестве элементарных кодов, то полу-
i = i
чим искомую схему S'. Для Е' выполнено свойство префикса и
Теорема доказана.
Следствие 1. Неравенство Крафта-Макмиллана явля-
ется необходимым и достаточным условием существования раз-
делимого кода с длинами элементарных кодов
Следствие 2. Если существует разделимый код с задан-
ными длинами элементарных кодов, то существует и префикс-
ный код с теми же длинами элементарных кодов.
Первое следствие с очевидностью вытекает из теорем 20 и 21
(достаточно лишь вспомнить, что префиксный код — это раздели-
мый код). Для доказательства второго следует применить сначала
теорему 20, а затем теорему 21.
§ 3.	Коды С МИНИМАЛЬНОЙ ИЗБЫТОЧНОСТЬЮ.
Оптимальное кодирование Хаффмена
Предположим, что задан алфавит А = {аи..., аг} (г > 2) и набор
положительных вероятностей ри...,рг (52р< = 1) появлений симво-
1 = 1
лов а15...,аг в сообщениях (предполагается, что символы ап...,аг
появляются в сообщениях независимо). Пусть далее задан алфавит
В = {b^..4bq} (q > 2). Тогда можно построить целый ряд схем Е
алфавитного кодирования
обладающих свойством взаимной однозначности. В частности, все-
гда можно взять в качестве элементарных кодов ^,...,дг различные
слова в алфавите В одинаковой длины Z, где I =] logfl г[.
62
Для каждой схемы Е можно ввести среднюю длину Zcp, опре-
деляемую как математическое ожидание длины элементарного кода,
т. е.
*СР = I^uw.
Очевидно, что величина Zcp (Zcp 1) показывает, во сколько раз уве-
личивается средняя длина слова при кодировании со схемой Е.
Пусть
Г-infZ^,
где нижняя грань берётся по всем схемам Е, обеспечивающим свой-
ство взаимной однозначности. Легко заметить, что
1 5U’«J]10g,r[
(верхнюю оценку даёт, например, упомянутое выше кодирование).
Отсюда следует, что при построении кодов, у которых величина Zcp
близка к Г, можно не рассматривать коды с Zcp большим, чем ]logg т[.
Значит, для таких схем
Pili С]log,г[.
Положим р* = min pf. Поскольку р{ > 0 (г = 1,..г), то р* > 0 и
1 i < г
I < i1Qggrl
i р*
для всех г. Значит, имеется конечное число возможных значений Zcp,
для которых Г /ср ] logg г[. Следовательно, величина Г достигается
на некотором Е и может быть определена как
Г = min/E.
Е ср
Коды, определяемые схемой Е с Zcp = Г, называются кодами
с минимальной избыточностью или оптимальными кодами Хафф-
мена,
Очевидно, что коды с минимальной избыточностью дают в сред-
нем минимальное увеличение длины слов при соответствующем ко-
дировании. Ввиду этого представляет интерес задача о построении
кодов с минимальной избыточностью. Ниже эта задача решается для
двоичного кодирования, когда кодирующий алфавит В содержит два
символа (скажем, 0 или 1); похожим способом задача решается и
в общем случае (когда В = {Ьи..., bq}, 3).
В силу следствия 2 (к последним двум теоремам) существует ал-
фавитное кодирование со свойством префикса, дающее коды с мини-
мальной избыточностью. Поэтому при построении кодов с минималь-
ной избыточностью можно ограничиться рассмотрением префиксных
кодов.
Префиксный код удобно задавать с помощью занумерованного
ориентированного дерева с корнем, в котором из каждой вершины
б'?
выходит не более двух дуг и в каждую вершину, кроме корня, вхо-
дит по одной дуге (в корень не входит ни одна дуга). Каждой дуге
дерева приписывается 0 или 1; дугам, выходящим из одной вершины,
приписываются разные символы (0 и 1). Такие деревья будем назы-
вать кодовыми. Каждой вершине v кодового дерева соответствует
единственный путь Р(у), ведущий в неё из корня дерева; вершине v
сопоставляется слово из символов, приписанных дугам, составляю-
щим путь P(v). Нетрудно заметить, что если двум вершинам и, и v2
приписаны двоичные слова (наборы) b и Ь' и слово b является пре-
фиксом слова 6', то путь из корня дерева в вершину v2 проходит
через Отсюда следует, что слова, приписанные концевым вер-
шинам кодового дерева, образуют префиксный код (на рис. 19а это
код 00, 01, 101, 1110, 1111) и, наоборот, всякому префиксному ко-
ду соответствует множество концевых вершин некоторого кодового
дерева.
Рис. 19
Предположим, что из некоторой вершины кодового дерева D вы-
ходит ровно одна дуга. Если начало и конец этой дуги отождествим,
а саму дугу удалим, то, очевидно, получим кодовое дерево D', кото-
рое также как и исходное дерево D задаёт префиксный код (с преж-
ним алфавитом сообщений Л), но в этом коде некоторые элементар-
ные коды окажутся короче соответствующих элементарных кодов,
определяемых исходным деревом D. Указанный переход от дерева D
к дереву D’ назовём операцией усечения; если, например, дважды
применить операцию усечения к дереву на рис. 19,а, то получим ко-
довое дерево, изображённое на рис. 19,6.
Укажем некоторые свойства оптимальных префиксных кодов.
Будем считать, что символы apOg,...,^ алфавита сообщений А за-
нумерованы в порядке убывания вероятностей их появления, т, е.
Свойство 1. В оптимальном коде длины 1г элементарных
кодов Ь. не убывают, т. е.
64
Действительно, если это не так и для некоторых i и j одновре-
менно > р. и то возьмём схему кодирования S', в которой
символу соответствует элементарный код bjt а символу а - —эле-
ментарный код (т. е. в исходной схеме кодирования S поменя-
ем местами элементарные коды 6- и Ь.). В результате получим код
с меньшей величиной Zcp, ибо
Pi If + Pi I, = p. Ij + Pj I, + {pi~pj№-l1)>pili + Pj li •
Но это противоречит предположению об оптимальности исходного
кода. Свойство 1 установлено.
Свойство 2. Существует оптимальный код, в кото-
ром двум наименее вероятным символам аг { и аг соответству-
ют элементарные коды одинаковой длины, различающиеся лишь
в последнем разряде.
Рассмотрим произвольный оптимальный префиксный код и соот-
ветствующее ему кодовое дерево. Пусть Ь — вершина дерева, пред-
шествующая концевой вершине (элементарному коду) Ьг (рис. 20).
Если из Ь выходит лишь одна дуга (входящая в Ьг), то к кодовому
дереву (и к коду) можно применить операцию усечения, в результате
чего дуга будет удалена, а вершина Ьг отождествлена с Ъ. Поскольку
операция усечения уменьшает Zcp, это противоречит оптимальности
исходного кода. Значит, из вершины Ь выходят две дуги, и сущест-
вует элементарный код 6., имеющий ту же длину 1Г, что и Ьг. От-
сюда и из того, что по свойству 1 I. 1Г _, < lr вытекает равенство
I. = 1г ! = 1г. Если i г - 1, то в исходной схеме кодирования по-
меняем местами элементарные коды Ь{ и Ьг _,. В итоге получим код,
который также как и исходный будет оптимальным, а кроме того, он
будет обладать нужным свойством.
Положим теперь (как и выше), что источник сообщений S выда-
ёт сообщения в алфавите А = аг} и для вероятностей р{,..рг
появления символов аи...,аг в сообщениях справедливо соотноше-
ние
Рассмотрим источник S', полученный из S отождествлением («скле-
иванием») символов аг _! и аг. Он выдаёт символы ап...,аг_2 с преж-
ними вероятностями	-2> а новый символ а? («склеенный»)—
6'5
с вероятностью pf = pr„i +рг. Такой источник S' будем называть
редуцированным. Предположим, что для редуцированного источ-
ника имеется некоторый код {bj, 4^,.. ЬгнемУ построим
код для исходного источника 3 следующим образом. Для символов
аи...,аг.2 сохраним прежние коды Ь|,...,ЬГ„2, а в качестве Ьг_} и Ъг
возьмём соответственно слова Ь'О и Ь'1. Очевидно, что если код для
редуцированного источника S' — префиксный, то и построенный код
для исходного источника — тоже префиксный.
Теорема 22 (о редукции). Если префиксный код
...,6Г_2,6'} для редуцированного источника 8' является опти-
мальным, то и префиксный код {b^b2,...,br^2ibtQ1b,l} для исход-
ного источника 8, построенный указанным способом, также яв-
ляется оптимальным.
Доказательство. Обозначим через /ср и Zcp соответственно
среднюю длину кода для редуцированного источника S’ и кода для
исходного источника S. По построению 1Г_{ = 1Г = Г + 1, где Г —
длина элементарного кода Ь', и р' = pr„i 4-рг, поэтому
= Ерл + Рг-А1' +1) + Рг(1' +1) =
1 = 1	»= 1
г-2
= 52	+	+ - 1 + Рг = 4р + Рг - 1 + Рг- (*)
1 = 1
Если код для источника 8 не является оптимальным, то возьмём
оптимальный код, обладающий свойством 2, и построим по нему код
для редуцированного источника S’, сопоставив символу d верши-
ну Ь', предшествующую вершинам Ьг_{ и Ьг, и сохранив для осталь-
ных символов а1,...,аг„2 те же элементарные коды d1)...,fer_2, что
и в оптимальном коде для S. Средние длины Zcp и 1^ для новых кодов
удовлетворяют (*) и поскольку новая величина Zcp (для оптимально-
го кода) меньше соответствующей прежней, то и новая величина Zcp
будет меньше прежней. А это противоречит оптимальности кода для
исходного редуцированного источника. Теорема доказана.
Теорема 22 даёт алгоритм построения оптимальных кодов.
В этом алгоритме сначала производится свёртывание искомого ко-
да в соответствии с правилами перехода от источника 8 к редуци-
рованному источнику S'. В процессе свёртывания один за другим
получаются всё более простые (короткие) коды и в конце концов —
код из однобуквенных элементарных кодов. Фактически это означает
преобразование набора вероятностей до тех пор, пока не получится
набор вероятностей (из двух чисел), для которого оптимальный код
находится тривиально. После этого найденный код развёртывается
в соответствии с теоремой о редукции в последовательность опти-
мальных кодов, которая заканчивается искомым кодом.
Пример построения оптимального кода в случае г — 6 и набора
вероятностей Р ~ (0,4;0,25;0,15,-О,1;0,05;0,05) представлен в таб-
лице 8.
66
Таблица 8
А	Р	Р1	р"	рШ	pZV	е"	Ezn	E"	s'	E
а1	0,4	0,4	0,4	0.4	/0,6		1	1	1	1
	0,25	0,25	0,25	Л, 35)	/0,4		r°°\	01	01	01
«3	0,15	0,15	/0,2 \	/0,25/			\01\	/000\	001	001
	0,1	0,1V	'0,15/					\ooi\	/0000	0000
*5	0,051	х0,М							LOOOlx^	Г 00010
°6	0,05/									L00011
§ 4. Самокорректирующиеся коды. Коды Хэмминга
Самокорректирующиеся коды ниже рассматриваются для неко-
торого частного случая (равномерного) кодирования.
Пусть А = {0,1} — алфавит сообщений, содержащий два симво-
ла. Пусть далее {Si,...,аа} — множество всех слов S= ... ат
в алфавите А, имеющих фиксированную длину т (а = 2т).
Предположим, что в канале связи, по которому передаются сло-
ва (сообщения), действует источник помех, который может вызывать
ошибки не более чем в р символах одного слова (сообщения). Это
значит, что двоичная последовательность, полученная на выходе ка-
нала связи, отличается от двоичной последовательности, поступив-
шей на вход этого канала, не более чем в р позициях. Ясно, что если
передавать исходное сообщение а1.. ,ат (без предварительного коди-
рования), то на выходе канала связи невозможно будет установить,
какое сообщение фактически было передано. В связи с этим возника-
ет вопрос, нельзя ли осуществить кодирование слов а из множества
{Si,...,а,}, т. е. слов вида ...ат, словами Д ... длины п так,
чтобы по коду /?/...полученному на выходе канала при передаче
кода . fln можно было однозначно восстановить этот код и, зна-
чит, исходное сообщение а1...ат? Коды, обладающие данными свой-
ствами, называют самокорректирующимися кодами относительно
рассматриваемого источника помех или кодами, исправляющими р
ошибок.
Рассмотрим коды, исправляющие одну ошибку. Будем считать,
что кодовые слова имеют длину п, т. е. представляют собой двоичные
наборы (векторы), содержащие п разрядов (компонент).
Найдём натуральное число к такое, что
2k~l^n<2k;
нетрудно заметить, что к ~ [logn]+1 =]log(n+1)[. Для произвольно-
го i из множества {0,1,...,2* - 1} через ё^Л)(г) обозначим двоичный
набор	длины к, удовлетворяющий условию
к
j --1
т. е. являющийся двоичной записью числа i с помощью к, цифр (на-
пример, е<в)(35) —(100011), е<8)(35) = (00100011)). Сложение чисел
67
no mod 2 будем обозначать знаками Фи£. Пусть Вп —множество
всех двоичных слов (наборов) длины п в алфавите {0,1}. Суммой
наборов а — (а,,..ап) и /3 — (Д,../Зп) из Вп будем считать набор
(«1 Ф Д, а2 © Р2,..ап ф Дг); для обозначения операции сложения
наборов также будем использовать знаки ф и Умножение произ-
вольного набора b = (//?l,...,^n) из Вп на элемент а из {0,1} введём
следующим образом: ар ~ (аД, аД,,..., арп).
На множестве Вп определим вектор-функцию h(p), полагая для
произвольного набора в — (Д , р^.. .,/?„) е В п
(1)
1 = 1
Очевидно, что h(p)— это двоичный набор длины k, полученный
в результате сложения наборов, являющихся двоичными записями
(с помощью к цифр) номеров единичных разрядов набора р. Рас-
смотрим код Нп, состоящий из всех наборов Р = (р19Р2,...,рп)е Вп
таких, что	_
h(P)^ (ОД^);	(2)
к
этот код называется кодом Хэмминга.
Призер. Положим п = 6, Д = (110011) и 7 = (110001). Тогда
Л: =3, Л(Д) = (0,0,1)ф(0,1,0)ф(1,0,1)ф(1,1,0) = (0,0,0) и £(7) =
= (0,0,1) ф (0,1,0) ф (1,1,0) = (1,0,1). Следовательно, ре у $ Н6.
Теорема 23. Код Хэмминга исправляет одну ошибку.
Доказательство. Для произвольного двоичного набора
а = (а15а2,...,ак) через N(a) обозначим число, двоичной записью
которого является набор а, т. е. положим
к
ЛГ(а) = ^2а.2*->;
1 = 1
jV(a) будем считать числовым значением набора а. Рассмотрим од-
нозначное отображение (декодирование), при котором каждому набо-
ру р е Вп ставится в соответствие набор р, если Р еНп, или набор,
полученный из р заменой разряда с номером N(h(P)) на противо-
положный, если р $Нп. Убедимся, что если в произвольном кодовом
наборе произойдёт любая одна ошибка, то эта ошибка будет исправ-
лена при указанном декодировании.
Действительно, пусть в некотором наборе Р = (Д, Д2,..., Рп) е Нп
произошла ошибка в j-м разряде, в результате чего получился набор
/? = (^,^,...,Д;_ и(Д.ф1),Ду + 1,...,О Так как то
h(pf)~ У P^k}(i) Ф ~
i -=1
- h(P) Ф е**>(У) = (0,.. .,0) ф е^(У) =
68
Произведя в наборе /?' замену разряда с номером 7У(А(/?')) ==
—	— У, получим исходный набор /3. Теорема доказана.
Пример. Пусть в наборе /3 ~(110011) е Нб произошла ошиб-
ка в пятом разряде, в результате чего получился набор /3' —(110001).
Так как h(/3') = (0,0,1) ф (0,1,0) ф (1,1,0) = (1,0,1), то числовое зна-
чение набора h((3l) равняется 5, и это значение определяет номер
искажённого разряда.
Из определения вектор-функции А(3) (соотношения (1)) вытека-
ет, что у-й разряд hj(f3) набора =	есть сумма
по mod 2 тех и только тех разрядов набора /3, двоичная запись (с по-
мощью к цифр) номеров которых содержит 1 в у-м разряде. Усло-
вие принадлежности набора /3 коду Хэмминга Нп (соотношение (2))
можно записать в виде
( ММ
< ...	(3)
1МЗ) = 0.
Двоичная запись с помощью к цифр числа 2k~j (j = 1,2,...,к),
т. е. набор etfc)(2*“J) содержит, очевидно, ровно одну единицу в у-м
разряде, поэтому разряд (3#входит лишь в у-е уравнение из (3).
Прибавив (по mod2) к обеим частям равенства Ау(/3)=0 разряд
получим эквивалентное ему соотношение Д^.(/3) — n где h'5(J3) по-
лучается из Лу(/3) путём удаления слагаемого Условие (3) мож-
но переписать в виде
(Л{(Д) = ^*-н
< ...	(4)
I =
Суммы Л^/?),...,h'k(/3) содержат лишь те разряды набора /?,
номера которых отличны от степеней двойки; эти разряды назовём
информационными. Из (4) видно, что информационные п - к раз-
рядов можно взять произвольными, и тогда остальные к разрядов
/З^о,/3^1,...,/^*-, однозначно определяются из условия (4); разряды
/3£о,	назовём контрольными. Из сказанного вытекает сле-
дующее утверждение.
Теорема 24. Код Хэмминга Нп содержит 2пк кодовых
наборов, где к =]log(n + 1)[.
§ б. Геометрические свойства кодов Хэмминга. Оценки
числа кодовых слов в коде, исправляющем р ошибок
Будем рассматривать единичный n-мерный куб Вп как метри-
ческое пространство, где для любых двух двоичных наборов (точек)
/3 — (Д,...,/Зп) и 7 — (?1,..., 7П) расстояние р(/3, 7) между ними равно
числу разрядов, в которых они различаются, т. е.
69
р(Д',т)=£^-г1-
* = I
Пусть /3 —некоторый набор из Вп. Множество наборов (3* та-
ких, что р(Р./3') < р, называется шаром радиуса р с центром в /3»
Теорема 25. Множество двоичных наборов из В п со-
ставляет код. исправляющий р ошибок, в том и только в том
случае, когда расстояние между любыми двумя наборами этого
множества не меньше чем 2р 4-1.
Доказательство. Если условие теоремы выполнено и при
передаче кодового набора (3 по каналу связи произошло р' < р оши-
бок, то принятый набор (З1 будет отстоять от любого другого кодового
набора 7 не менее чем на 2р41 ~р' > р, и переданный набор /3 опре-
деляется однозначно.	~
Если же расстояние между некоторыми кодовыми наборами /3
и 7 не превосходит 2р, то найдётся набор 6, отстоящий от /3 и от 7
не более чем на р. При получении набора 6, очевидно, нельзя од-
нозначно установить, из какого набора (/3 или 7) он произошёл при
имевших место не более чем р ошибках. Теорема доказана.
Из этой теоремы и теоремы 23 вытекает
Следствие. Расстояние между любыми двумя различны-
ми кодовыми наборами из Нп не меньше трёх.
Последняя теорема допускает следующую геометрическую ин-
терпретацию.
Около каждого кодового набора опишем шар радиуса р. Все на-
боры, которые могут получиться из кодового набора /3 в результате
не более чем р ошибок, содержатся в шаре с центром в /3. Если
расстояние между кодовыми наборами не меньше 2р + 1, то шары
не пересекаются, и по искажённому набору соответствующий кодо-
вый набор (центр шара) восстанавливается однозначно. Если рас-
стояние между какими-либо кодовыми наборами не превосходит 2р,
то соответствующие этим наборам шары пересекаются и по наборам
из пересечения центры шаров однозначно указать нельзя.
Подобные рассуждения позволяют достаточно просто получить
оценки для числа кодовых наборов в самокорректирующихся кодах.
Пусть К* — произвольный самокорректирующийся код, исправ-
ляющий р ошибок и представляющий собой некоторое множество
наборов из Вп. Из теоремы 25 следует, что шары радиуса р, описан-
ные около кодовых наборов из АГрп, не пересекаются. Каждый такой
шар содержит 14- п 4- С* •+ ... 4- С* наборов (отличающихся от центра
не более чем в р разрядах), откуда следует
|к;|(1 + п + с* +... + с₽) < 2"
или
пп
1^*1^ i 4-п	’’..4 С'’
70
последняя оценка носит название верхней границы Хэмминга.
Код Кр называется максимальным, если он содержит наиболь-
шее число кодовых наборов (при заданных п и р).
Пусть К*тм — произвольный максимальный код из п-разрядных
наборов, исправляющий р ошибок. Найдём нижнюю оценку мощно-
сти этого кода.
Построим код, исправляющий р ошибок, следующим образом.
В качестве первого кодового набора возьмём произвольный п-раз-
рядный двоичный набор Затем к /Зг добавим какой-нибудь на-
бор fa, лежащий вне шара радиуса 2р с центром в На третьем
шаге в код включим набор /?3, не принадлежащий шарам радиуса 2р,
описанным около $ и Д, и т. д. Построение завершается, когда по-
сле очередного /-го шага не останется наборов вне шаров радиуса 2р
с центрами в $, /3^,... Расстояние между любыми двумя наборами
из множества	по построению не менее 2р+ I и поэтому
построенный код согласно теореме 25 исправляет р ошибок.
Каждый шар радиуса 2р содержит 1 + п + С* +... + С*р наборов.
Шары с центрами в Д содержат все 2п наборов из Вп, поэтому
Ц1 + п + С2 + ... + С2р)>2п
(в случае противоположного неравенства Z (1 + n -h С2 + ... + С2р) <
< 2п существовал бы набор, лежащий вне рассматриваемых шаров
с центрами в	откуда получаем
1	1 + п + С2 + ... + С2р ’
Учитывая, что мощность максимального кода К£тп не меньше мощ-
ности I построенного кода, получаем оценку
I I >
1 ЛП“| 1 + п+ С* +... + C*'’
которая носит название нижней границы Гильберта.
Из теоремы 24 и верхней границы Хэмминга вытекает
Следствие. При п = 2* - 1, где t ~целое число, код Хэм-
минга является максимальным.
Действительно, в этом случае k =]log(n+ 1)[= t и согласно те-
ореме 24 в Нп входят 2П"* кодовых наборов. С другой стороны, со-
гласно верхней границе Хэмминга имеем
да =2-.
т. е. множество наборов Нп имеет максимальную мощность.
7/
Глава VII
ДИСКРЕТНЫЕ ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ
§ I. Задача на покрытие. Точное
РЕШЕНИЕ ЗАДАЧИ НА ПОКРЫТИЕ
Характерной особенностью дискретных экстремальных задач,
как правило, бывает проявляющаяся в том или ином виде «дис-
кретность» решений таких задач. Скажем, в задачах синтеза схем
из функциональных элементов дискретность проявляется, например,
в том, что любая схема содержит целое число элементов; в задачах
поиска кратчайших путей на графах дискретность можно усмотреть
в том, что всякое ребро графа либо входит в некоторый путь, либо не
входит в него, и т. д. Экстремальность рассматриваемых задач обыч-
но заключается в экстремальности искомых решений: ищут схему,
реализующую заданную булеву функцию и содержащую при этом
наименьшее возможное число функциональных элементов; выбира-
ют путь, соединяющий две заданные вершины графа и имеющий наи-
меньшую возможную длину; в заданной сети строят целочисленный
поток наибольшей величины и т. д.
При решении дискретных экстремальных задач обычно бывает
нетрудно построить некоторые достаточно простые (в содержатель-
ном смысле) алгоритмы переборного характера для нахождения нуж-
ного решения; однако такие алгоритмы фактически непригодны для
практического использования из-за неприемлемо большой трудоём-
кости поиска требуемых решений. Гораздо труднее подыскать под-
ходящие алгоритмы, использующие относительно небольшое или хо-
тя бы даже просто приемлемое число элементарных операций. Соб-
ственно это обстоятельство и объясняет тот факт, что лишь для от-
носительно небольшого числа дискретных экстремальных задач из-
вестны подходящие для практического использования алгоритмы по-
иска точных решений. В связи с этим для многих содержательных
и важных в прикладном отношении задач ограничиваются поиском
приближённых (в том или ином смысле) решений; при этом большую
актуальность приобретает и проблема оценки качества получаемых
решений. Сказанное проиллюстрируем ниже на конкретных приме-
рах и первой рассмотрим задачу на покрытие.
Покрытием множества А ==	,..., ат} называется любая систе-
ма (Аи А2,..., Ап) подмножеств множества А, объединение которых
равно А; подмножества At,...,An считаются при этом элементами
покрытия (А1,...,АП), Покрытие считается тупиковым, если при
удалении из него любого одного элемента оно перестаёт быть покры-
тием.
При заданной системе подмножеств (А1,..., Ап) задача нахожде-
ния минимального покрытия (или просто, как говорят, задача на по-
крытие) заключается в нахождении покрытия, являющегося частью
заданного покрытия (Aj,..., Ап), содержащей наименьшее число эле-
ментов покрытия (т. е. подмножеств из числа Ап..., Ап).
Покрытие можно представить булевой матрицей (таблицей)
||а..||. Строки этой матрицы соответствуют элементам	мно-
72
жества А, а столбцы — элементам покрытия Аи..., Ап, Элемент
(i =	j — 1,...,п) данной матрицы равен 1 в том и только
в том случае, когда г-й элемент множества А входит в j-е подмно-
жество А„, т. е.
{1, если at е A
О, еслиа^А};
если = 1, то считаем, что j-й столбец покрывает г-ю строку. Вся-
кую задачу на покрытие, очевидно, можно свести к задаче на покры-
тие булевой матрицы, заключающейся в том, чтобы для заданной
матрицы найти наименьшее число столбцов этой матрицы, в сово-
купности покрывающих все строки матрицы.
Один из способов решения задачи на покрытие заключается
в следующем. Сопоставим г-й строке матрицы ||а0|| (i = l,...,m)
дизъюнкцию
V V ... V
которая в качестве слагаемых ipАу(.г(0) включает сим-
волы (имена) всех столбцов заданной матрицы, покрывающих г-ю
строку (символы Ар..., Ап в данном случае рассматриваем как сим-
волы булевых переменных). Составим затем конъюнкцию всех дизъ-
юнкций Д (г = 1,..., га):
&	V	V ... V ^j(i,r(,)))-
» — 1
В полученном выражении («произведении сумм») раскроем скобки
(используя дистрибутивный закон) и проведём упрощения с исполь-
зованием законов коммутативности, ассоциативности, идемпотент-
ности (АуАу = Ау) и поглощения (В V ВС = В). В итоге придём
к дизъюнкции конъюнкций («сумме произведений»), в которой
а)	каждая конъюнкция содержит попарно различные символы;
б)	ни одна из конъюнкций не входит (в качестве сомножителя)
в другую конъюнкцию. Конъюнкции полученного в итоге выражения,
как нетрудно заметить, определяют все тупиковые покрытия исход-
ной матрицы, а содержащая наименьшее число символов (столбцов)
конъюнкция и даёт решение задачи — указанные в этой конъюнкции
столбцы матрицы составляют минимальное покрытие.
Однако указанный способ нахождения минимального покрытия
уже при относительно небольших размерах рассматриваемых матриц
(скажем, 102 строк и столько же столбцов) требует выполнения весь-
ма большого числа элементарных операций и потому для решения
прикладных задач фактически непригоден.
§ 2.	Градиентный алгоритм поиска приближённого
РЕШЕНИЯ ЗАДАЧИ НА ПОКРЫТИЕ. ОЦЕНКА
сложности градиентного покрытия. Отклонение
ГРАДИЕНТНОГО ПОКРЫТИЯ ОТ МИНИМАЛЬНОЙ)
Для приближённого решения задачи на покрытие известен про-
стой эвристический метод, который носит название градиентного
алгоритма (другие названия этого же метода: жадный алгоритм;
метод наискорейшего спуска; метод вычерпывания). Метод за-
ключается в пошаговом отборе в покрытие таких столбцов таблицы,
каждый из которых вносит (на соответствующем шаге) наибольший
вклад в покрытие остающихся строк.
Более точно этот алгоритм применительно к некоторой заданной
булевой матрице М можно представить так.
Г. Возьмём в качестве R исходную матрицу М, а в качест-
ве Р — пустое множество.
2°. В R выберем столбец SR, покрывающий наибольшее число
строк и отнесём выбранный столбец к Р (если указанных столб-
цов SR несколько, то выбираем из них столбец с наименьшим номе-
ром).
3°. Вычеркнем из матрицы R все строки, покрытые столбцом SR.
Если все строки матрицы R оказались вычеркнутыми (покрытыми),
то процедура построения на этом заканчивается и в качестве по-
крытия берётся полуденное множество Р. Если R содержит ещё
какие-то строки (непокрытые), то возвращаемся к пункту 2°.
Проанализируем полученное с помощью градиентного алгоритма
приближённое решение задачи на покрытие.
Под градиентным покрытием матрицы М будем далее подразу-
мевать покрытие данной матрицы, полученное с помощью градиент-
ного алгоритма. Под сложностью покрытия будем подразумевать
число столбцов в этом покрытии.
Пусть М — произвольная булева матрица с т строками и п
столбцами, содержащая в каждой строке и в каждом столбце не ме-
нее чем по одной единице. Обозначим через Zmin сложность мини-
мального покрытия этой матрицы, а через — сложность её гради-
ентного покрытия.
Пусть	—некоторое минимальное покрытие матри-
цы М, А{1) — множество покрытых после I шагов строк при при-
менении градиентного алгоритма, В(1)— множество строк, остав-
шихся после Гго шага градиентного алгоритма непокрытыми. Ниже
будем считать 2 (при Zmia = 1 имеем тривиальный случай, ко-
гда минимальное покрытие состоит из одного столбца и находится
с помощью градиентного алгоритма за один шаг).
Лемма 8. |Л(/)| >	(1 - >4-) .
i=0
Доказательство проведём индукцией по I. При I = 1,
очевидно, |Л(2)| >
ТП1П
Предположим, что неравенство леммы верно для номеров шагов
1,2,..., Z - 1; докажем его для Z-ro шага. Если |Л(/)| = т, то лем-
00
ма доказана (формально: $2 (1 ~ р-) ~ Ln)- В противном случае
».=о rnm
ещё не все столбцы 5И..., 5^ вошли в градиентное покрытие Р. Те
из них, что ещё не вошли в градиентное покрытие Р, покрывают
множество B(l -1). По крайней мере один из столбцов
(не вошедших в Р) покрывает не менее Д—й доли В(1 - 1), т. е. не
‘mm
т — |Д(/ -1)	п
менее-----у-'---- строк. Поэтому
*11110
74
|Л(О1 >\А(1- 1)1 +	= л + (1 - л)|Л(1 -
‘min	niin \ rnin /
I - I
> (по предположению индукции) /у" +	“ (~
г-0
Лемма доказана.
Следствие. |В(/)| < т (1 ” г~ ) •
Обозначим через Г минимальное натуральное число такое, что
|5(П1 < U-
Лемма 9. 1Гк Г 4- lmin.
Доказательство. На каждом шаге градиентного алгорит-
ма покрывается по крайней мере одна новая строка. Поэтому, если
|В(О1 Ln» то Д° получения покрытия осталось сделать не более Zmtn
шагов; отсюда и получается оценка леммы.
Теорема 26 (о сложности градиентного покрытия).
0+i]in(J/(L”ln-D) D •
Доказательство. Оценим сверху Г. Решим относитель-
но I вспомогательное уравнение т (1 - -г-) ~ Zmin; если решение
этого уравнения обозначим через L, то для L получаем выражение
г в __»n<foW„ _
HU/(U - !))•
Поскольку ]L L, а
< 1, то
L.)	_/т1п.
Отсюда и из следствия к лемме 8 получаем
KI
< U>

т. е.
7» < 1 г г_1__ln(m/^niiii) Г
4 ]1п(/гашЛй, -!))[•
Отсюда и из леммы 9 получаем
Ln
__I»WU) Г . I
ЧЛг‘))1.
, J1 —
+ U I in(U/(Un - 0)
Теорема доказана,
75
Для отношения -г^ — отклонения градиентного покрытия от ми-
*min
нимального получаем оценку
k < । + -А_] ln(m/U Г
Cun Cun J MCimACun — О) I
Более грубые оценки можно получить, если использовать разло-
2 у3 4
жение ln(lH-z)~z~-2-4-y-при |г| < 1. Из этого разложения
следует, что In (1 - Д-) < -Д-, а
\ тип / mm
in т-^5т ~ I*1 —= - 1п (1 -	> -г~-
тшп 1	1 — т—	\ ‘min / Sum
‘miu
Используя последнее неравенство и оценку теоремы 26, получаем
для сложности градиентного покрытия оценку
= Ц1п(7п/1гаю)+1+г£),
а для отклонения
>С1п(7п//ш1п)+1+Л.
•min	тип
Полученные оценки достаточно хороши; об этом свидетельству-
ет следующий пример.
Пусть MQ есть матрица размером 2к х kt состоящая из всевоз-
можных двоичных наборов длины к; пусть далее М* — матрица раз-
мера 2* х 3, в которой г-й столбец состоит из единиц, два осталь-
ных— из нулей (г = 1,2,3). Рассмотрим матрицу М, составленную
из подматриц Мо, М2, М3:
м.	м
М2	н
м3	н
В этой матрице т ~ 3 • 2к строк и п к 4- 3 столбцов. Отметим,
что первые три столбца содержат по 2к единиц, а все остальные —
по 3 • 2к “1 единиц. Градиентный алгоритм на первых к шагах первые
три столбца не выберет; его применение, очевидно, приведёт к три-
виальному покрытию, содержащему все к 4-3 столбцов, т. е. в данном
примере /ГА — к 4- 3.
В то же время минимальное покрытие образуют первые три
столбца, т. е. Zmin - 3. Отсюда получаем
76
что по порядку равно правой части из оценки для отклонения:
^^ln(m/U)+U г—
•min	‘min
=•	+ 1 + I = fcln2 +
u	u	u
Таким образом, полученную выше оценку сложности покрытия
градиентным алгоритмом в общем случае существенно улучшить не-
льзя.
§ 3. Задача о минимальном остовном дереве
Приведём теперь примеры дискретных экстремальных задач, для
которых известны эффективные, т. е. вполне доступные по числу вы-
полняемых элементарных операций алгоритмы. Первой рассмотрим
задачу о поиске минимального остовного дерева.
Пусть G — неориентированный связный граф. Остовным дере-
вом или остовом графа G называется всякий связный подграф гра-
фа G, являющийся деревом и содержащий все вершины графа G.
Остов графа, очевидно, можно получить путём последовательного
удаления циклических рёбер графа, что делается достаточно про-
сто. Ниже рассматривается более сложная задача — поиск остова
во взвешенном графе, которая может иметь в ряде случаев содержа-
тельную интерпретацию.
Граф G называется взвешенным, если каждому ребру е этого
графа приписано неотрицательное число с(е) — вес ребра (разным
рёбрам, естественно, могут быть приписаны разные веса).
Рассмотрим задачу нахождения во взвешенном графе остовного
дерева с минимальным общим весом рёбер, т. е. дерева, у которого
сумма весов всех его рёбер минимальна; такое дерево называется ми-
нимальным остовным деревом (или минимальным остовом). Укажем
два алгоритма поиска минимального остовного дерева для связного
взвешенного графа G с п вершинами.
Первый алгоритм (жадный). На первом шаге выбираем реб-
ро с наименьшим весом и включаем его в искомое дерево (вместе
с инцидентными ему вершинами). На каждом следующем очередном
шаге выбираем новое ребро с наименьшим весом, не образующее цик-
лов с уже выбранными рёбрами. Этот процесс продолжается до тех
пор, пока не будет выбрано п -1 рёбер, образующих (в соответствии
с одним из характеристических свойств дерева) остовное дерево. По-
добный алгоритм называется градиентным (или жадным). Очевидно,
указанный алгоритм требует конечного числа шагов. Докажем, что
полученное с его помощью остовное дерево является минимальным.
Пусть с использованием градиентного алгоритма получено
остовное дерево D; предположим, что D не является минималь-
ным. Пусть градиентный алгоритм включает в D рёбра е11е2,..чеп_1
так, что эти рёбра идут в порядке неубывания их весов. Возьмём
минимальное остовное дерево 29П11П, которое включает в себя рёбра
77
еи е3,..е; j для наибольшего возможного i. Очевидно, з > 1, а с дру-
гой стороны i < п - 1, т. к. D не является минимальным остовным
деревом. При добавлении ребра et. к дереву Dmin появляется про-
стой цикл Z, причём единственный, ибо любые две вершины (в том
числе и инцидентные добавленному ребру е() в дереве Dmln соедине-
ны единственной простой цепью — иначе уже в дереве Dmin был бы
цикл. Этот цикл Z должен включать некоторое ребро е отличное
от et, • ..> поскольку	в дереве D цикла не образуют. По-
скольку	принадлежат дереву Pmin, в котором нет цик-
лов, и поскольку градиентный алгоритм на каждом шаге добавляет
ребро наименьшей стоимости, которое не образует циклов, то вес е
должен быть не меньше веса ei (иначе к	вместо бы-
ло бы добавлено ребро е). Если вес е больше, чем вес в(, то остовное
дерево P^in, получающееся из Pmin изъятием ребра е и добавлени-
ем было бы остовным деревом с меньшим весом, чем у Dmln —-
получаем противоречие. Получается, что веса е и должны быть
равны, в связи с чем D^n будет минимальным остовным деревом. Но
это противоречит нашему предположению о том, что г — наиболь-
шее из возможных. Поэтому дерево D (построенное градиентным
алгоритмом) будет минимальным остовным деревом.
Второй алгоритм поиска минимального остовного дерева (ал-
горитм ближайшего соседа). Этот алгоритм не требует ни сортировки
рёбер по весам, ни проверки на цикличность каждого добавляемого
к строящемуся дереву ребра.
Построение минимального остовного дерева начинается с про-
извольной вершины Vi в заданном графе G. Пусть (v^Vy)— ребро
с наименьшим весом, инцидентное v{9t ребро (г\, tr) включаем в иско-
мое дерево. Затем среди всех рёбер, инцидентных либо vi9 либо vjt
выбираем ребро с наименьшим весом и включаем его в частично по-
строенное дерево. В результате этого в дерево добавляется новая
вершина, скажем vk. Повторяя процесс, ищем ребро с наименьшим
весом, соединяющее либо vi9 либо vjt либо vk с некоторой новой вер-
шиной графа (отличной от vovy,vfc). Процесс продолжается до тех
пор, пока все вершины из G не будут включены в дерево, т. е. пока
дерево не станет остовным. Доказательство того, что алгоритм при-
водит к минимальному остовному дереву, аналогично доказательству
для градиентного алгоритма.
§ 4. ПОИСК КРАТЧАЙШЕГО И НАДЁЖНОГО ПУТЕЙ В ГРАФЕ
Пусть G — взвешенный граф, причём все веса рёбер — неотри-
цательные числа. Пусть Z — какой-нибудь путь, соединяющий вер-
шины v и w; длиной пути Z из v в w будем считать сумму весов
всех входящих в данный путь рёбер. Возможность прикладной ин-
терпретации задачи поиска кратчайшего пути во взвешенном графе
очевидна. Заметим, что без ограничения общности можно рассматри-
вать в данной задаче графы без петель (отсутствие их в кратчайшем
пути очевидно) и без кратных рёбер; при наличии кратных рёбер,
78
соединяющих вершины v и w, следует оставить в графе лишь одно
ребро — с наименьшим весом.
Опишем «отмечивающий» алгоритм поиска кратчайшего пути
между двумя вершинами v и и взвешенного графа G (заметим, что
этот алгоритм применим как в случае неориентированного, так и
в случае ориентированного графа, когда перемещение по дугам до-
пускается только в направлении ориентации).
Вначале вершине и присваивается окончательная метка 0, а каж-
дой из остальных вершин присваивается временная метка оо. На каж-
дом шаге одной вершине с временной меткой присваивается окон-
чательная метка и поиск продолжается. Таким образом, на каждом
шаге метки меняются следующим образом.
1. Каждой вершине у, не имеющей окончательной метки, прис-
ваивается новая временная метка — наименьшая из её прежней вре-
менной метки и числа плюс окончательная метка вершины г,
где i — вершина, которой присвоена окончательная метка на преды-
дущем шаге, а — вес ребра, связывающего i-ю вершину с j-й;
если ребро, связывающее г-ю вершину с j-й (для ориентированного
графа — дуга, ведущая из i-й вершины в j-ю) отсутствует, то счита-
ется Ufy = оо.
2. Находится наименьшая из всех временных меток, которая и
становится окончательной меткой своей вершины. В случае равенст-
ва выбирается любая из них, например (для определённости), имею-
щая наименьший номер.
Процесс продолжается до тех пор, пока вершина w не полу-
чит окончательную метку. Первой помеченной окончательной меткой
вершины будет v, которая находится на нулевом расстоянии от се-
бя. Следующей вершиной, получившей окончательную метку, будет
вершина, ближайшая к v. Третьей вершиной, получившей оконча-
тельную метку, будет вторая по близости и т. д. Легко видеть, что
окончательная метка каждой вершины задаёт длину кратчайшего пу-
ти от начала v до данной вершины; это утверждение формально легко
доказать индукцией по числу вершин с окончательной меткой. Дейст-
вительно, основание индукции — для вершины v — очевидно. Пусть
v,g,...,p— первые к штук ближайших к v вершин; пусть, далее,
q — (к 4- 1)-я по близости к v вершина. Возьмём кратчайший путь,
связывающий veg; смежная с q вершина из этого пути принадле-
жит, очевидно, множеству вершин {v,g,...,p}. Но тогда вершиной q
может быть только та вершина, которая выбирается на (к 4-1 )-м шаге
в соответствии с алгоритмом — иначе получим противоречие с пред-
положением о том, что q — (к + 1)-я по близости к v вершина.
В качестве примера на рис. 21 представлен граф, на котором тре-
буется найти кратчайший путь между вершинами а и д. В таблице 9
отражены результаты применения отмечивающего алгоритма для ре-
шения поставленной задачи; в этой таблице и на рисунке в скобках
заключены окончательные метки вершин.
Искомый кратчайший путь между вершинами а и д находим,
идя обратно от д по вершинам с окончательными метками. На пер-
вом шаге выбираем вершину, смежную с д и такую, что (её метка) +
(расстояние до д) даёт метку вершины д\ аналогично осуществляют-
ся второй и последующие шаги. Таким способом от д до а получим
79
Рис. 21
последовательность вершин g-+e—*b-^c-*cl —► а, из которой по-
лучаем кратчайший путь от а до д:
а- > d —* с --+Ъ ед
(в данном случае путь указан входящими в него вершинами).
Выше предполагалось, что вес любого пути в графе — аддитив-
ная функция, т. е. он равен сумме весов рёбер, образующих путь
из одной вершины в другую. Но можно рассматривать и случай,
когда требуется найти минимум мультипликативной функции. При
Таблица 9
а	ъ	С	d	е	/	9	h
(О)	ОО	оо	оо	оо	оо	OQ	оо
(О)	11	7	3	оо	оо	ОО	оо
(О)	11	7	(3)	оо	оо	ОО	оо
(О)	11	6	(3)	15	11	ОО	оо
(О)	11	(6)	(3)	15	и	ОО	оо
(О)	9	(6)	(3)	15	11	оо	оо
(0)	(9)	(6)	(3)	15	11	оо	оо
(0)	(9)	(6)	(3)	13	И	19	00
(0)	(9)	(6)	(3)	13	(11)	19	оо
(0)	(9)	(6)	(3)	13	(11)	19	19
(0)	(9)	(6)	(3)	(13)	(11)	19	19
(0)	(9)	(6)	(3)	(13)	(И)	18	19
(0)	(9)	(6)	(3)	(13)	(И)	(18)	19
яо
этом можно прологарифмировать нашу функцию, решить задачу для
её логарифма, а затем полученный результат пропотенцировать. В ка-
честве примера рассмотрим задачу о наиболее надёжном пути при-
менительно к каналам связи.
Пусть задан граф (7, в котором вершины задают некоторые пунк-
ты, а рёбра (или дуги) — каналы связи между соответствующими
пунктами. Каждому ребру (или дуге) et приписано число р(е,.) — ве-
роятность безотказной работы канала связи е{, т. е. надёжность кана-
ла et, причём 0<p(et) < 1. Предположим, что каналы связи выходят
из строя статистически независимо друг от друга. В этом случае на-
дёжность пути (связи) Z между пунктами v и ш, т. е. вероятность
безотказной связи между v и w будет равна произведению надёж-
ностей соответствующих каналов, т. е. весов рёбер, входящих в Я.
Обозначим надёжность пути Z через P(Z); тогда
Р(7)= П P(ej.
е, eZ
Нам требуется найти такой путь Z\ для которого
P(Z*) = maxP(Z),
z
где максимум берётся по всем путям, ведущим из v в w. Последнее
условие (задаваемое равенством) можно представить в виде
P^Z*) = П2П P(Zj
или (после логарифмирования)
ln P(Z’) ~ mJnln P(Z) -
= min In -f,—- >—< = min I V' in -4-v
Z П P^i) z 1	P<ei>
€ Z	\ € Я
Отсюда видно, что наша исходная задача отыскания надёжного пу-
ти сводится к задаче отыскания кратчайшего пути между заданными
вершинами v и w на графе, который получается из исходного заме-
ной веса p(ej каждого ребра е. на вес
Заметим, что при использовании отмечивающего алгоритма по-
сле расстановки окончательных меток для всех вершин графа будут
найдены кратчайшие расстояния от заданной исходной вершины до
всех вершин графа.
ЗАДАЧИ
К главе I.
Задача 1. Найти число размещений к одинаковых шаров
по п ячейкам при условии:
а)	в каждой ячейке находится не более одного шара;
б)	в каждой ячейке может находиться более одного шара;
в)	в каждой ячейке находится более одного шара.
Задача 2. Доказать равенства:
i *0
п = к
г>1:м2)=п2-':
fc«0
к = О
*=0
»=»0
ы
Задача 3. Доказать, что
а)	(£) возрастает по п при фиксированном к;
б)	(fcZj) убывает по i при фиксированных п и к;
в)	найти максимальное значение (£) при фиксированном п.
Задача 4. Найти максимальное значение суммы
( П1	।	_L_ ( пв
\к J 1 \к )	\ к ) >
если п1 + п24-...4-п, = пи п делится на з.
Задача 5. Показать, что число разбиений целого числа п
на к частей равно числу разбиений п на части, наибольшая из ко-
торых равна к.
82
Задача 6. Пусть А — некоторое множество, В и С — под-
множества множества А, а Хв и Хс — характеристические функции
подмножеств В и С, Доказать равенства:
а)	Хэ-= 1 ~ Хв-
6)	Хв\с = Хв ~ ХвХс-
в)	Хлпс = ХвХс-
г)	Хвис~Хв + Хс ~ХвХс-
д)|в| = !>(*).
sofiA
Задача 7. Имеется т предметов и п различных свойств, ко-
торыми могут обладать эти предметы. Пусть тг — число предметов,
обладающих в точности г свойствами из п. Доказать, что
mr = 52(-1)* (*, г) $2	МА» •••»»*+.)»
*-0	1	<...<<fc+r<n
где	+ — число предметов, обладающих	+
свойствами (г > 1).
Задача 8. Найти производящую функцию для последова-
тельности {а„}, если: a) an = 1; б) ап =(£); с) ап = (”+£-1).
Задача 9. С помощью тождеств, связывающих производящие
функции, вывести тождества для биномиальных коэффициентов:
а)	(1 + ®)"(1 - х)п = (1 - хг)п,
fc"2) при чётном к,
,=о	'	'	* (О	при нечётном к;
б)	(1 + ®)п(1 + х)~т = (1 + х)п~т,
1=0
Задача 10. Найти ап по рекуррентным соотношениям и
начальным условиям:
а)	ап+2 “ 5°n+i + 6а„ = 0, Оо = 10, «ц = 26;
б)	ап+4 - 5ап+2 4- 4ап = 0, Oq = 10, = 26,	— 56, (% = 122.
Задача 11. Найти n-й член последовательности Фибоначчи
{Fn}, задаваемой рекуррентным соотношением Fn+2 = Fn¥[ + Fn и
начальными условиями F{ — F2 ~ 1.
К главе II.
В задачах 1-14 рассматриваются неориентированные графы.
Задача 1. Показать, что в любом графе без петель и кратных
рёбер, содержащем не менее двух вершин, найдутся две вершины
с одинаковыми степенями. (Степень вершины графа определяется
числом инцидентных этой вершине рёбер.)
83
Задача 2. Пусть cr(G) — наименьшая из степеней вершин
графа G, не имеющего петель и кратных рёбер и содержащего п
вершин (п > 2).
а)	Доказать, что если a(G) > то граф связен.
б)	Показать, что в предыдущем утверждении нельзя заменить
Задача 3. Доказать, что если в графе степень каждой вер-
шины больше единицы, то в нём есть цикл.
Задача 4. Доказать, что каждое дерево является двудольным
графом.
Задача 5. Найти число попарно неизоморфных 4-вершинных
графов без петель и кратных рёбер.
Задача 6. Доказать, что при любом натуральном п > 3 су-
ществует n-вершинный связный граф без петель и кратных рёбер,
содержащий п - 1 вершин с попарно различными степенями.
Задача 7. Доказать, что если в графе имеется ровно две
вершины с нечётными степенями, то найдётся цепь, соединяющая
эти вершины.
Задача 8. Доказать, что если в n-вершинном дереве нет
вершин степени 2, то в нём содержится не меньше чем ^-41 висячих
вершин.
Задача 9. Корневое дерево D имеет к висячих вершин, от-
личных от корня, и не имеет вершин степени 2, отличных от корня.
Доказать, что при fc > 2 общее число вершин в дереве не превосхо-
дит 2к.
Задача 10. Доказать, что в связном графе любые две простые
цепи максимальной длины имеют общую вершину. Верно ли, что у
них всегда есть общее ребро?
Задача 11. Доказать, что не существует графа с двумя или
более вершинами без петель и кратных рёбер, у которого степени
всех вершин попарно различны.
Задача 12. Доказать, что любой граф допускает такую гео-
метрическую реализацию в трёхмерном пространстве, при которой
его ребрам отвечают прямолинейные отрезки.
Задача 13. Доказать, что ранг матрицы инциденций связно-
го графа с п вершинами равен п - 1 (подразумевается, что арифме-
тические операции при вычислении определителей производятся по
модулю 2).
Граф называется эйлеровым, если в нём имеется цикл, содержа-
щий все вершины и все рёбра данного графа.
Задача 14. Доказать, что для связного графа следующие
утверждения эквивалентны:
1)	G — эйлеров граф;
2)	каждая вершина графа G имеет чётную степень;
3)	множество рёбер графа G можно разбить на простые циклы.
Задача 15. Найти число неизолированных ориентированных
графов, содержащих:
84
a)	2 вершины и 2 дуги;
б)	2 вершины и 3 дуги;
в)	3 вершины и 2 дуги;
Задача 16. Доказать, что если полустепень исхода каждой
вершины (т. е. число исходящих из этой вершины дуг) ориентиро-
ванного графа положительна, то в нём существует ориентированный
цикл. (Петля считается ориентированным циклом длины 1).
К. главе III.
Задача 1. Пусть D — собственное подмножество множе-
ства Еп всех булевых наборов длины п и |Р| 2я"1. Показать, что
существует такой набор а е Еи, что D Q (а ф D) = 0, где а ф D
есть множество всех булевых наборов вида а ф /3, где (3 е D, а
а ф 0 = (04 ф Д,..ап ф 0п).
Задача 2. Найти число попарно различных булевых функ-
ций, получающихся из функции V х{х3- подстановкой констант
вместо переменных
Задача 3. Найти число булевых наборов длины п, на которых
функция	обращается в единицу, если:
a)	f(xit...,xn) = £	2	я,,
к — 1 1 < ij < ... < ik < п
б)	/(х{,...,хп) = Е X ...х(;
* = 1
в)/(а:1,...1а5п)=	£	х{<-...х^
1 <г,	<п
(знак £ означает сумму по модулю 2).
Задача 4. Множество А состоит из булевых функций, каж-
дая из которых существенно зависит от всех своих переменных. До-
казать, что всякая формула Ф над А, содержащая попарно различные
переменные, каждая из которых входит в Ф ровно один раз, реализует
булеву функцию, существенно зависящую от всех своих переменных.
Задача 5. Пусть /(^,..., хп) — булева функция, существен-
но зависящая от всех своих п переменных. Доказать, что найдутся
переменная х{ и булева константа a (a G {0,1}) такие, что функция
f(x{,..х. _ j, а, хг. +1,..., хп) существенно зависит от всех своих п - 1
переменных.
Булева функция f(x{).,.,xn) называется симметрической, если
при любой перестановке переменных получается функция, равная
Задача 6. а) Показать, что любая булева функция от трёх
переменных может быть получена из симметрической функции от
семи переменных отождествлением переменных.
б)	Указать взаимно однозначное соответствие между множест-
вом булевых функций от трёх переменных и множеством симметри-
ческих функций от семи переменных.
в)	Показать, что любая булева функция может быть получена
из симметрической функции отождествлением переменных.
Задача 7. Известно, что булева функция f(xx,	я^) зави-
сит существенно от каждой из трёх своих переменных. Доказать, что
в этом случае найдутся переменные (i е {1,2,3}) и булева констан-
та а (cr G {О, I}) такие, что при подстановке в f(x{, х21 х3) константы а
вместо переменной xt получается симметрическая функция, сущест-
венно зависящая от каждой из оставшихся двух переменных.
Задача 8. Можно ли функцию х & у реализовать формулой
над множеством {я у}? (Другими словами, можно ли конъюнкцию
выразить через импликацию?)
Задача 9. а) Доказать, что любую булеву функцию от п
переменных, отличную от константы 0, можно представить в виде
дизъюнктивной нормальной формы (д. н. ф.), содержащей не более
2п~1 элементарных конъюнкций вида х°1 •... • х“* (к < n; ip iq при
p^q)-
б) Указать булеву функцию от п переменных, для которой лю-
бая д. н. ф., представляющая эту функцию, содержит не менее 2п~1
элементарных конъюнкций.
Задача 10. Доказать, что булева функция f(xx,..., хп) обра-
щается в единицу на нечётном числе наборов значений своих пере-
менных в том и только в том случае, когда полином Жегалкина этой
функции содержит конъюнкцию максимальной длины х{х%... хп.
Пусть М — произвольное множество булевых функций. Замы-
канием множества М называется множество всех тех булевых функ-
ций, каждая из которых может быть реализована формулой над М;
обозначается замыкание множества М через [М].
Задача 11. Доказать следующие свойства замыкания:
а) М С [М]-,
б)
в)
г)	[М] — [1М]];
д)	если М{ С М2, то [MJ С [М2].
Булева функция Д^,...,^) сохраняет константу 0 (кон-
станту 1), если Д0,...,0) = 0 (соответственно если /(!,..., 1) = 1).
Множество всех булевых функций, сохраняющих константу 0 (кон-
станту 1), обозначается через То (соответственно через Д),
Булева функция f(x\,..-,xn) считается: самодвойственной, ес-
ли /(ж1,...,яп) = /(я1,...,яп); линейной, если существуют такие бу-
левы константы	что /(жп...,жп) = аофа1ж1ф...фапжп;
монотонной, если для любых двух наборов а =- (ап...,ап) и /3 ~
= ($,...,/?„) таких, что а < /3 (т. е. ах Д,..., ап (Зп) выполняется
неравенство Да) < ДЬ). Множества самодвойственных, линейных
и монотонных булевых функций обозначаются соответственно через
S, L и М.
В классах То, 7], S,L,M выделим подмножества булевых функ-
ций, зависящих от п переменных	и обозначим эти подмно-
жества через TQn, Дп, Sn, Ln, Мп соответственно.
Задача 12. Доказать, что классы TQ, Д, S, L, М замкнуты
и отличны от Р2 (Р2 —множество всех булевых функций).
86
Задача 13. Найти число булевых функций в каждом из
множеств То", Ttn, Sn, Ln.
Задача 14. Найти число булевых функций /(^,..., хп), при-
надлежащих множеству:
a)	7JU 7J UL;
б)	IjnSOl;
в)	То U (L П М)-,
v)(T^S)\L;
e)S\(T0\L);
ж)	То U 1] U S U L;
з)	(L\S)\M.
Задача 15. Доказать, что если булева функция f(x^.,,
...,хп) не является самодвойственной, то, подставляя х их вместо
переменных	можно получить константу (0 или 1).
Задача 16. Доказать, что если булева функция /(ж,,...
...,жп)— немонотонная, то, подставляя вместо её переменных функ-
ции 0, 1, х, можно получить функцию х.
Задача 17. Доказать, что если булева функция /(жр...
...,жп) — нелинейная, то, подставляя вместо её переменных функ-
ции 0, 1, х, х, у, у, можно получить х & у или х & у.
Пусть А — замкнутый класс, а В — произвольное множество
булевых функций из А. Множество В полно в А, если любая функ-
ция из А может быть реализована формулой над В; множество В
считается базисом в А, если В полно в А, но любое собственное
подмножество В полнотой в А не обладает.
Задача 18. Используя утверждения из задач 12,15-17, дока-
зать следующий критерий полноты (теорему Поста): для того, чтобы
множество М булевых функций было функционально полным в Р2,
необходимо и достаточно, чтобы это множество не содержалось це-
ликом ни в одном из классов 7J, 7], S, L и М.
Задача 19. Доказать, что если булева функция f монотонна
и существенно зависит не менее чем от двух переменных, то система
{О,/} полна в Р2.
Задача 20. Выяснить, является ли множество В базисом
в А, если:
а)	А = 7], В ~{xy~z};
б)	А = 7J, В -{ху V z}\
в)	А = L, В — {х ~ у, х ф у};
г)	А — L, В = {я?! ф Х2 ф... ф хк, 1}, к — константа;
д)	А = TQ П 7], В {ху, xyVxzV yz}.
Булева функция f называется шефферовой, если любую булеву
функцию можно выразить через f (т. е. если f образует базис в Р2).
Задача 21. Выяснить, при каких п функция f является
шефферовой:
a)	f >• • • > ) ~ ^ Ф *^1 Ф«»»Ф*£,Я'1 + 1 Ф • • • Ф Хп __ ] Хп Ф Хп X.,
б)	лп) = 1	Ф...фXn-iX*;
87
в)	/(«!,. ;Хп)=- 1 ф	х<х^
г)	/(x1,...,xn) = 1 ©(^/х,)®... Ф(х,/х\ И)Ф... ®{xn_Jxn)®
Ф {Xn/X\)'i
Д> f(xl,...,xn)=. 1 ©(^/^©...©(х./х^!)®...®^,,.!^).
Задача 22. Найти число шефферовых функций, зависящих
не более чем от п переменных.
К главе IV.
В главе IV были определены:
а)	схемы из функциональных элементов в базисе
6)	функции, реализуемые схемами;
в)	сложность L(S) произвольной схемы S;
г)	сложность L(f) функции /;
д)	функция Шеннона L (п).
Если вместо базиса {&, V, —} берётся какая-нибудь другая конеч-
ная система функций F = {Л т° все перечисленные объекты
и понятия вводятся совершенно аналогично тому, как это было сде-
лано для {&, V, небольшие и почти очевидные изменения в опре-
делениях, соответствующие рассматриваемому базису F, вносятся
лишь на самом первом этапе — при определении схемы. Например,
в случае схем в базисе {&, ф, 1} вершинам из V2 приписывается сим-
вол 1 (константа 1), а каждой вершине из V3 приписывается один из
символов &, ф (одна из функций х1 ф я^). Для схем в базисе
{/} множество вершин V2 (из определения схемы) пусто, а каждой
вершине из V3 приписывается символ / (функция xl/x2 = xi V®2)»
и т. д. В предлагающихся ниже задачах базис указывается нижним
индексом (или, точнее, нижней системой индексов) при соответст-
вующих обозначениях.
Задача 1. Доказать равенства:
а)	£{&,v,-}U) — £{&,Vj-}(0) —	У) ~	=
б)	L{&^_}(x ф у) = L{&jV _}{х - у) = 4.
Задача 2. Доказать равенства:
а)	£{&,©, 1}(ж ~ У) — 3;
б)	Ь{&,®л}(хУ) = Ь(ш/з/) =	Уу) = 3;
в)	Ь{а>ф>1}(ж-^2/) = 4.
Задача 3. Доказать равенства:
а)	£{/}0) = L{/}(x —* у)~ L{/}(x &у) = 2;
б)	Lyy(x V у) = 1/|д(0) = 3;
в)	^{/}(ху) = L{/}(x Ф у) = 4;
г)	L{/}(x~y) = 5.
Задача 4. Показать, что
Задача 5. Показать, что для любой булевой функции f(x{,...
...,х'п) выполняются неравенства:
6) L{v,.asn)) < 2L(&,Vt_}(/(«!,..®„)) + n;
Задача 6. Найти £{А>Ф>1}(Ж1 V V ... V xn).
Пусть Nn [fi,..fn}, где = xx фж2®.. ,ф^„!Ф^ +! Ф^+2Ф...
... Ф жп, i = 1,2,...,п.
Задача 7. Показать, что
a)L{ffi}(2V3) = 3;
6)L{e}W) = 6;
в)Ь{(В)(ЛГп)==2п-2;
(здесь через L^(Nn) обозначаем сложность реализации систе-
мы булевых функций Nn схемами из функциональных элементов в
базисе {#! ф xj, т. е. полагаем L^y(Nn) = minX(5), где минимум
берётся по всем схемам в базисе {ф}, реализующим Nn, a L(S) —
число функциональных элементов ф в схеме S).
Пусть —множество всех булевых функций от п перемен-
ных ж1?...,жп, представимых полиномами Жегалкина степени не вы-
ше k.
Задача 8. Показать, что:
а)	для любой функции f € Q^2 справедливо неравенство
2
Ь{4,е,1}(/) £
б)	для каждой функции f G Q^3 справедливо неравенство
„з
в)	для каждого п = 2,3,... существует такая функция fn е Qnj2,
что
2
•£'{4,ф,1}(А)х1^7
(а(п) х Ь(п) означает, что найдутся константы q и Cg, для кото-
рых одновременно выполняются неравенства а(п) с{Ь(п) и Ь(п) <
< с,а(п)).
Задача 9. Показать, что в любом конечном полном базисе
можно построить схему из функциональных элементов, реализую-
щую все булевы функции от п переменных и содержащую 2Г - п
элементов; доказать минимальность этой схемы.
Задача 10. В базисе из всех двуместных булевых функций
построить схему из функциональных элементов, которая содержит
не более чем 5п - 3 элементов и вычисляет арифметическую сумму
двух n-разрядных двоичных чисел.
Задача 11. Пусть Сп есть (n, ] log(n4-1 )[)-оператор, т. е. упо-
рядоченный набор из ]log(n-|-1)1 булевых функций
...,/]108<п+!и(жр•••>#„)), который на произвольном наборе <7 —(ст15...
..ап) значений переменных	..., хп выдаёт набор /?(о) = (/i (<г),...
, • •> /|iog<n+1)[(^))» являющийся двоичной записью числа единиц в на-
боре а. Доказать, что
L{M(Cn)<n.
89
Задача 12. Доказать, что для произвольной симметрической
булевой функции	от п переменных справедлива верхняя
оценка сложности
Задача 13. Показать, что для любых двух конечных полных
в Р2 базисов Б, и Б2 и всех булевых функций / G Р2 справедливо
соотношение
ЬБ1(/)хЬБ2(/).
Задача 14. Пусть Кп — множество всех элементарных конъ-
юнкций xf* •... • х"п длины n, a Dn — множество всех элементарных
дизъюнкций х°' V... V х„* длины п. Доказать цепочку равенств
Ь{А1Ч(К U Dn) ~ L{K_}(K U Dn) ~ 2n+1.
К главе V.
Ниже рассматриваются функции из Рс, т. е. отображения вида
3/ = /(х), гдея: = {а:(1),я:(2),...,я:(г),...}, у={у(1),у(2) »(*),...}.
а значения x(i) и y(i) принадлежат множеству Е2 = {0,1}, i = 1,2,...
Задача 1. Среди перечисленных ниже функций из Рс найти
детерминированные и ограниченно-детерминированные функции:
а)	у(2* - 1) = з/(2*) = x(t), t = 1,2,...;
б)	у(*) = у(* + 1) = а:(*)фя:(* + 1), * = 1,3,...;
в) »(*)«£«(<)» * = 1>2,.
< = 1
(О
2(*)V y(t + 1),
при t =1,
если t — чётное число,
если t — нечётное число
большее двух;
Ь Т I	* + 1
если V х(г)> £®(г),
Д) У(О= <
е) !/(*)=<
О,
1
О,
в противном случае;
если в наборе (х(1),я(2),...,а5(*))
нулей больше чем единиц,
в противном случае;
1
Задача 2. Выяснить, являются ли перечисленные ниже функ-
ции ограниченно-детерминированными, и для ограниченно-детерми-
нированных функций найти их вес:
а) У(0 =	( 1 при * = 1, ( x(t) при * > 2;
б) у(*) =	( 1 при * = 1, | ж(* - 1) при * > 2;
в) у(*) =	( ш(1) при * = 1, ( х(*) V у(* - 1) при * > 2;
90
Г) 1/(0 = {	0 при t = 1,2,...,п, x(t) при t > п 4-1;
д) 1/(0 = j	г ж(0, если t —нечётное число, x(t/2), если t —чётное число;
0 i/(0 = j	' 0 при t = 1,2,..., п, k х( t - п) при t > п 4-1;
ж) у(0 =	j 1, если 22 Хх ~ Ю» \	i = ! ( 0 в противном случае.
Задача 3. Построить диаграмму переходов, таблицу перехо-
дов, канонические уравнения и схему автомата в базисе {&, V, -, z}
(содержащем функциональные элементы, реализующие х & у, хУ у,
35, и элемент единичной задержки z) для о.-д. ф.:
	' 0, если 0mod3) = O,
0 1/(0 = *	1, если t(mod3)= 1, u е(0, если t(mod3) = 2; Г 0, если t — нечётное число,
б) 1/(0=’	ж(0, если t =4п4-2, ( x(t - 2), если t = 4п, где п'= 0,1,... ( 1, если t = 1,
в) 1/(0= (	0, если t = 2, [ x(t - 1), если t > 3;
0 1/(0 = j	’ х(1), если t —нечётное число, k ж(2), если t — чётное число; r	t 0, если J} ^(0(m°d3)-O, i = 1
Д) 1/(0 = <	t 1, если 22 ®(i)(mod3) = 1, i = 1 t x(t), если 22 ®(O(m°d3) = 2; k	»' = 1
е) у(0 = ‘	' 0 при t = 1, x(t - 1) V y(t - 1) при t > 2; f 1, если t = 1,
ж) у(0 =	< ^(t), если x(t)- y(t - 1), t > 2, ( x(t - 1), если x(t)^y(t - 1), t >2;
з) 1/(0 = |	r x(t) при t = 1,2, x(t) V y(t — 1) при t = 3,4,...
Задача 4. Построить схему автомата в базисе {&, V, -, z},
реализующего упорядоченную пару о.-д. ф. у{ =/1(ж), эд = /2(ж), зада-
ваемых условием: (эд (0, эд( *)) есть двоичная запись числа х( 1) 4-...
... 4- x(t)(mod3), t = 1,2,...
91
Задача 5. Построить диаграмму переходов и схему автомата
в базисе {&, V, -,z}, реализующего о.-д. ф. у --	задаваемую
условием:
,.(П==( Ж,(1)при t -1,
' 1 МО® Яг(* ~ 1) при t =2,3,...
Задача 6. Построить канонические уравнения, таблицу пере-
ходов и диаграмму переходов для о.-д. ф., реализованной автоматом,
представленном на схеме: а) рис. 22; б) рис. 23; в) рис. 24.
К главе VI.
Задача 1. Построить двоичный префиксный код с задан-
ным набором I длин кодовых слов (элементарных кодов):
а)	Г= (1,2,3,3);
б)	Г= (1,3,3,4,4,4,4);
в)	/=(2,2,3,3,3,4,4);
Задача 2. Выяснить, может ли набор чисел I быть набо-
ром длин кодовых слов разделимого алфавитного кода в //-значком
кодирующем алфавите:
92
a)	I = (1,2,3,3,4), q-~2;
б)	Г= (1,2,2,3,3,3), g = 3;
в)	£-(1,1,2,2,3,3,3), (? = 3;
r) I = (1,1,1,2,2,2,3,3,3,3,3), q = 4.
Задача 3. Алфавитный двоичный код 52 (А) содержит более
чем 21 кодовых слов длины, не превышающей Z. Выяснить, может ли
код 53(A) быть
а)	взаимно-однозначным;
б)	префиксным.
Задача 4. Используя теорему о редукции, построить двоич-
ный код с минимальной избыточностью для набора вероятностей Р:
а) Р-(0,6;0,2;0,1;0,1);
б)	Р = (0,4;0,3;0,1; 0,08; 0,08; 0,04);
в)	Р = (О,3;О,3;0,1;0,1;0,04;0,03;0,03;0,03;0,03;0,02;0,02).
Задача 5. Указать набор вероятностей Р, для которого су-
ществует оптимальный двоичный код Хаффмена с заданным набором
I длин кодовых слов, и построить соответствующий код:
a)	/ = (1,2,4,4,4,4);
б)	Г= (1,3,3,4,4,4,5,5);
в)	Г= (2,2,3,3,3,4,5,5);
Задача 6. Доказать, что в оптимальном двоичном коде Хафф-
мена число элементарных кодов максимальной длины чётно.
Задача 7. Выяснить, существует ли оптимальный двоичный
код Хаффмена с заданным набором I длин кодовых слов:
а)	Г= (1,3,4,4,4);	г) Г-(1,2,3,4,4,4,4);
б)	Г= (1,2,3,4,5); д) Г= (1,2,3,5,5,5,5).
в)	Г= (1,2,3,4,5,5);
Задача 8. Рассматривается множество S оптимальных дво-
ичных кодов Хаффмена для всевозможных наборов вероятностей
(Pi,---,Pi5,2“20)» удовлетворяющих условиям
р1>...>р15>2-20
и
Pi + ... + Р1з + 2~20= 1.
Пусть /(52) — наибольшая длина слова из кода 52- Найти
max Z (S) и min Z(£).
EeS EeS
Задача 9. Построить код Хэмминга Л6.
Задача 10. Найти кодовое слово 0 из кода Хэмминга для
сообщения а:
а)	а =001;	д) « = 1110001;
б)	а = 101;	е) а = 11011001;
в)	а = 1000;	ж) «=0011010111;
г)	« = 1011;	з) « = 110101110010.
9‘i
Задача И. По каналу связи, искажающему передаваемое
слово не более чем в одном разряде, было передано кодовое слово из
кода Хэмминга, отвечающее сообщению а. Восстановить исходное
сообщение а, если принято было сообщение /3:
------	г)/3 = 101110111;
д) /3=00011000101000;
е) /3= 00111000101000.
a) /3 = 010011;
б)/3 = 110001;
в) /3 = 001100111;
К главе VII.
Задача 1. Найти минимальное остовное дерево для взве-
шенного графа, изображённого на:
а) рис. 25; б) рис. 26.
Задача 2. Найти кратчайший путь между вершинами v и и'
графа, изображённого на рис. 27.
Рис. 27
94
Задача 3. Найти максимальный поток между полюсами а
и р сети, изображённой на:
а) рис. 28; б) рис. 29.
Рис. 29
Задача 4. Выделить две вершины в приведённом на рис. 30
графе так, чтобы при указанных пропускных способностях рёбер
можно было бы создать поток наибольшей величины через полу-
ченную сеть. Сколько попарно неизоморфных сетей, допускающих
потоки максимальной величины, можно получить, выбирая разными
Рис. 30
Задача 5. Указать максимальное (по числу рёбер) паро-
сочетание для единичного n-мерного куба. Сколько рёбер содержит
такое паросочетание? (Единичный n-мерный куб представляет собой
95
граф с 2П вершинами, занумерованными двоичными наборами, т. е.
числами («!,..ап) длины п, в котором рёбрами соединены те и
только те пары вершин, номера которых различаются ровно в одном
разряде.)
Задача 6. На единичном п мерном кубе произвольным об-
разом выбраны две вершины. Найти величину максимального потока
в полученной двухполюсной сети при условии, что пропускная спо-
собность каждого ребра равна единице.
Если вершине v единичного n-мерного куба приписан набор
5 — (au...,an), то номером этой вершины будет число /V(v) —
п
- ai^n *» т. е- число, двоичной записью которого является на-
бор а.
Задача 7. Найти минимальное остовное дерево и его вес
для единичного n-мерного куба, если вес ребра, соединяющего вер-
шины v и v', равен:
a)	min(7V(v), #('</));
б)	тах(ЛГ(т;)^(^)).
Если вершине v ejwsmm n-мерного куба приписан набор а =
= ап), то весом данной вершины считаем число w(v) = 52 <**•
i = 1
Задача 8. Найти минимальное остовное дерево для единич-
ного n-мерного куба, если вес ребра, соединяющего вершины v и v't
равен:
a)	min(w(v), w(v'));
б)	max(w(v),
СПИСОК ЛИТЕРАТУРЫ
1.	Алексеев В. Б., Ложкин С. А. Элементы теории графов и схем.
М.: Изд-во МГУ, 1991.
2.	Б е р ж К. Теория графов и её применения. М.: ИЛ, 1962.
3.	Гаврилов. Г. П., С а п о ж е н к о А. А. Задачи и упражнения по
курсу дискретной математики. Издание второе. М.: Наука, 1992.
4.	Дискретная математика и математические вопросы кибернетики. Т. 1. / Под
редакцией С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.
5.	Е м е л и ч е в В. А., Мельников О. И. С а р в а н о в В. А.
Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.
6.	Комбинаторный анализ. Задачи и упражнения / Под редакцией К. А. Рыбни-
кова. М.: Наука, 1982.
7.	Л у п а и о в О. Б. Асимптотические оценки сложности управляющих
систем. М.: Изд во МГУ, 1984.
8.	Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.
9.	О ре. О. Теория графовлМ.: Наука, 1980.
10.	Уилсон Р. Введение в теорию графов. М.: Мир, 1977.
11.	Харари Ф. Теория графов. М.: Мир, 1973.
12.	Холл М. Комбинаторика. М.: Мир, 1970.
13.	Шоломов Л. А. Основы теории дискретных логических и вычисли-
тельных устройств. М.: Наука, 1980.
14.	Яблонский С. В. Введение в дискретную математику. Издание второе.
М.: Наука, 1986.