В.П. Одинец
М.Я. Якубсон
Элементы
дискретной
математики
 '-'I 1 INVM П ЮЛ1«У8 ГЭЦДС
м id ннодтмэце ммшугхот our
^dT/J f fiL < H aOi.iiHq f
(noxsimfin^v
Федеральное агентство но образованию
Коми государезвенный педагогический институт
В.П Одипец, М.Я. Якубсбн
Элементы дискретной математики
Учебное пособие
Допущено учебно методическим объединением но направлению
педагогического образования в качестве учебного пособия для
студентов высших учебных заведений, обучающихся
ио направлению 540200 "Физико-математическое образование"
РГГТУ им А.И. Гврцеиа
Библиотека No 3
есте<ЛБенно-математическ0й
ПИТвраТуры
Сыктывкар 2006
ФБ РГПУ им А. И Герцена
IIIIIIIIIMIIIIIII
3000004718
УДК 681 3.06.51
519.1
ББК 22.176
Печатается по решению редакционно-издательского совета Ко
ми государственного педагогического института от 21.12.2005 г.
Рецензенты:
Флегонтов А.В. — профессор, доктор физ.-мат. паук за-
ведующий кафедрой информационных систем и математического
обеспечения PL ПУ им. А И Герцена (г Санкт-Петербург);
Фокин Р.Р. - профессор, доктор пед. наук, профессор ка
федры информатики СПбГУП (г. Санкт-Петербург), действи-
тельный член Академии информатизации образования
Одинец В П , Якубсон М.Я.
Элементы дискретной математики. Учебное пособие. -
Сыктывкар: Изд-во Коми пед. ип-та, 2006 - 175 с.
ISBN 5-87661-066-6
Киша основана па лекциях, прочитанных первым авто>юм
на факультете точных наук Зелсногурского университета (Поль-
ша) и физико-математического факультета Коми пединститута,
а вторым автором па матемагичсском факультете РГПУ им
А И Герцена.
В двух частях. I. Элементы комбинаторики и рекуррентные
соотношения, II Элементы теории графой, изложены все основ-
ные понятия и факты дискретной математики, соответствующие
Государственному образовательному стандарту для специальности
"Информатика" педагогических нузов. Для удобства читателей
сложные доказательства выиесепы в два приложения.
Книга рассчитана на студентов щжподавателей школ и других
учебных заведений, а также всех, интересующихся информатикой.
ISBN 5-87661-066-6	©Одинец В.П., Якубсоп М Я., 2006
©Коми государственный педагогический институт, 2006
3
Оглавление
Предисловие ...............................-..........°
’{есть I. Элементы комбинаторики и рекуррентные
соотношения
1.	Элементы комбинаторики..................................7
1.] Основные принципы комбинаторики .......................7
1.2	Основные комбинаторные конфигурации:
размещения, пе^стаповки, сочетания-	...	8
1.3	Свойства сочетаний Пином Ньютона Кратные суммы.
Производящие функции................................ 12
1.4	Упражнения............................    -	19
2.	Рекуррентные соотношения..........................22
2.1	Рекуррентные уравнения Примеры. . . М- . -	...........-22
2.2	Линейные рекуррентные уравнения..................31
2.3	Сравнение роста и убывания последовательностей...40
2.4	Асимптотические решения рекуррентных уравнений
Формула суммирования Эйлера......................... 47
2.5	Упражнения...................-.....-........-....56
Часть II. Элементы теории графов
3.1	Графы Определения. Классификация..............  -60
3.2	Операции па графах.........  -................   79
3.3	Связность и fe-связность графов. Метрики на графах....	91
3-4 Цикломатическос число. Деревья. Алгоритм Краскала......104
3.5	Планарные графы. Формула Эйлера.
Хроматическое число. .........................-		113
3.6	Внешняя и внутренняя устойчивость диграфов
Ядра графов Игры на i рафах	...	... 129
3.7	Эйлеровы и гамильтоновы графы. Двудольные графы.
Теорема Кенига...............................   -	-  • 140
3.8	Упражнения......................................147
4
Приложения .........................................  158
Библ noi-рафический список ........................   363
Предметный указатель.................................... 165
Именной указатель................................     169
Указатель обозначений.................................173
5
Предисловие
'[искрегная1 математика - это область математики, занима-
ющаяся изучением структур дискретного (в противоположность
непрерывному), в частности, конечного характера. Эти структуры
возникают как в самой математике, так и в области ее прило-
жений. Изложение дискретной математики может быть наполнено
различным содержанием в зависимости от цели и задач данного
изложения.
Действующий в настоящее время стандарт для студентов
педагогических вузов, специальности которых связаны с. информа-
тикой, требует изложения двух больших разделов. Первый вклю-
чает теорию рекуррентных уравнений (которую можно р-.ссмагри-
ватъ как начала теории динамических систем с дискретным време-
нем), второй - элементы теории графов. Первый раздел посвящен в
основном теории линейных рекуррентных соотношений, решению
простейших рекуррентных уравнений, включая асимптотические
методы, а также методы суммирования. Во втщюм разделе рас-
сматривается классификация графов, даны операции на графах,
включая основную теорему о синтезе графов па языке матриц
смежности, изучаются свойства связности, планарности, раскраски
графов метрики на графах цепи, циклы и нуги па графах.
Сверх стандарта мы рассматриваем проблематику внутренней
и внешней устойчивости гра<}юв, ядра графов и игры на гра-
фах, а также некоторые понятия идемпотентного анализа - бурпо
развивающейся теории на стыке дискретной математики, теории
алгоритмов и теории управления. Нами рассмотрены целочислен-
ные функции получаемые с помощью производящих функций,
а также функция Гранди - рекурсивная функция, важная для
теории игр. К|юмс того, при изучении фундаментального множест-
ва решений однородного рекуррентного уравнения нами вводится
матрица Каэорати и определитель Казорати, использующиеся при
изучении зависимости (или независимости) последовательностей,
что ш-рает важную роль при анализе наблюдений.
В отличие от курсов дискретной математики для втузов мы не
рассматривали проблемы функциональных композиций и деком-
позиций. а также теории переключательных функций и их разло-
'от лаг. discretus прерывпегый.
6
жспий. Некоторые из этих вопросов изучаются в педвузах в xyj>-
сах "Математическая логика". "Компьютерная алгебра", "Теория
алгоритмов". Также нс рассматривались элементы теории кодиро!
вания, хеширование, сортировки, операции над строками текста,
как это имеет место в учебных пособиях для специалистов по
прикладной математике. Тем не менее, как приложение резуль-|
тагов первого раздела и теории графов, мы рассмотрели задачу
пересчета корневых деревьев.
Нумерация теорем, предложений, следствий, определений,
примеров, замечаний и формул в книге трехзвенпая (глава, па
раграф, порядковый номер). Конец доказательства будет обозна-
чаться значком 
В конце книги мы приводим список основной и дополнительной
литературы на русском языке. Эта литература может быть полезна
тем, кто хотел бы расширить свои знания по отдельным гемам.
В заключение хотелось бы поблагодарить всех причастных
к появлению этой книги, и прежде всего рецензентов: про-
фессоров А.В Флегонтова и Р.Р.Фокина, а также профессоров
В.М Нежинского и М.В Швецкого, прочитавших рукопись и сде-
лавших пенные замечания.
I Элементы комбинаторики	7
1 Элементы комбинаторики
1.1	Основные принципы комбинат-
орики
Комбинаторика (лат. combinare соединять, сочетать) - раздел
математики, занимающийся пересчетом элементов конечных мно-
жеств. Задача пересчета - это определение числа элементов, при-
надлежащих данному конечному множеству и обладающих задан-
ным набором свойств. Пусть X конечное множество, содержащее
п элементов (будем обозначать этот факт |Х| = п) В комбинат-
орике принято говорить, что объект х из X может быть выбран
п способами. Если множества X] . ..Хп не пересекаются, то, оче-
видно,
и*.
1=1 *—1
В комбинаторике этот факт (для случая п = 2) называется прави-
лом суммы.
Правило суммы. Если объект х может быть выбран т
способами, а объект у соответственно п способами, то выбор
"х или у " может быть осуществлен т + п способами.
Например, езди в коробке 12 белых и 12 черных шашек выб-
рать любую (белую или черную) шашку можно 24 способами
Обобщением правила суммы является формула для количества
элементов объединения пересекающихся множеств.
Теорема 1.1.1 (Формула включений и исключений).
U* =£|xi|-£|x1x,|+ £ |xixJxJfc|-...+(-i)"-1|x1...xn|.
‘“1 t-l i/j
(Здесь мы пишем XjXj вместо X, Г> Х7).
Доказательство проведем па примере случая п = 3. (Случаи
п = 1 и п — 2 тривиальны.) Начнем с равенства |Xi U Х2 U Хд| =
Х]|-|- X2I+ Х3|. Оно неверно, в частности, потому, что элементы,
принадлежащие пересечениям двух множеств, посчитаны дважды.
Исключая их, получим |Х] U Х% U Хз| — |Xi| + X2I |Хд —
8
1. Элементы комбинаторика
|XiX2| - |Х2Хз! - |Х|Х3|, однако это равенство также неверно,
потому что элементы из пересечения всех т[>ех множеств были 3
раза включены и 3 раза исключены, поэтому их надо включить
еще раз, получаем верное равенство
|X1UX2UX3 = ^1|+|Х2|+|Х3[- Х,Х2|- ХгХзНХ^з + X.X2X3J
Этот метод доказательства объясняет название формулы. До-
казательство для щхмзвольного натурального п приведено в при-
ложении 1.
В ситуациях, когда надо выбрать пару объектов, применяется
правило произведения.
Правило произведения. Если объект х может быть выбран
т способами, причем при каждом таком выборе объект у может
быть выбран п способами, то выбор упорядоченной пары (х,у)
может быть осуществлен тпп способами.
Краткая математическая запись этого правила такова
|Х, xX2| = |Xi|.|X2|.
Пример 1.1.1. В ситуации предыдущего примера пару, состо-
ящую из белой и черной шашки, можно выбрать 144 способами.
1.2	Основные комбинаторные кон
фигурации: размещения, пере
становки, сочетания
При решении комбинаторных задач часто приходится рассмат-
ривать подмножества некоторого конечного множества, обладаю-
щего заданными свойствами. Каждое такое свойство опреде^1яег
некоторую конструкцию из элементов множества, называемую
комбинаторной конфигурацией. Здесь мы рассмотрим щххггейшис
комбинаторные конфигурации: размещения, перестановки, соче-
тания.
J 97CWf?H7bJ комбинаторики
Набор элементов из n-элсмсптного множества X ~
,	.-Лп}1 п G называется выборкой объема к из п члемен-
или (п, ft)-выборкой. Если порядок элементов выборки сущест-
вен Д-1Я ДЭ’,НОЙ задачи, выборка называется упорядоченной. Упо-
рядоченные выборки, отличающиеся только порядком элементов,
считаются различными. Если порядок элементов несуществен, вы-
борка называется неупорядоченной. Неупорядоченные выборки, от-
учающиеся только порядком элементов, считаются одинаковыми.
В выборках может также допускаться или не допускаться повто-
рение элементов.
Определение 1.2.1. Упорядоченная (п, к)-выборка, п € N,
fc G в которой элементы могут повторяться, называется разме-
щением с повторениями из п элементов но к. Количество таких
размещений с повторениями обозначается А*. Отметим, что, во-
обще говоря, к может быть больше п.
Пример 1.2.1. Номер городского телефона в Санкг-Пегер-
бурге состоит из 7 цифр Считая, что на любом месте может
стоять любая цифра, определите максимальное число телефонных
номсров.
В этой задаче рассматриваются упорядоченные выборки с по-
вторениями, то есть мы должны вычислить А|0. Для вычисления
используем принцип произведения Первая цифра номера может
быть любой из 10, то же верно и для всех остальных позиций,
поэтому число номеров = 107, го есть 10 миллионов.
В общем случае, применяя те же рассуждения, получаем сле-
дующий результат.
Предложение 1.2.1.
А* = п*, пеК к е N.
Определение 1.2.2. Упорядоченная (п, к)—выборка, n Е N,
к - 1,2,..., п, элементы которой по могут повторяться, называется
размещением из п элементов по к. Количество таких размещений
обозначатся А*.
Пример 1.2.2. Ощоделите число 7-значных телефонных но-
меров, все цифры которых различны.
Аналогично решению прошлой задачи замечаем, что первая
НИфра номера может быть любой из 10, но для второй цифры
имеем только 9 возможностей, для третьей 8 и так далее. Получаем,
io	1. Элементы комбинаторики
что Л{0 — 10 • 9 • .. 4 — 604ЯОО. Заметим, что э'го примерно в ]к
раз меньше, чем в предыдущей задаче.
В общем случае получаем следующий результат.
Предложение 1.2.2.
Л*=п(п 1)... (n - fc + 1) = - П' п е Н k = 1,2. п
(n - Аг)!
Пример 1.2.3. Сколькими способами можно расставить друг
За другом 7 оловянных солдатиков? Математическая форму-
лировка задачи; сколькими способами можно упорядочить п-
злементпое множество?
Очевидно, что мы имеем экстремальный случай предыдущей
задачи: число мест, на которые нужно расставить элементы, со-
впадает с числом элементов. Число (п, п)-выборок равно Л" = п!
Определение 1.2.3. Упорядоченная (п, п)-выборка. в которой
элементы не могут повторяться, называется перестановкой п эле-
ментов Количество перестановок обозна 1ается Рп
Предложение 1.2.3.
Рп =	= п!. п с N.
Пример 1.2.4. Сколько различных (необязательно осмыс-
ленных) слов можпо получить перестановкой букв слова МАТЕ-
МАТИКА?
В этом слове 2 буквы М, 3 буквы А, 2 буквы Т. Если бы все бук-
вы были бы различны, ответ был бы Рю = 10!, однако перестановка
одинаковых букв пе приводит к различным словам. Буквы М и Т
можно переставить 2! = 2 способами, а буквы А 3! = 6 способами-
Таким образом, ответ дается выражением - 151200.
Определение 1.2.4. Упорядоченная выборка, в которой со-
держатся элементы k типов, причем количество элементов первого
типа равно П|,..., элементов A-го типа пд,, и rq + ... + п* — я.
называется перестановкой с повторениями типа (n, fci,..., кп). Их
количество обозначается Р(п\,..., п*).
Предложение 1.2.4.
п?
Р(«1, ...,«*) = ——j-------I.
nJ • п2! •...  nfc!
j Элементы комбинаторики
11
Пример 1.2.5. Имеется 3 одинаковых приза, которые надо рас
ределить между 10 человеками. Сколькими способами это можно
сделать?
В этой задаче нужно пересчитать (10,3)-выборки, но, поскольку
гризы одинаковы, эти выборки нсунорядочены. Для того чтобы их
пересчитать, временно их упорядочим будем считать, что призы
различны. Тогда количество выборок дается вам формулой Л|0.
при этом, однако, из одной неупорядоченной выборки получится
3! = б упорядоченных. Таким образом, количество неупорядочен-
ных (10,3)-выборок равно 4^ = 120-
Определение 1.2.5. Неупорядоченная (п, fcj-выборка, в ко-
торой элементы не могут повторяться, называется сочетанием из
п элементов по к. Количество таких сочетаний обозначается С*
(В англоязычной литературе вместо С„ используется обозначение
Предложение 1.2.5. С„ —	~ п € N, к — 1,2 ... ,п.
Доказательство буквально повторяет решение предыдущей
задачи.
Пример 1.2.6. В буфете продаются пирожные 5 сортов.
Сколькими способами можно выбрать 3 пирожных?
Здесь речь идет о пересчете неупорядоченных (5,3)-выборок,
допускающих повторения. Предположим, чго у официанта, прини-
мающего заказы, есть бланк из 5 граф по числу сортов пирожных и
он ставит в соответствующую графу крестики по числу заказанных
пирожных данного сорта. Таким образом, заказ может быть зако-
дирован последовательностью из 4 палочек, разделяющих графы, и
3 крестиков, при этом выбор закат равносилен следующей задаче:
упорядочить 4 палочки и 3 крестика. Количество таких упорядо-
чений равно Р(4,3) =	== Су = 35.
Определение 1.2.6. Неупорядоченная (п,Л)-выборка, в кото-
рой элементы могут повторяться, называется сочетанием с по-
вторениями из п элементов по к. Количество таких сочетаний
обозначается С„.
Предложение 1.2.6. С* = %7и~|?г -	п 6 N> =
1	**	КДП— I j.	n i к t
2,... ,n.
Замечание 1.2.1. Часто по определению считают
Л" - Л" - Рп = С°п = С"п = 1, п С N.
12
1 Элементы комбинаторики
Это согласуется со всеми формулами, если считать 0* = 1.
1.3 Свойства	сочетаний. Бином
Ньютона. Кратные	суммы.
Производящие функции
Докажем некоторые свойства чисел С„, пользуясь комбинатор]
ны.ми соображениями.
Предложение 1.3.1.
пец А = 0,1,...п.	(1.3.1)
Доказательство- По определению. С„ это количество спосо-
бов. которыми из п-элементного мпожесгва может быть выбран< к
элементное нодмножес-гво, однако каждому такому подмножеству
однозначно соответствует (п — Л)-элсментное дополнение, таким
образом, (п — А:)-элемеитпых подмножеств столько же, сколько и
/п-элсментных, откуда следует доказываемое утверждение. 
Предложение 1.3.2.
Сп11 = Сп + Сп' \ п€Ц Jt = O,l....n.	(1.5.2
Доказательство. Выделим в п 1 1 элементном множестве А
какой-нибудь элемент (обозначим его 1). Все к4- 1-элемснтныс под-
множества А разобьем на два типа: содержащие* I и не содержащие.
В подмножествах первого типа одно место уже занято - па нем
стоит 1, осталось к свободных мест, па которые нужно поставить
п элементов, не равных 1, так что подмножеств первого типа С„
В подмножествах второго типа все к 4- 1 мест свободны, на них
нужно поставить п элементов, не равных 1. так что подмножеств
второго типа С„+1. Всего же к 4-1-элементных подмножеств п 4-1 -
элементного мпожесгва 0^1}, что дает нам требуемое равенство.

Предложение 1.3.3.
С*4- С*4-... |-С£ = 2". neN.
(1.3-3)
I Элсмснч
bi комбинаторики
13
Доказатсльстпо. Числа С%>€%,..., С*,... выражают ко-
чесгва 0 элементных, одноэлементных, ..., fc-элементных,
лИ подмножеств n-элементного множества А Таким образом, сум-
"ч даег количество всех подмножеств А. Докажем, что их число
2П Занумеруем элементы А числами от 1 до п Каждому
потмножеству А сопоставим строку из нулей и единиц следующим
образ м; на n-м месте стоит 1 если n-й элемент принадлежит
подмножеству. и 0, если не принадлежит. Это соответствие - биек-
ция Число строк длины п, элементы которых принадлежат 2-
элементному множеству {0,1}, равно А" = 2". 
Свойства 1.3.1 и 1-3.2 позволяют быстро вычислять числа С„
для небольших п. Пользуясь очевидными равенствами = С” -
1 мы записываем числа О'* в виде треугольной таблицы по сле-
дующим правилам:
1.	Строка с номером п состоит из п чисел.
2.	Первая строчка таблицы состоит из одной единицы, вторая
из двух единиц.
3	Первое и последнее число любой строки, начиная с третьей,
единицы, каждый из остальных элементов равен сумме двух чисел
предыдущей сцюки, стоящих над этим элементом.
Эта таблица известна как треугольник Паскаля2, Приведем
несколько ее первых строк.
1
1	1
I 2	1
13	3	1
1	4 G 4
15	10	10	5
1	6	15	20	15
1	7	21	35	35	21
1	8	28	56	70	56
1
1
6	1
7	1
28	8	1
Числа (7„ часто называют биномиальными коэффициентами
Действительно, их комбинаторная природа помогает быстро и сс-
2Блсз Паскаль известен, помимо работ и области математики, физики
” философии, как создатель (в 1642 г.) первых реально работавших
вычислительных машин.
14
1. Элементы комбинаторики
Блез Паскаль (I623-16C2)
тественно доказать формулу, известную иод названием бинол
Ньютона. (Бином - двучлен a + b.)
Теорема 1.3.1 Для любого п 6 Ко
(a + 6)n = ^Ckan~kbk.
Л-0
(1.3.4)
Доказательство. Рассмотрим степень (а + Ь)п как произве-
дение п одинаковых скобок a 4- Ь При раскрытии этих скобок
получается 2П слагаемых вида где к 0,... ,п. При каждом
фиксированном к количество подобных слагаемых an~kbk равно
количеству способов, выбрать из п скобок го к, из которых выби-
рается множитель 6. а это число равно Ск. 
Замечание 1.3.1. Общепринятая терминология не совсем
исторически справедлива. Формулу (1.3.4) для натуральных п
знали до Ньютона Блез Паскгыь, а еще раньше - среднеазиатские
I Элементы комбинаторики
15
математики, например Гийасэддип ал-Каши и Умар Хайям3. За-
<лу|<1 Ньютона в данном вопросе состоит в обобщении формулы
(1.3.4) «а любые вещественные показатели, при этом сумма превра-
щается в бесконечный биномиальный ряд. Заметим также, что
Г.В.Лейбпиц, создавший одновременно и независимо от И-Пьютона
дифференциальное и инте!ральнос исчисление, внес выдающийся
вклад и в комбинаторику. Его труд 1666 года "Рассуждения о
комбинаторном искусстве1' положило начало комбинаторике как
самостоятельной ветви математики. Известно также, что Г В.Лей-
бниц в 1671 построил работающую вычислительную машину |4’].
Исаак Ньютон (1643-1727)
Пользуясь формулой бинома Ньютона, можно вывести еще ряд
тождеств, связывающих биномиальные коэффициенты. Положив
«“6=1, еще раз получаем формулу
Cj’ + C* 4- ... + С" =2”.
'Известный математик и знаменитый поэт. Ранее писали Омар Хайям.
16
Элементы
комбинаторики
При a = 1, Ь — 1 получаем
с£-С’ + ...-г(-1)"С-=0.
Интересные тождества получаются при использовании комплот
ных чисел. Если a = 1, b = i, в левой части получаем
(1 4-i)n = (cos 4-1 sin	=2»(cos^+sin^). |
В правой части

Конкретизируя значение п и отделяя действительную и
часть, получаем различные тождества. Например, при
мнимую
п = 4Л
выводим
C?fc-^fc + ... + C« = (-l)fc22fe,
4-...-C# г=0.
Свойства сочетаний позволяют вывести формулы для степа
ных сумм.
Определение 1.3.1. Выражение
Sjt(m) = 1* 4- 2* 4- .. + mk
называется k-й степенной суммой.
Рассмотрим m-сочстапия с повторениями из п 4- 1 букв!
а, Ь, ..., х. Их количество равно = C£.tn. Разобьем и:
классы в зависимости от количества входящих гуда букв а. Есл1
к мест заняты буквами а, остальные tn — к занимаются буквам!
от Ь до х, это можно сделать С^~к =± С’\„* fc_, способами. Таки!
образом, получаем
4- С* 4- С2Н 4-... 4- С^т= С£т.
Заменяя п на п 4- I, гп па т ~ I и пользуясь свойством (1.3.1)
получаем
Q + С"+1 4- С£, 2 4 .. + С’”4гп' .	(1.3.5
] Э-’ff-менты комбинаторики	17
При п - 1,2.3 получаем
1 + 24... + ,„ = -2fcl+!),	(гз.6)
1-2, 2-34-..+„Hm+l)=’"(f"+^t-2),	(1.3.7)
О
1  2  3 4- 2 3 4 + ... + тп  (m 4- 1) • (m + 2) =
= m(m + I)(m + 2)(m + 3)	3
Первая из этих формул даст нам S|(m). Переписывая с|юрмулу
(1.3.7) как
о ..о	+ 1)(т + 2)
I2 + 22 + ... + m2 + 1 4- 2 + ... + т = —*----------
3
получаем, используя (1.3-6),
.2 , о2 ,	, -2	+ ОС”1 + 2) ™(™ + 1)
i г l -t- — -+ m —	-	 — —	—
m(m + l)(2m 4-1)
Аналогично из (1.3 8) и (1.3.9) получаем
1’ + 23+... + п? = ^Ц+1£.	(1.3.10)
Формула бинома (1.3.4) позволяет связать с последо-
ватслыюс1ью биномиальных коэффициентов числовую «функцию.
Подставив в (1.3.4) a = 1, Ь — х, получаем
/(х) = (1 4 х)п = 02 + С^х + ... + С^хк + ...+ С^хп. (1.3.11)
Таким образом, члены последовательности (Ск
фнниензами при zfc. Эт< подшХиг^Игй^^с^сд; ющему определению.
) являются коэф-
есгестввимо-матеизтичёосой
лигерапуры 
18
I. Элементы комбинаторики
Определение 1.3.2. Пусть дана последовательность (од). Ol
эс
разуем степенной ряд апхп. Этот ряд задаем функцию
п-0
оо
/(«) = ^апхП>
п-о
(1.3.12
определенную на облает сходимости степенною ряда. Такая фупк-1
ция называется производящей функцией последовательности од).1
Таким образом. (1 1 аг)” произв дящая функция для конечной
последовательности C*,fc = 0, .. ,тг. Понятие производящей функ
ции позволяет использовать для изучения последовательностей а?н
гебраические и дифференциальные методы. Например, из (1.3.12)
следует, что
ОД = —^-L> tigNo -NU{O}.
Пример 1.3.1. Пусть дано упорядоченное множество Л из н
элементов. Разобьем его на две непустые части так, чтобы одна из
них лежала целиком левее другой (например, А — (од,.... од) IJ
(од+1,... .од).) Потом каждую из частей делим па две таким жа
образом до тех нор, пока не получится п одноэлементных мно:
жсств. Назовем последовательность делений процессом. Скольк!
сущее, вует процессов разбиения?
Обозначим количество процессов разбиения (п+1)-элементной|
множества через Вп. Тогда Bq - количество разбиений одпоэлтч
ментною множества и Bq = 1. Пусть п > 0. На первом шаге (rt+1)-
элемептпое множество может быть разбито п способами: перво!
подмножество может содержать от 1 до п элементов. Разобьем
множество всех процессов А на п классов в k-w класс. Л* no-i
падут процессы, у которых па первом шаге в первое подмножестве
попадет к элементов. Подсчитаем число элементов в At- Так как!
в первом подмножестве содержится к элементов, дальше оп разби-
вается Bjt-i способом, вторая часть содержит п I-1 - к элементов!
поэтому разбивается Вп способами. По правилу произведения
Ик| = Bk-iBn к- как А = U ... U -4П, по правилу суммы
ВП = BqB„ 1 + /ЛНП г + ... + Яп jH0.	(1.3.13)
I Элементы комбинаторики
19
вместе с условием Bq = 1 мы получаем рекуррентное соотноше-
ние для последовательности (Вп). (Подробнее о 1>екуррснтпых со
отношениях см. дальше.) Поизводящая функция для последова-
тельности (Bfl) имеет вид
f(x) = Во + В\х + В^х2 4-... 4- Впхп 4 —
Введем функцию
Р(х) = х/(х) = Box + В\х2 + В2х3 + ... + Bnxn+I 4 . - -
и возведем ее в квадрат. Получим
Рг(х) = В&2 4- (B0Bi + BiВо)х3 + ...+
(ВоВп 1 + BtBn_2 4- — 4- Bn_iBo)xn 1 4- ...
Учитывая (1 3.13), получаем
В2(х) = В,х2 4- B2xs 4-... 4- Впхп 11 4-... = F{x) - х.
Решая квадратное уравнение F2(x) = F(x) — х, получаем F(x) =
v2~'lz (знак минус, перед корнем ставим, так как /’(О) = 0).
Раскладывая корень в биномиальный ряд [2], получаем
v/F-’to = (1 - 4x)i' = 1 - 2х - ~С^х2 - ..-^7C2nnxn+, - ...,
'	'	2 2	п F1 2п
отсюда
Ь (х) = х + ^х2 4 ... 4- -L-C2V"+i 4-...
Сравнивая коэффициенты при одинаковых степенях х, получаем
=	1 ptt
4 пч-1 '-'2п •
1.4 Упражнения
1.	В геральдике используетед б основных цветов. Сколько фла-
гов из трех юризопта-льных полос можно составить?
20
1. Элементы комби н аторик.
2.	Сколькими способами из 28 костей домино можно выбрав
две КОСТИ ТАК, чтобы их можно было приложит ь друг Я
другу?	I
3.	Сколькими способами можно расставить на шахматной	доев
две ладьи	
(а)	одного цвета;	I
(Ь)	разных цветов?	I
4.	Па загородную прогулку	поехали	92	человека. БутербродыI
колбасой взяли 47 человек, с сыром 38 человек, с ветчиной В
42 человека, и с сыром и с колбасой - 28 человек, и с колбасоВ
и с ветчиной 31 человек, и с сыром и с ветчиной - в
человек, все три вида бутербродов - 25 человек, а несколькВ
человек вместо бутербродов взяли пирожки. Сколько человЛ
взяли пирожки?
5.	Сколькими способами можно выбрать из полной колоды в Я
карты 5 карг так, чтобы	I
(а)	среди них было 4 карты одного достоинства (ка;>е);
(Ь)	все карты были одной масти (флеш);	]
(с)	достоинства карт шли подряд, например 5, 6, 7, 8, 
(стрит)?	1
б.	В студенческой группе 20 человек. Сколькими способам
можно выбрать craiMjcry. профорга и 3 равноправных членов
культкомиссии?
7.	Сколько различных слов можно получить, переставляя бук
вы слова КОМБИНАТОРИКА?
8	В некоторм государстве у всех жителей разные наборы зубов.
Каково максимальное число жи телей этого государства?
9,	Сколько ожерелий можно сделать из 7 разных бусинок?
I Элементы комбинаторики
21
j 0 Сколькими способами можно переставить буквы слова ОБО-
РОНОСПОСОБНОСТЬ так, чтобы две буквы О не стояли
рядом?
11.	Найти сумму четырехзначных чисел, записанных только
цифрами 1,2,3.
12.	Сколькими способами можно разменять 10 рублей монетами
в 10, 50 копеек и 1, 2, 5 рублей?
13-	На листе бумаги изображена сетка из п вертикальных и
п горизонтальных прямых. Сколько различных 2гг-звснных
замкнутых ломаных можно провести по линиям сетки так,
чтобы каждая ломаная имела звенья на всех горизонтальных
и всех вертикальных прямых?
14.	Сколько диагоналей в выпуклом n-угольпике? Сколько точек
пересечения этих диагоналей7
15.	На одной из двух параллельных прямых отмечепо 8 точек,
на другой - 11 точек. Найдите:
(а)	число треугольников с вершинами в отмеченных точках;
(Ь)	число выпуклых четырехугольников с вершинами в от-
меченных точках (три вершины четырехугольника не
должпы лежать на одной прямой);
(с)	число песамопересекающихся шестнадпатизвенпых
ломаных с вершинами в отмеченных -точках, звенья
которых не лежат на этих прямых;
(d)	число нееамонересекающихся десятизвенных ломаных
с вершинами в отмеченных точках, звенья которых не
лежат на этих прямых
16.	Доказать, что
(a)	Cj + 6C*+6C3 = п3;
(Ь)	14- 7С'п + 12С£ + 6G3 - (п + I)3.
22
2. Рекуррентные coothotjjchh.
2 Рекуррентные соотношения
2.1 Рекуррентные уравнения. При
меры
Определение 2.1.1 Последовательность (т„) будем пазы
вать рекуррентной, если существует функция к переменны;
f(x\такая, чю для любого n G No = N U {0}
^n+k = f (-&-П1 Sn+i,  • - > Я-п J-fc—1)-	(2.1.1
Если к - наименьшее натуральное число с таким свойством, будсь
говорить о рекуррентной последовательности порядка к. Условие
(2.1.1) будем начинать рекуррентным соотношением порядка к.
Само по себе 1>екуррснтное соотношение не задает последе»
вателыгость однозначно Наряду с ним необходимо задать начал*
ные условия - первые к членов последовательности ••->«*-1 • В
случае, если ставится задача нахождения формулы общего член!
последовательности, заданной рекуррентным соотношением, упог
ребляется термин рекуррентное уравнение.. Явно заданная после
довательиость, удовлетворяющая рекуррентному уравнению, на-
зывается решением этого уравнения.
В дальнейшем мы будем специально заниматься линейными ре-
куррентными шхгпсдовательностями.
Определение 2.1.2 Последовательность (хп) будем называть
линейной рекуррентной с постоянными коэффициентами (ЛРП),
если для любого n G Nq
Я-пЧ-к nl-£n+fc— 1 O2®n-^fc—2 Т- - - • Т	"i	(2.1.2)
где ai, .. ,а„ Е К, Ъп - заданная числовая последовательность.
Если Ьп = О, ЛРП назовем однородной, в противном случае неод
народной.
Уравнение (2.1.2), задающее ЛРП, будем называть линейным
рекуррентным уравнением (ЛРУ). Заметим, что однородное ЛРУ
всегда имеет решение хп — 0- Такое решение будем называть
тривиальным
Приведем примеры ЛРП.
7 Рекуррентные cool ношения	23
Пример 2.1.1. Геометрическая прогрессия
2	П
хи - а, X} = aq,x2 — uq ,.. -, xn = aq ,...
можег быть задана рекуррентным уравнением
х«+1 = <Fn. = «
Это линейное однородное рекуррентное уравнение nepBOi-о по-
рядка.
Пример 2.1.2. Арифметическая прогрессия
Хц = а.Х| = а + d, х2 = а + 2d,..., хп = а 4- nd,.
может быть задана рекуррентным уравнением
^п+1 = “Ь d, Хо ~ а.
Это линейное неоднородное рекуррентное уравнение первого по-
рядка.
Рассмотрим ЛРП, частным случаем которой являются рас-
смотренные в двух предыдущих примерах прогрессии.
Определение 2-1-3- Последовательность, заданная рекур-
рентным уравнением
xn+i = qxn +• d, zo = а,	(2 1.3)
называется арифметика-геометрической прогрессией. Очевидно,
при q = 1 получаем арифметическую, а при d=0 - геометрическую
прогрессию.
Основной задачей теории ]>екуррентно заданных последова-
тельностей является следующая: по рекур]>ент ному заданию по-
следовательности найти явную формулу общего члена Решим ее
Для арифметико-геометрической щхирессии. Будем считать, что
Ч / 1- Введем новую последовательность уп — лп-ц — хп, тогда из
11 = qxn 4-d, х„ ,2 = qxn 11 +d следует xn+2 ~xn > i = Q(T-n н —xn)>
то есть yn+| _ qyn, ПрИ этом уц = (g-l)a-pd. Таким образом, (yn) -
геометрическая прогрессия с первым членом j/o — г: = (g - 1)а 1 d и
знаменателем д, ее общий член у„ — cqn. Выразим теперь хп через
Уп. Имеем
1ft} *= Т] - То, У1 = Х2 - Xi, t/n-! = Хп - Т.„ Р,
. пил. ЫЛЛТИ/ШСЛ
складывая эти равенства, получаем
п -1
52 Ук = Тп - я0,
fc—О
откуда
хп = а + 52cqk = я + ((9 - О'1 + <f)~-7 = aqn +d- --
Сформулируем доказанный результат.
Теорема 2.1.1. Арифметика геометрическая прогрессия,
данная рекуррентным уравнением
х0 = а, хп+1 = qxn +d, q/l,
может быть задана явно в виде
п . Qn ~ 1
гп - а, хп = aq + d - - —- , n 1
9-1
(2.1.
Формула для арифметико-геометрической прогрессии мож!
быть обобщена.
Теорема 2.1.2. Пусти дана последовательность (хп)> зада
ноя рекуррентным уравнением
Хп+1 — а^Хп 4- бд,	(2.1.
где Оп,Ьп € IR,n € Pfe,Ti > по- Тогда
п-1	п—1	/	п—I \
*п = Zno	Пй*+ 52	I bfc	П °; I	’	С21'
fc—no	fc—по	\	j—k+l J
где, по определению, для любого т
т-1	т-1 / n 1	\
JJ afc = 1 и 52 /,fc . JJ Uj I = 0.	(2.1.
к—т	к—т \ J—к+1 /
2 Рекуррентные сосп ноше пня
25
Доказательство проводится по индукции При п — фор-
мула 2.1-2 верна, так как
*3-0—I	По -1 / Пф—I \
’ II °k + У? I hk IJ a J = х0  1 + 0 = х0.
к—п0 к—не \ j-k+l /
Предположим, что формула 2.1.2 справедлива для к = п, тогда
Жп+1
—	— Gn
п	п—I
= ’по  П «к + У2
к~По	к—Пр
п	п-1 / n	\	п
~' а’По ’ I I Ofc 5 у I bk J J Gj I + bn  | J aj —
к—no	к-По у	j=fc+l	)	j—n	11
n	n / n	\
= *n0 П °*+ 52 Ib* • П аз I 
k—n0	k—no \	]—fc+1 /
В частном случае, когда un — а для любого n е Flo и по = О,
получаем
п—I
= хоап + У2 * Ьк
к-0
(2 1-8)
Пример 2.1.3. Па сколько частей разбивают плоскость п пря-
мых в общем положении (любая пара прямых пересекается, ника-
кие три прямые по пересекаются в одной точке)?
Решение Обозначим количество областей, образуемых п
прямыми, через хп. Очевидно, хо = 1 Прямая с иомены п + 1
ресскаск^г со всеми п прямыми и делится точками пересечения
на п4-1 часть, каждая из которых делит какую-то часть плоскости
на две, поэтому возникает п + 1 новая область, отсюда xn+i —
Лп + 7i 4- 1 Решая это уравнение по формуле (2 1.8) и используя
26
2. Рекуррентные соотпоиген
(1.3.6), получаем
п-1 I	п— 1 \	п—1
= 1. 1п + £ (fc +1) п 1=1 + £(fc +1) =
fc=O \	j—k+l J	к=0
, n(n+l) n2+n + 2
Пример 2.1.4. [4] Рекуррентные уравнения естественно в
н икают в задаче радиолокации. Антенна радиолокатора излуч;
узкий пучок электромагнитного излучения. Если -ши пучок вст
чает на своем пути некоторый объект (цель), часть его энерг
отражается и регистрируется антенной. Таким образом, сам ф<
получения отраженного сигнала в некото1юм направлении евн
тельствует о наличии в этом направлении цели. Для определен
расстояния до объекта нужно измерить bjximb между носылк
импульса и приемом отраженного импульса. Однако здесь ос
ряд трудностей. Энергия единичного импульса мала, его труд
зафиксировать на фоне естественного шума, причем для точно
определения расстояния импульс должен быть как можно коро«
Один из способов решения этой проблемы посылать длинпч
серию коротких импульсов гак, чтобы сравнение с отраженны
сигналом происходило бы однозначно. Для этого строится период
ческая последовательность импульсов с очень длинным периоде»
Поскольку пас интересует только наличие или отсутствие сигн
ла, будем использовать двоичную систему счисления с обычны»
правилами сложения и умножения, в частности 1 + 1=0 (без пер
носа в следующий разряд). Множество {0,1} с такими операция»
обозначим /*2.
Пусть дан сигнал длины гп, а = (ao.ai,...	о, е /
Сопоставим ему бесконечную рекуррентную последовательное
порядка m
Si+i = ‘«Si +QS, i+--•+cjnsi m, x m,c, e Ег.цэ.Ст / 0 (2.1.
с начальными условиями
«о = Ofl, «I = «1,. . - , Sm 1 = Птп-1 -
) рекур!>ситиые ('оотпотпсния
27
,чп) ПРР11
юр 1-2-2)
2.1-9)
[Оско;п>ку с> — 0 или 1. легко доказать, что последовательность
щична. По аналогии с производящей функцией (см.
рассмотрим характеристический многочлен уравнения
с(х) = сахт + Cix’7’-1 + ... + Ст-	(2.1.10)
'1елукипам тещжма дает достаточное условие для того, чтобы
нфцод последовательности (2.1.9) был достаточно большим.
Теорема 2.1.3. Пусть многочлен вида (2.1.10) для последова-
псльпости (2.1.9) делит х2"' 1 и не делит никакого х1 — 1 при
< 2*” — 1. Тогда период (21 9) равен 2™ — 1.
Последовательности с таким свойством называются последо-
{ютелъностями максимального периода. Например, многочлен
с1 1- х3 + 1 (над Ft) делит х15 — 1, но не делит ни один xk — I при
I < 15. Этот многочлен соответствует уравнению .9, + я,_з 4- Si-t
Найдите решение этого уравнения с начальными условиями 1000 и
Убедитесь, что это решение имеет период 15.
Для сравнения посланного и отраженного сигналов исполь-
Вуегся авнигьорреляционная функция
1 Г-1
(2.1.11)
г i-o
где s(j) рекуррентная периодическая последовательность а г
ее период. Рассмотрим простейшую последовательность с периодом
1> 3 - kr,
0, j -£ кг, А: 6 ГЧо
«дин импульс па период Для этой последовательности
A( J ”> > = АГ’
Л(у) = < Г
( 0: j^kr,kE^.
Если отраженный сигнал Sq является точной копией посланного
сигнала я0 с задержкой d, тогда s(j) = s*(j — d). Для дизъюнкции
so .'Sq Л (ji) -Jl 0 только при j — kd, к C это позволяет ощжделип.
’адержку d и jjhcctohiihc до объекта.
28
2 Рекуррентные coothoijichi
Замечательное свойство последовательностей максимально
периода состоит в том, ч то их автокорреляционная функция имея
тот же вид, что и у последовательности «о "один импульс J
период" Автокорреляционную функцию определим несколько п<
другому
Теорема 2.1.4. Пусть	множество послсдовател
костей максималыюго периода над Р^, задаваемых многочлена
/(х) степени п. Определим
2“-!
A'(j) = B(si + si+j)> где = +1,В(1) = -1.
i-0
(Здесь +1 к — 1 рассматриваются как вещественные числа.) Том.
АЪ =12П 1^ = к(2П~ G
I 0, 3 / *(2" - I).
Для однозначного определения расстояния нужно, чтобы псрис
был больше, чем возможное значение d. Системы связи со сну*
никами используют многочлены степени 50. которые дают перис
250 -1к IO1S. При передаче Ю6 импульсов в секунду период будс
порядка годя.
Введем несколько функций, сопоставляющих вещесгнеппы
числам целые.
Определение 2.1.4. Целой частью числа х G R (обозначена
[а:]) назовем наибольшее целое число, не превосходящее х.
[т] — max{к 6 Z : к х}.
Например, [15] = 15, [тг] — 3, [—1.5] = —2. В англоязычно
литературе данная функция именуется нижней целой частью
обозначается [х].
2 Рекуррентные соотношения
29
Определение 2.1.5. Верхней целой частью числа х G R
(обехшачепне [я:]) назовем наименьшее целое число, большее или
равное х
[з:] — min{fc е Z ; к > х\.
Например. [15] = 15, [я] =4, |—1,5] = —1.
Рис. 2.1.2. График функции у = |д]
Очевидно.
г 1 _ / х € Z
И UxJ + l.zgZ.
Пример 2.1.5. Задаваемый осциллятором стандартный сигнал
с периодом I (см. рис. 2.1.3) можно описать как график функции
30
2. Рекуррентные соотпошенн
Уо = х — [т]1 называемой дробной частью х. Если же мы хот
задать сигнал с. произвольным периодом о > 0, его можно щждс
вить как график функции
( {х 1
Ух = « Уо + о
V \а 2
= а
х
а
2
(см. рис. 2.1.4).
Рис. 2.1.4. График функции у.
Пример 2.1 6 Функцию
у(*) -
0, J С Z
1. х 4 Z
2 рекуррентные соотношения
31
ножно описать как у - И ~М (™ РиС 21 5) (Это характеристи-
-к гя функция множества нецелых чисел (см. приложение 1)).
Рис. 2.1.5. График функции у = ].т| — [.т]
2.2 Линейные рекуррентные урав-
нения
Перейдем к изучению общих cboJicib решений линейных рекур-
рентных уравнений (ЛРУ). Ограничимся подробным изучением
ЛРУ второю порядка, так как все существенные черты данной
теории могут быть показаны для этого случая
Теорем i 2.2Л. Если последовательности (а„) и (Ъп) - реше
•>шя однородного ЛРУ
^п-2 = Р^п+1 + q^n,
(22.1)
та для любых констант С\, С’г С К последовательность (с^), где
Сп — ClOn +
(2.2.2)
таклсе будет решением (2.2.1).
Доказательство. Сп+2 — G ап+2 -г ОгЬп+2 — СЛ (pun-i + qan) +
'2(рб +l pgbn) =p(C1on+}+C2hnil)+q(C1an+C2bn) - pc,,, i
Определение 2.2.1 Выражение C|Un + С'г^п называется об-
решением уравнения (2.2.1), если любое решение этою урав-
ие.ния имеет указанный вид для некоторых значений консгант С| и
32
2. Рекуррентные соотношен
С-i- Другими словами, для любых начальных условий хо — а, Х| Я
0, а,0 6 К найдутся единственные значения констант С, и I : I
такие, что последовательность С{пп + С’£ЬП является решсниецЯ
(2.2.1), удовлетворяющим начальным условиям.	
Будем искать решение (2.2.1) в виде хп ~ tn,t / 0. П д|
подстановке папу чаем t*H2 =p(n+l +gt", откуда tn(t? ~pt~q) = J
Получаем, что для любого ненулевого решения (2.2.1) вида хп =
t должно быть корнем уравнения l2 — pt — q — 0 и для любого корцЛ
этого уравнения to последовательность ап — t" является решением!
(2.2.1)
Определение 2.2.2. Уравнение
t2 - pt - q ~ 0	(2.2.3 
называется характеристическим, уравнением для уравнения
(2.2.1).
Предложение 2.2.1. Последовательность (хп) : хп = ('“
является решением уравнения (2.2.1) тогда и только тогда ког«3в
t - корень характеристического уравнения (2.2.3).	I
Очевидно, возможны три варианта в зависимости от знака!
дискриминанта уравнения (2.2.3).
Теорема 2.2.2. Если уравнение (2.2.3) имеет 2 различный
вещественных корня t\ и fa, общее решение уравнения (2.2.1) иле -в
ет вид	I
xn = Cyt™ + C'zt”.	(2 24 l
Доказательство По предыдущей теореме любая последовав
гельность вида (2.2.4) удовлетворяет уравнению (2.2 1). Д кажем!
теперь, что при любом выборе начальных условий t.q — а, Х\ — i
система уравнений
J Ci + Сг = а
( C’jtj f C‘zt2 — b
имеет единственное решение, но это очевидно, так как опредЬ
литсль системы
’ ] - t2 - ti / 0. 
и t2|
Пример 2 2.1. Рассмотрим задачу, которую приводит в вы-
шедшей в 1202 году кише "LilxT Abaci" итальянский матсматш*
Леонардо Фибоначчи
2 Рекуррентные соотношения
33
"Пара кроликов приносит pa t в месяц приплод из двух кроль-
чат (самки и самца), причем новорожденные. крольчата через два
месяца после рождения уже приносят приплод. Сколько кроликов
появится через год, если в начале года была одна пара новорожден-
ных кроликов?"
Леонардо Фибоначчи (1180-1240)
Обозначим через fn количество пар кроликов в начале п-го
месяца. Тогда /0 — 1, /j — 1, /2 — 2 (у самых первых кроликов
родилась еще одна пара), /з = 3 и вообще
In — fn— I 4" fn -2-
°с-1едоватсл1.посгь, заданная этим рекуррентным уравнением
начальными условиями /и — 1. Ji =1, называется по-
Слсдоватпслъниспгью Фибоначчи. Характеристическое уравнение
имеет вид t'2 — t - 1 — 0, его корни fli2 = поэтому общее
34
2. Рекуррентные соотношу
решение имеет вид
Для определения констант имеем систему уравнений
Ci+ 0’2 = 1,
Решая ее, получаем Ct = &=i, С-2 = В итоге падуч?
(формулу Нине для чисел Фибоначчи. назва1шую так в честь фр
цузского математика Жака Пине, получившего этот резулыа
20-х годах XIX века.
(2.2
Числа Фибоначчи имеют множество интересных свойств |
Докажем одно из них.
Предложение 2.2.2.
5? А = /п+2 - 1-
к-0
Доказательство. Запишем основное уравнение как Д [ 2
fkj-\ = /к и подставим вместо к числа от 0 до п. Получим
А — А — /о
/з - /г = /1
<
/п+1 ~~ /п ~ /п-1
. /п+2 — /п+1 = fti •
Сложив, получим Х2Г-оА = /п+2 ~ /ь учитывая, что /j =
получаем требуемое. 
Q pCKYPl^lnHble соотношения
35
Жак Бине (1786-1856)
Теорема 2.2.3. Если уравнение (2.2.3) имеет 1 вещественный
корень t 0. то общее решение уравнения (2.2.1) имеет вид
Xn = C\tn 1 С2ШП	(2.2.6)
Доказательство Очевидно, последовательность (й„) : an = t"
довдетворяет уравнению (2 2.1). Докажем, что эго верно и для
. bn = nf.n. Гак как t - корень кратности два многочлена t —
rt~(l - 0, 1 является также корнем его производной 21—р. Поэтому
^n+2 — p&n+1 — qbn = (п 4- 2)tn+2 — p(n + l)tn+I - qut" =
- i InL4 + 2t — pnt - pt — qn) = tn(n(t2 - pt — q) 4- t(2t — p)) = 0-
По теореме 2.2.1 xn будет решением (2 2 1) При любом выборе
начальны.х условий то -- а, ху = Ь сисгема уравнений
— а
см + с^. - Ь
36
2. Рекуррентные соотнотпсл
имеет единственное решение, так как определитель системы
1
I
О
I
= «#0
в рассматриваемом нами случае. 
Теорема 2.2.4. Если уравнение (2.2.3) имеет 2 комплексна
корня t|;2 = a ±/3t, где (3 то общее решение уравнения (2.21
имеет вид (далее т = у/а24- ff2; <р — argtj):
хп = тп(С\ cos п<р 4- С2 sinny>).
(2.2.1
Доказательство. По предложению 2.2.1 ап ~ t" — r"(cosny>
isinrr/>) и bn —	— тп(саишр - isinn^) будут решениями (2.2.1
поэтому Сд = |(оп + Ьп) = rncosn<p, dn = i(an — bn) = rnsmr|
и xn = 6’i cn 4- Ctdn также решения (2.2.1). При любом выбо,
начальных условий zo = a, xi — b система
г(С’| cos <р + С-2 sin tp) — b
имеет единственное решение, так как определитель системы
1 О
г cos <р г sin <р
= г sin ip = Р О
в рассматриваемом нами случае. 
Для решения однородного ЛРУ порядка к, к > 2 применяв^
сходную технику. Так же доказывается, что ненулевое {юшени
вида (zn) = (tn) возможно, только если t - корень характерист*
четкого уравнения. Так как многочлен порядка к с вещественным
коэффициентами раскладывается в нроизведенне вещественны
линейных и квад!»атичпых множителей |2] мы сводим задачу 1
уже рассмотренным случаям уравнений первого и второго порядк!
Приведем решение для простейшего случая.
Теорема 2.2.5. Пусти
Tn+jt —	। fc_i 4-... (- а^хп
(2.2..
7 Рекуррентные соотношения
37
Qpy 7юрядка и характеристическое уравнение.
tk -a\tk~' - ... - а* =0
iMeern k различных вещественных корней	Тогда общее
,ешсние ЛРУ ьмвеи вид
хп = ЭД + ... Ч Ckl%.	(2.2.9)
Доказательство В доказательстве нуждается лишь то. что
и1Я любого выбора начальных условий xq = бд, зд — 6( ..
:* 1 - bfc 1 найдутся константы Сь.R, такие, что (2.29)
довлетворяс! начальным условиям. Определитель соответствую
дей линейной системы что определитель Вандермонда, равный
Kt, — tj) 0. так как все корпи t, различны 
Возможен и другой подход к понятию общего решения рекур-
рентного уравнения.
Определение 2.2.3. Рассмотрим т последовательностей
Jn)i (xn)j-   • (Т™У Будем говорить, что эти последовательности
аинелЬю завистны, если существуют такие постоянные С\,... ,Ст,
i№ вес одновременно равные нулю, что для каждого п € No выпол-
няется равенство
Cl Т.; + С’2Х* + . .. + СтХп = 0.
(2.2.10)
Б противном случае ноеледователыюсги (ж„), (гг^),..,, (xJJ1) пазы
Ьаются линейно независимыми.
Приведем критерий лилейной независимости последовательно-
стей.
Определение 2.2.4. Рассмотрим
(хп)- (т'п),.... (х”1). Матрицу
ш последовательностей
Ti-i	4 и
V’i+m-l хп+т-|
(2.2.11)
г,>дем называть мат^уицей Kaxopamu. Определитель матрицы Ка-
,0Рв1ц будем называть определителем Казорати
40
2 Рекуррентные coothowchj!
2 корень характеристического уравнения кратности 1, поэта
ztl = Ап2п, где число Л пока неизвестно. Отсюда
zn+1 = Л(п + 1)2’*’', zn+2 = Л(п + 2)2"’2,
подставляя в уравнение и приравнивая коэффициенты при од
паковых степенях п, получаем А = отсюда z„ =
окончательно
х„ = С12"+С2(-4)" + 1п2".
2.3 Сравнение роста и убывани
последовательностей
При изучении решений рекуррентных уравнений часто bosi
каст необходимость их сравнения. Приведем некоторые к л ас,
ческие определения из математического апализа.
Опрсделение 2.3.1. Рассмотрим две последовательности (з
и (уп), такие, что уг, - 0 пс больше, чем для конечного чис
значений п е 14 Последовательности (агп) и (уп) называются .
бивалентными ((хп) ~ (уп)), если liiii £= = !.
п-><ю »»
Пример 2.3.1. Пусть (з?п) некоторое решение рекуррентж
уравнения, хп -> 0. хп / 0 и
уп ~ sin 2жп
также решение этого уравнения, тогда
11Ш -j------------------------- = 1,
п-»ло ‘ зш2гп
следовательно, (х„) ~ (уп).
Определение 2.3.2. Пусть две последовательности (хп) и (у,
таковы, что j/n — 0 не больше, чем для конечного числа зпачени
neN, и lini bi = 0, тогда говорим, что (хп) является бесконеч
п—>эо
малой относительно (j/n), и пишем (хп) = о(уп).
Чаще всего это обозначение применяется в том случае, ког,
обе последовательности стремятся к нулю. В этом случае говор»
что (хп) бесконечно малая более, высокого порядка, чем (уя).
2 рекурР^соотношения
41
П имер 2.3.2 Пусть (лп) - некоторое решение рекуррентное
уравнения, *. -> »•	* 0 ” <»"> гда
Уп = (arctg.rn)5
!^кжс решение этого уравнения. Тогда
..	v хп п
h m - —	—г = Ini —— = О
п *гс (arctg.rn)» ” >му*п
Следовательно, (хп) - о(?/п).
Будем теперь рассматривать положительные последова
тсльпосчи.
Определение 2.3.3. Пусть две последовательности (хп) и (?/п)
таковы, что существует постоянная С > 0, такая, что начиная с
некоторого номера хп < Суп- тогда юворим. что (zn) является
ограниченно?! относительно (рп), и пишем (хп) = О(уп)-
Например, (2?12 4- Зп - 3) — О(п2), так как легко покатать, что
2п2 4 Зп — 3 < Зп2 для всех п G N
Замечание 2.3.1, Хотя в записи (тп) = О(Уп) применяется
знак равенства, мы должны его рассматривать как своеобразный
знак включения. Например, запись (n^/h) = О(п2) правильна, в
то же время запись О(п2) = бессмысленна. То же самое
относится и к записи (хп) = »(?/»)• Для корректного использования
данных выражений следует помнить, что в соотношениях, содержа
щих О(]/п) или о(уп), правая часть содержи! меньше информации,
чем левая. Например, в цепочке "равенств", рассматриваемых при
х -> оо,
®	1 Л(1 \	1	/Л
---- = 1+ -4-О(-7)=1 + - + о(-)=1 + о(1)
х — I	х \х*)	х	\х)
ип^юрмация убывает в направлении слева направо.
Обозначения (хп) = О(уп) или (/(п)) — О(р(п)) используются
па практике только тогда, koi да функция д(п) более простая, чем
функция /(п), и не растег стишком быстро по сравнению с /(п)
Иначе говоря, функция р(п) должна хо|юшо передавать характер
P<>cia функции f(n) и являться ее очень близким верхним ограни-
’*итеяс<м. Например, следующие математически корректные утвер-
л<делия на практике не применяются: (п2) = O(nJ 4- п2 1п?г + 6683)
илИ {t-«)	О(„2)
42
2. Рекуррентные сосгпкплоЛ
Для того чтобы функции f и у росли с одинаковой скор< П1
потребуем. чтобы выполнялись оба условия (/(и))
(.'/(«)) - O(fin)).
Определение 2 3 4 Если существуют постоянные С| > I
('2 > такие, что начиная е некоторого номера выполняется,»
Уп С’2ачн	I
i-оворят, что последовательности (хп) и (у„) имеют один поряи
обозначим эю (in) ~ (уп)-
Можно привести щюстое достаточное условие для того чг<
(xn) X (i/n)-
Предложепие 2.3.1 Если существует конечный
liin — # О,
« >эо?/п
УТЮ У/п	I
В этом случае говорят, что хп = О*(уп)- Заметим, что тп1
О (,Vn)	^ Уп-
Пример 2.3.3 Дон«-тим f(n) является суммой нееколыв
ата1яемых, одно из которых при больших п существенно болыЯ
чем остальные. Если обозначить через </(п) это " доминирующее
слагаемое, получим (/(«)) = О*(д(и)). Например, если /(п)1
произвольный полипом степ<чш d с положительным старшим id
эффициептом «о, то (/(»*)) = O*(«<jnrf). Одночлен й(\иЛ яв.1яем
"доминирующим" Слагаемым.
Если для данной функции f(n) найдем хорошую оценку дт]
едкую, что (/(п)) = О*(</(л.)), можно использовать функцию 1
чтобы понять, как ведут себя значения функции /(п) при болыня
л. Если (/(»<)) = О*(п), можно сделать вывод, что если аргумент!
увеличить в два раза, то значение функции /(о) также, примере
удвоится. Если (/(п)) = О*(п2), то при удвоении аргумента зм!
чение функции f(n) увеличится примерно в четыре раза. Ес.'^
(/(т0) = О*(2"), ю при увеличении и на 1 величина /(п) возраеЛ
примерно вдвое.
Наиболее интересным частным случаем отношения (/) “ ;/
является отношение (/) ~ (у). В этом шучае говоря i. что f aenMil
ютнческп равно у. В частности, если f(n) многочлен crenenj
рекуррентные соотношения
43
d с коэффициентом «о / О при nd, то (/(n)) ~ (aond)- Другим
примером является следующая теорема.
Теорема 2.3.1 (П-ЛЧебышёна о распределении простых
чисел).
/ п \
где v(n) - число простых чисел, не превосходящих п (п G ГМ).
Пафнутий Чебышев (1821-1894)
Приведенные выше символы часто применяются не сразу после
знака равенства, но внутри более сложных формул. Если говорим,
например, что некоторая функция имеет порядок П(°|п,п")1 это
значит, что существуют такие константы С > 0 и по, что при
п «качения функции не превышают nf',nlr”1. Если говорят.
4jo функция имеет порядок п0’^1), это значит, что для достаточно
>ч.'1Ыиих п значение функции находи гея между двумя фиксирован-
ными степенями п.
Пример 2.3.4 Пусть с означает произвольную положитель-
ную гиютоянную малую величину (например, £ — 0.001). Тогда
44
2 Рекуррентные соотношу
(Inn) = О(пс), более того. (Inn) = o(nc). Чтобы подтпсЛ^жа
вычислим значения функций Inn и п£ для очень больших значей
п. Вычисления становятся особенно легкими, если п будет сгепси
числа 2. Например, если п = 2lutJ00tJ(J, го Inn = 1 000 0(‘Ю In 2i
693147.18, в то время как число П6 = 21Мо имеет в десятина
разложении 302 цифры.
Чтобы получить доказательство этого факта, достаточно ш
меншь нрэдило Лопнгаля для вычисления
1*1 п
lim ----— О
П—W: пс
Пример 2.3.5. Пусть J(n) означает число цифр, необходим
для записи числа п в позиционной системе с основанием Ь. Заф)
сируем b и будем считать п переменной величиной. Toi да
f(n) - 1 + [log6 nJ = 1 I
In n
hiT
Поскольку b а значит и In b постоянны получаем (/(г?)) = О* Innl
Таким образом, функция "число иифр"всдс1 себя прибли ятгельм
как лшарифм
Следующий пример показывает, насколько важно различи
между переменной и постоянными при использовании обозначаю^
О, о.-.
п
Пример 2.3.6. Рассмотрим сумму J3 степеней первых!
i~1
натуральных чисел. Если зафиксируем k и позволим « неогранй
четшо расти то постучим
(2.3-1
п
Чтобы это доказать, достаточно показа! ь. что jpvr/(n) —	52 (и)1
1-1
1	I
будет ипгегратьной суммой для интеграла / xkdx — j^-p. откуда
>|	1
9 РСКУР^'111'1^0 С(>т1ЮШ€НИЯ
45
что lirn ® = 11 ,ДС -/(п)	Олиако еСПП 3афИК'
И будем считать А- переменной, схремящсйся к бескопеч-
cnpvcM^« "тверЖл1СцПе (2.3.1) будет неверным. Например. при п = 2
ноем jyjpjjQBiulO бы. что
из него
что очевидно, неправда. Ложным является и более слабое yrnejx
ждение
Приведем некоторые следствия утверждения (2.3.1):
- важные частные случаи;
(2.32)
Г 1=<Хп*).	(23.3)
\ к + 1 I
\l— I	/
Замечим.что (2.31) и (2.3.2) содержат в точнопя одну и ту же
информацию, а (2 3 3) является несколько более сильным утвер-
ждением . Соотношение
О(гЛ-’)
(2.3.4)
16
2. Рекуррентные соотношец
еще сильнее. так как оно содержит второй член асимтиотичеси
т*
разложения J" ik при и -> ос. Дли получения этого аси
г-1
логического равенства необходимо исследовать порядок роста i
ноеги
пк+1 пк
Г+Т “ У
Индукцией но к можно показать, что эта разность равна
О(пк 1
Повторяя эти рассуждения, получаем с каждым разом новую
формацию относительно исследуемой величины.
Определение 2.3 8 Выражение, сцуДг) h <:2рг(г) + - иг
наегся асимптотическим рядом для f(x) при т -> Хц (занисып
к;
/(х) ~	С|р|(х) при X » -То),
I-1
если fl1+l(x) = o(ft(x)) при х
•> Ясь и для каждого п
п	\
/(*) 5? WA*) I - w(.9n(^)) при х - > х0.
i-1	/
Асимптотический ряд не обязан сходиться. Например, ряд
(2.3.
является асимптотическим разложением для
при х -> ос. однако этот ряд расходится при любом х. Это nd
должно удивлять- гак как с точки зрения сходимости мы исгледуеЦ
поведение частичных сумм при фиксированном х ип -> ос. 1
рекуррентные СОО1 ношения
47
л зрения асимптотики исследуем sn(x) при (фиксированном
с точки	расходииций<.я асимптотический ряд
П Я £	Х0- га

обычно можно использовать для хорошей аппроксимации f(x) при
t Xq если х достаточно близок к Хо и момент окончания
сумм»ц>ования выбран верно. Например, используя ряд (2.3-5) для
приближенного вычисления функции
/(х) =
с точностью 10 \ можно считать, что х = 10 достаточно близко к
х0 = |-эо. Частичная сумма
1,1,2	6	.	24	.	120
io + юо 1 Тооо + юооо + юоооо юооооо _ 0,11296
даст подходящую аппроксимацию для /(10) ~ 0,11306
Одним из наиболее известных применений асимптотических
методов являйся знаменитая формула Стирлинга* для фактори-
алов:
(n!) ~ I х/2тгл ппс~п ) при п —> оо
2.4 Асимптотические решения ре-
куррентных уравнений. Форму-
ла суммирования Эйлера
Определение 2.4.1 Пусть дано линейное рскур{>ептное урав-
нение с постоянными коэффициентами вида
*n-fc - nixn+k-1 + ... + од-хл + Ьп, п С No-	(2.4.1)
Фактически эту формулу выпел в 1729 г. де Муаир из ас.имптити
,,x'Koixj ряда Стирлинга, дающего разложение 1п(п!).
4«
2. Рекуррентные сослношгг,
тогда если решение (х„) уравнения (2.4.1) имеет вид
хп = т. ( для всех п €
то решение называют стационарным-,
если решение (хп) уравнения (2.4.1) удовлетворяет условию
lirn xn = j, in x.	12
n ->OG
где J/» — i (для всех n € No) стационарное решение, то рейл
(хп) называю! асимптотически стационарным.
Пример 2.4.1 Уравнение
х>и 1 = ахП | b, а ± 1	(2.4
имеет стационарное решение вида
b
’-“i =	р»
(Если а = 1 и 6 / 0. то (‘тационарного решения не существует.)]
Замечание 2.4.1 В приложениях стационарное решение мо
по интерпретировать как положение равновесия, которое в nod
дующем ис .меняется.
Пример 2.4.2. Рассмотрим подробно уравнение (2.4.1)
Тп+1 = ахп + Ь, а.Ье№.
Ес.ш п / 1 н х0 / х, го решение, "crajnyjoiiicc" от .т0, имеет вид
хп = (®0 - *)«” 4 2-
Очевидно, 11осле.4ова1ел1.иосгь (хп) имеет конечный предел ра
ный х. только при |«| < 1. При >том, если 0 < ц < 1. решен!
убывает при Хр > х и рас ют при .г0 < т. Если I < « <
го решение |акжс будет асимптотически стационарным, оно буда
колебаться около значения х. постепенно приближаясь к а?. Таки
образом, при < 1 хп х —> 0. В оста.п>пых случаях решение <
будет аенмнготически шанионарным. Если а < 1. го нослсдо.
тельце,сть (jn) ко.1еблсгся около начального значения
iioriciienri
9 РсК.УРРси111Ь1(- <™)ТНОШСНИЯ
49
него удаляясь. Если же u > 1, то решение растет неограниченно
,уГ Жс у ± и неограниченно уменьшается при .то < i. При |о| > 1
Кдеем (х'п) ~ ((^о -^)«п)> таким образом, при >а| / 1 мн шьтучаем
хРрОп1ук> асимптотику решения, при больших п приближающую
его сколь угодно точно.
Пример 2.4.3 В формуле Бине (2.2.5) для последовательности
стремится к нулю при п —>
Фибоначчи второе слагаемое
□О, поэтому
(*п)
1 (1 + V5
7Й 2
отсюда при больших п отношение
« 11	~ 1,618034.
х„ 2
Например. ?Q“ = Ц = 1,61818 . Это дает возможность при-
ближенного вычисления числа <р = 1 Заметим, что это
число известно как постоянная золотого сечения. Считается, что
прямоугольник с таким отношением сторон — самый красивый из
всех прямоугольников. Применение данного метода приближенных
вычислений см. в унр. 2.5.6.
На го, что lim существует у целого класса последовазель-
п—»оо Тн
постен, обратил внимание в 90-е годы XIX нека А.Пуанкаре.
Определение 2.4.2 Пусть дало линейное рекуррентное урав-
нение с переменными коэффициентами вида
xn_fc = ai(n)xn ।k j + ... + аь(п)хп + bn, n c No, (2.4.5)
причем Существуют пределы lim щ(п)=о,,	Л, lim bn = b.
-	'	n—toe	n »oo
Ьлда будем говорить, что уравнение (2.4.5) обладает свойством
Пуанкаре.
Теорема 2.4.1 (Пуанкаре, 1885). Если у]>авнение (2.J,.5), где
= 0, обладает свойством Пуанкаре и если корни уравнения
Afc-O;Ak 1
. — щ = 0
50
2. Рекуррентные соотношещ
удовлетворяют условию
|А|| > |А2| > ... > |А*|,
то для каждого нетривиального решения (хп) найдется такое I
{1,..., А:}. что
lim ^=±1 = А,.
п->ос хп
Анри Пуанкаре (1854-1912)
В 1921 году О.Перрон усилил теорему Пуанкаре.
Теорема 2.4.2 (Перрон. 1921). Если выполнены все уело»
теоремы 2-4-1, при этом а,(п)	0 для любого п € N и любе
i € {1.. -,А:}, то существуют k линейно незавнеимых решен
уравнения (2-4-5)
(х^):....	: Пш 211.1 _ д ] к
л-юо ._(ч
Рек урр^'НТНЫС соотношения
51
Пример 2.4.4 Пусть даны уравнения:
1	п + 3	2
а) ТЛ4-2 = ^п+1 + Хп; ») хп+2 —	д_ 9:Гп+1 —
Эти уравнения обладают свойством Пуанкаре. Действительно,
lim = 0, lim -	= 1 и lim ----- = О,
п ->ооп n-юс п + 2	n-юо п + Z
пила, согласно теореме 2 4.1, имеем в обоих случаях одно и то же
характеристическое уравнение
А2 - А = 0.
Корли этого уравнения А] — 1. Аг = 0. По теореме 2.4.2 у обоих
уравнений есть 2 решения (а:„) (х„): JLin^ *’*’ = 1,	= °-
Можно проверить, что для уравнения Ь) = „т Для нахождения
(i’n) воспользуемся следующим предложением.
Предложение 2 4 1 Если (хп) - решение уравнения (2.4.5)
и lim	0. то zn = А"еп*'", где (мп) некоторая гюслсдова-
в юс
тедыюсть. сг^мящаяся к нулю.
Для уравнений а) и Ь) примера 2 4.4 х'п = с"*'", при этом для
Уравнения а) можно взять vn = отсюда х'п = п.
Замечание 2.4.2. Если уравнение (2.4.5) имеет постоянные ко-
эффициенты, условия теоремы 2.4 2 л предложения 2.4.1, очевидно,
выполнены. В этом случае А, корни характеристического урав-
нения (2.2.9). Последовательность ып - если А простой корень
2 2.9), если же А - корень (2.2.9) кратности 2, ему соответствуют
Два решения i: i/n = - и г' = —.
Пример 2.4.5. Рассмотрим еще один пример рекуррентного
соотношения, встречающегося при анализе трудоемкости алгорит-
ма типа декомпозиции |9 .
2 ” 1
хп — - У' Xk + йп + b	(2.4.6)
ь—о
начальным условием а?о =йо- Посмотрим сначала, как возникает
dTo соотношение.
52
2. Рекуррентные соотношенье
о РСКУР1)СН’ГНЫС соотношения
53
Рассмотрим класс проблем Рп, п — 1,2,..., сложность котЛ
рых «ависит от целочисленного параметра п. Пусть означай
среднее количество работы. требуемое дня решения проблемы р,
Предположим, например, что Р„ требует построения бипарцщЛ
дерева (см. далее) над последовательностью Ci,. .сп ПросмаЛ
риваем последовательное! 1. и выбираем некоторый определении^
элемент' ек в качестве корня дерева. Требуемое для этого каличе)
ство времени пропорционально п, что объясняет появление в (2 1611
слагаемого ап. Затем выполняется какая-то работа над элементом
ejt, обозначим ее через b
Элемент ejt разбивает последовательность ei,...,«fn па две ча-
сги: ei,...,Cfc_i иеь+ь-. ,сп, таким образом, мы разложили проблД
му Рп на две подпроблсмы F*-] и Рп к, отсюда при фиксирований
к получаем	|
хп = xh-i + xn_fc + an + b.
Предположим, что в результате просмотра последовательное™
любой из элементов Ci,t2>---’,.«n может быть выбран в качеств
корня е.к с одинаковой вероятностью, то есть к может принимая
любое значение от 1 до п с вероятностью Тогда средняя тру!
доемкость хп решения проблемы Рп удовлетворяет соотношении!
1 с—
Хп - - У2(хк I + jtn-fc) + ап + ъ,
*-1
которое после некоторых преобразований приводится к (2.4.6) 1
Решается это соотношение с помощью сиегематической про!
цедуры проб и ошибок, в ходе которой выясняется, что последовЛ
телыюсть хп = сп растет слишком медленно, чтобы удовлетворят^
(2.4.6). а хп — п2 и даже хп — п1~Е для любого с > 0 слишков
быст]и>. Это наводит па мысль искать решение в виде хп ~ mlgrl
что оказывается оправданным.	I
Замечание 2.4.3. Как уже было замечено в примере 2.4
асимптотически стационарное решение может колебаться октьи
HCKOTOjTOro ящчепия х. Часто возникает вопрос о суммироваюнч
последовательностей с таким свойством. Исследуя этот bohiwc,
величайший математик XVIII века Леонард Эйлер вывел изве-
стную формулу суммирования, основанную на последовательное П1|
разностей.
Определение 2.4.3 Пусть дана последовательность (ak).
цоСледовптелъностыо разностей назовем последовательность
(Др«к) ‘
Да* = Ofc 11 — “fci
Д2Щ Дак41 — A«fe = Ofc+2 - 2а*; ц + а*;
ЛрОк = ак+1 ~	1^к ~
'ракл.р. 1 + СрОк+Р-2 - - - - + (-1 рак =
— nk+p
Р
i-0
Теорема 2 4 3 (Формула Эйлера).
—!)РА 0(1, если ряд У2(-1)к°* сходится.
к-0	р*0	*=—О
к
Идея доказательства Преобразуем ряд (—1 слс"
*=о
дующим образом
S -- Ди О] I 0-2 -	- (ао - (Я1 -«в) + (а-2 - От) - •••) —
= ~(«0'A«fl + Aoi - Даг + ---) = 2° — ^(Аио —A°i+A°2 —•••)•
Преобразуя таким же обратом ряд в скобках, получаем
$-^Лд«о-д2«"+д2а1 ...) = ^-^04(Д2«с-д2<11+--)-
2	4	2 'I 4
Продолжая преобразовывать выражение в скобках, получаем р-
частичную сумму второго 1>яда из условия теоремы. Пользуясь
сходимос-гыо исходного ряда, доказываем, что остаток преобрато-
ь«шного ряда стремится к нулю- 
Ь4
2. Рекуррентные соотношу
Леонард Эйлер (1707-1783)
Пример 2.4.6, Можно доказать по индукции, что для nocj
довательпости а* — Д,
AP°fc = (~	(fcTT)(fc + 2)... (A -f- р + 1) ’
в частности
(р +1)! pH
Рассмотрим ряд
<ю	.
и- 1
Этот ряд сходится очень медленно: для того чтобы получить то
ность 0,01, надо вычислить 99 членов ряда Применяя к этому 1>я>
преобразование Эйлера, получаем быстро годящийся ряд
схп
1112 = \^ ——.
2 Рекуррентные соотношения
55
получения той же точности достаточно посчитать всего 5
,;,снои данного ряда.
Пример 2.4.7 Аналогично для последовательшхти —
i	* • 1 ,
3JI j	5 kt 1/2
?!
ДРЛ(1 — (~1)Р	- -рту ~ j	—
2	+ 1)...(±+р)
= (,1}р .. 2Р Р! =(_1)Р 2Р.±_
1 ’ 1-3...(2р + 1)	' ’ (2р+1)!!
{здесь мы используем обозначение (2р + 1)!! = 1 3 ... (2р + 1) для
произведения всех нечетных натуральных чисел от 1 до 2р+ I).
Прпмепим преобразование Эйлера к ряду Лейбница
1
2n + 1
р!
(2р 4-1)!!
3.ieci мы также видим улучшение сходимости
Замечание 2.4.4. Эйлер применял вою формулу также и к
расходящимся рядам. В некоторых случаях преобразованные ряды
сходились Теория преобразования расходящихся рядов в сходя-
щиеся. а медленно сходящихся в быстро сходящиеся была разв-
ита it XIX и XX веках в работах С.Пуассона, Н.Абсля, Э Чезаро,
А.Таубера, О.Теплица. Т.Кожима и других. Также преобразование
рядов используется при решении разностных уравнении, то есть
уравнений, содержащих конечные разности искомой функции (см.
опр. 2.4 3).
Замечание 2.4.5 Можно рассматривать рекуррентные урав-
нения не только для числовых, но и для функциональных после-
довательностей Например, линейное уравнение второго по|»ядка
/п+2(х) - 2хТп+1(г) + 7n(z) = 0, Т0(х) = 0, 7i(z) - х
задает последовательность многочленов 7'п(.г) степени п, назы-
ваемых многочленами Чебышева 1 рода, которые явно задаются
формулами
Мт) — cos(n arccos х) =
56
2. Рекуррентные соотношу
Готфрид Лейбниц (1646-1716)
2.5 Упражнения
1.	Построить графики функций:
(а)	у = х-М;
(Ь)	У = а|(5 + Ц- |1, а>0.
2.	Решить следующие рекуррентные уравнения первого
рядка.
(а)	1-1 ~ 2лп	+ 5;
(Ъ)	жп+1 — 5хп	-i-5n;
(с)	Xn-t 1 - п^'”	+ n!’X> —
(d)	" nTT^n^i = i;	
(а)	л. 1 — (L rt С	Зп	, ,3-0 = 1.
ч
рекуррентные соотношения
57
Нилы: Абель (1802-1829)
3.	1 рехмерное щюстранство поделено п плоскостями, из кото-
рых никакие две нс параллельны и никакие четыре не имеют
общих точек. Найти число областей, па которые разделяется
пространство.
4.	Кредит в 12000 рублей, данный под 12% годовых, погашается
ежемесячно в размере 380 рублей, за исключением послед-
нею месяца, когда выплачивается остаток по кредиту мень-
ший чем 380 рублей. Сколько месяцев будет погашаться кре-
дит >i каков последний взнос?
б. С помощью определителя Казорати щюверить, какие из сле-
дующих последовательностей линейно независимы:
(а) (2"),(2^2),(еп);
!Ь) (2”),((-2)"). (3й).
58
2. Рекуррентные соотношение
Отто Теплиц (1881-1940)
6 Решить следующие 1>екур1н*птпые уравнения btojwio но-
рядка:
(а) хп+2 = 16хп;
b 2^4 2 = 5жП4-1 ~ 6тп;
(с) Xn^-2	2Xr_^1
(4) xni2 -^пн -2агп;
(«) Жп+2 =2znt! -2хп,Х1 = Дх2 = 1;
(f) хп_2 5я>1+1 + ^хп = « + 1;
(fi) ~ 4х„ (I + 4xn = 2W;
(h) «п+2 - 4xn+i + 3zn = (n + 1)3”.
7 Приближенные вычисления с помощью рекуррентных урам
пений	I
рскуррет ные соотношения
59
(а)	Каковы вещественные корни характеристического урав-
нения для ЛОУ хп = 2ггп-1 4- 2in-2?
(b)	Найти рациональное приближение к \/3 с точностью до
0.001 с помощью последовательности 1,3. ..
(с)	Пусть х„ = oiTn 1 Ь «г^п-2-Найти рекуррентное соот-
ношение для тп = в виде гп ~ f(rn-i)-
(cl) * Метод Ньютона для вычисления большего корня урав-
нения
х2 — а\х — 02 = У’(т) = О
состоит в применении итерации .тпц - F(rrn), где
F{x) — х ~ г Показать, что этот метод сходится
быстрее, чем метод предыдущего упражнения.
60
3. Элементы теории гр^
3 Элементы теории графов
3.1 Графы. Определения. Класси
фикация
При решении многих задач, касающихся связей между каким»,
либо объектами, естественно возникают графы конфигурации
состоящие из точек, некоторые из которых соединены линиям#
При этом точки (вершины) соответствуют объектам, а линии ( еб-
ра) связям. Исторически первой такой задачей была решений
Эйлером в 1736 году задача о Кенигсбергских мостах. ГермЯ
"теория графов" появился в 1936 году так была названа кии!
венгерского математика Д.Кёнша. Приведем математическое Я
ределение графа. Поскольку мы хотим расе матривать различи»!
приложения гра<)юв, определения будут достаточно развернутыми.
Определение 3.1.1 Пусть даны два множества X и
X П U = 0. Множество X будем называть множеством еершЯ
множество U множеством «сток5. Пусть
М С X х U х X, М £ 0.
Если (х, и, у) £ М, будем говорить, что вершины х и у инцнденгпяЛ
ветке и или соединены вегкой и. а ветка и инцидентна вершинам Я
у. Т|юйка (X,U, Л1) называется графом, если из условий (х, и ; 
М и (т',г1, у') € М следует, что либо х — х’ п у — у', либо X=
у' и у — х' Иными словами, каждая ветка может соединять 
более двух вершин. Если М = 0, X / Р>, to будем причислять!
графам также тройку (X, 0,0). Такой граф, нс содержащий ветоя
называется вершинным. 6	I
В англоязычной литературе используется термин "edge", перевод!
мый на русский как "ребро"или "дуга" В нашем изложении эти слое
имеют более специальные значения, поэтому в обшей ситуации мы буди
использовать слово "ветка"
6Существуют и другие определения графа, например в книге [8 | грач
определяется как тройка (X, U,S), где <5 - отображение из U в множеств
неупорядоченных пар элементов X.
Самос общее определение графа (если не привлекать теорию катен»
з.
Элементы теории графов
61
• ^з
• Х1	• ж2
G вершинный граф
Рис. 3.1.1
Пример 3-1-1 Пусть X = {xi,X2,xs},U = {111,112,113}, Л/ =
{(xi.Ui,X2), (ar2,ti2,xa), (X3,U2,X2), («3,113,1:3)}. Здесь ветка к! на-
правлена от Xi к «г, ветка 112 двусторонняя, а 113 - петля.
Определение 3.1.2 (Классификация веток). Пусть
граф.
а)	Ветка uEU называется дугой, или ориептщюванной веткой,
дл}| любых _т, у € X. х / у из того, что (х, и, у) Е М, следует,
410 (jr, u, z) М. Вершину х назовем ндчалол! дуги, а вершину у -
дается на базе двухосновной системы Мальцева (см , папример:
^'Odyidec, W.Sl^zak. Wybrane rozdzialy leorit grafOw Wyd. Akad By-
^Eo^kiej ini. К Wielkiego, Bydgoszcz, 21ЮЗ, 350 p ).
62
3. Элементы теории трал
концом дуги. Подмножество множества U, состоящее из всех ду»
обозначим через U.
Ь)	Ветка u G U называется петлей, если существует ,т С Л
такая, что (з:. и,х) С Л/. Множество нетель обозначим через U I
с)	Веска и С- U называется ребром, или неориснтировашД
веской, если для любых х, у € Х,х / у из того. что (х, и,у) (= jtf
следует, что (у, и,х) € М. Множество всех ребер обозначим черв
<7.
В примере 3.1.1 U = {ui}. U {u3}, U = {щ?}-
Замечание 3.1.1. Вески, как ориентированные, так и неори-
ентированные, часто обозначают с помощью вершин, которые они
соединяют. При этом дуги обозначают (х,у) или (ж7^), где Я
начало дуги, у - конец. Ребра обозначаются fa:, у] или (хТу), петли -
[х, х). Однако эти обозначения возможны лишь в rpa<J>e в которой
любые две вершины соединяет не более чем одно ребро или не боД
двух дуг в разных направлениях, а каждой вершине инцидентна Я
более чем одна петля. Такие графы называются графами Бе.ржа>И
честь французского математика Клода Бсржа).
Пример 3.1.2. Пусть X —	= {ui>“2,«3-.«4|
М = {(zi,U|,x2), (X},U2,X2)1(X2,U2,X1), (х3,ц3,х3),(х3,и4,х3Я
Вершине х3 инцидентны две несли, поэтому этот граф не являете
графом Бсржа.
Отмстим, что в графе G =	множество веток pi
бивастся на три попарно непересскающиеся подмножества: U
r/ut/utj, йпй= е &пй = 0, и пи — 0.
3-
Элементы теории графов
63
Клод Берж (р. 1926)
Определение 3.1.3. Граф G = (X,U,M) будем называть'
а)	ориентированным графом, если U = 0, и собственно
ориентированным графом, если дополнительно и~ 0 и U 0-
Ориентированные графы в XX веке назывались орграфами а те-
перь диграфами (от англ, directed graph)-,
b)	неориентированным графом, если U = 0, и собственно
неориентированным графом, если дополнительно IJ—0 и U 0-
Неориентированные графы называют неорграфами.
Если 6^0 и 0 / 0,ю i-раф G называют елнднанньш
Граф из примера 3.1.1, изображенный на рис. 3-1.2, - смешан-
ный.
Замечание 3.1.2. Вершинный граф (X, 0,0). а также граф,
состоящий из одних петель, относят и к ориентированным, и к
Неориентированным графам.
Пример 3.1.3. Пусть X - {xi,...,Xn} - группа людей в
некотором коллективе. Будем говорить, что пара {xt,:r}) образу-
64
.3 Элементы теории j рифы
ет дугу, если ж, доминирует над хг Получаем диграф, изобрЛ
жающий отношение доминирования. В диграфе па рис. 3.1 4 jS
{жьж2,...,о:с}, U =
Очевидно, что х-2 - неформальный лидер, так как он (с помоц ь
гг4) доминирует над группой.
Пример 3.1.4. Ест в городе X все улицы имеют одпосш
ровнее движение, то сеть улиц представляет собой диграф.
Пример 3.1.5 В средневековой тюрьме камеры {ж1,.т-2, чИ
{!/1>У2,Уз}1 {21,22,23} расположены вдоль трех коридоров. Кая
дый из трех надзирателей а. Ь,с может одновременно наблюдЛ
за камерами одного коридора и за надзирателем справа Jurjal
наблюдений надставлен на рис. 3 1.5
Элементы теории i рафов
65
Пример 3.1.6 Понятие алгоритма как четко определенной
фОЛСДУры является одним из основных в математике и ннфор-
(£1Гике (см. например [6]) Одна из формализаций понятия не.1>е-
<ч,рсивного алгоритма состоит н следующем. Под интерпретацией
^(числительного алгоритма понимается диграф со следующими
-войстпами. В диграфе имеется единственная вершина, в которую
16 еходит ни одна дуга, называемая eawl На вход подаются иеход-
dbK> данные Все остальные вершины делятся на три группы:
• Выход. Из них не выходит ни одна дуга. При достижении
выхода работа прекращается.
•	Вычислительный узел В такую вершину входит и из нее
выходит единственная дуга. Здесь происходит какая-либо
арифметическая операция.
•	Учел ветвления. В эту вершину входит одна дуга, а выходит
из псе две с пометками "да"и "нет". В узле проверяется,
верно ли, что какая-то переменная равна нулю -
(А'
Определение 3-1.4 Пусть дан граф G — (X,U, М). Граф G' —
Г7',Л1') будем называть подграфом графа G, если
X' С A', U' С ГД М' С М.
И’
Пример 3 17 Граф G' — (А ,17',№'), где X' — {а,11,х2.хз},
- (ui = (a.Xi),U2 — (a,a?2),M3 - (а,хз)} - подграф графа G из
примера 3.1.5.
' Подробнее см.: Смейл С. О проблемах вычисли юльпой сложности //
Магом, просвещение. 20CHJ Сер.З Вын.4. С.115-110.
66
3. Элементы теории ipm
Определение 3.1.5 Граф Бержа G - (X,U,M) называет
полным, или насыщенным, и обозначается Gx- если для люб
двух вершин £t,Xj из X существует ветка u С U : (с, и, у) G;
Иногда требуют, чтобы полный граф включал еще по одной пет
у каждой вершины. Полный псорграф без нетель с п вершин!
обозначаю'! Кп.
Пример 3.1.8 Па рис. 3.1.7а дан полный диграф Gx, V
{х।, т-2, ^з} без педель, а па рис. 3.1.76 полный неор1раф Gx-
{Т|,Т2,тз} с петлями
Рис. 3.1.7а
Элементы теории графов
67
Наряду с графами Бержа вводится важный класс простых
графоа.
Определение 3.1.6. Пусть п число вершин графа G =
(Х.Г/,А/), п 3. Назовем G простым графом, если любые две
рахтичныс вершины в G соединены не более чем одной веткой8
Замечание 3.1.3 Простой граф может содержал ь любое ко-
личество петель у каждой вершины. Любой простой граф, каждая
вершина которого инцидентна нс более чем одной петле и п 3,
является графом Бержа. С другой стороны, любой неориентиро-
ванный граф Бержа является простым графом Диграф Бержа при
и 3 может не быть простым, так как две различны вершины
могут бы гь соединены двумя дугами5
Пример 3.1.9. Граф G = {X,U,M), X — {х1,х2,хз,х4}, G —
{^l>u2,u3}, Af = {(x1,Ui,T2),(^2>H|-.^|), (Х2,Н3,Хз), (X2,W2,X4)}
будет смешанным гра«1юм Бержа, а также простым графом.
кДля п = 2 и 7* = 1 приняты специальные определения их целесооб-
разность будет понятна в параграфе 3.3. Простыми i рафами будем счи
^ть: диграф Бержа с двумя вершинами, неорграф с дпумя вершинами,
°Дним юн двумя ребрами, их соединяющими, и любым количеством
пр1ель, и граф с одной вершиной и любым количеством петель,
R литера гуре, особенно англоязычной (см., например: The Penguin
ittionary of MATHEMATIC'S. Edited by David Nelson Second edition.
Penguin books. London), принято другое, более узкое определение
piXieroro графа. Простым называется граф без петель и кратных ребер
е-'м. далее опр. 3-1.7). В нашей терминологии это граф Бержа без петель-
68
.3 Элсмсн1Ы теории rpd<
Рис. 3.1.8 к примеру 3.1.9
Определение 3.1.7 Неориентированный граф бе» пет дь
котором существуют по крайней мерс две различные нсришп
связанные более чем одним ребром, называют мулътигршфом. Я
или более ребра, связывающие одну и ту же пару вершин, паз
ваютея кратными. Таким образом, мультиграф содержит краги
ребра.)
Определение 3.1.8 Неориевтированпый граф, содержав
петли и (или) кратпые ребра, называют псевдографом.
Пример 3.1.10. Мульгиграф и псевдограф (см. рис.3.1.9а и
Рис. 31.9а Мульгиграф
д цементы теории графов
(59
Определение 3.1.9 Пусть G = (X,U,M) - диграф (17 = 0).
Сопоставим каждой вершине Хо € X множество концов всех дуг,
выходящих из этой вершины, причем, если в какую-то вершину
из ха идет п дуг, эга вершина считается п раз. Если вершине
z0 инцидентно несколько не гель сопоставим ей саму вершину Хо,
причем считаем ее столько раз, сколько петель ей инцидентны.
Если из вершины не выходит' ни дуг, ни петель, сопоставим ей
нус гое множество Такое сопоставление назовем мулътифункцие.й
(словарной функцией10) Fc;(x), соответствующей графу G
„ . . J {у € X . 3u € U : (х,и,у) Е М}
гвеч = <
(	0, в противном случае.
При этом вершина "у" берется столько раз, сколько существует
различных веток и из U таких, что (ж, и,у) € М (В дальнейшем
мы будем опускать индекс. G если из контекста понятно, к какому
графу относится мультифупкния.)
Пример 3.1.11 Пусть G — (X,U, Af), X — {а7>, £2,23},
f' = {ui,’*2,M3,w-»}, Af = {(х1,?ц,х2),(аС1,и2,Х1), (ж1,из,ж3).
(^з-п4,гз)}.
“’Трмное определение. мудьтнфункции следующее. Пусть А' множе-
ство (обычно конечное) Назовем его алфавитом Словом над X назовем
любую конечную носледовагсльпость элементов алфавита (возможно,
с повторяющимися элементами). Мультифункцисй F па А' называется
отображение F : X -> Z, где Z множество слов Над А'
70
3 Элементы теории грЯ
Тогда F(xi) = {Х1,х2,а:з}, F(^2) =	= {х3}. Итад
диграфу G = (X,U,M) мы сопоставили пару (X, F) где F .
мультифункция па X. Верно и обратное, то есть если па хик>
жссгвс X = {х1....,гги} задана мультифункция F, то можш
построить диграф, беря в качестве дуг или петель пары (х,, у), м
у G F(xi), i = l,...,n.
Пример 3.1.12. Пусть X = {хь^^з}, P(xi) — 0,	5
{xi.x2,i3}, F(xa) = {х2}- Тогда. U = {u, = (x2.a:i), «2 5
(х2,Х2), Чз = ш = (яз»я2)}, М ~ {(»2,ui,x2), (хг.иг/ч
(Z2,U31X|), (х3 «4,^2)}-	'
Рис. 3.1.11
1'аким образом, диграфы можно задавать и парой (X, F),
F - мул1>тифункция.
Элементы теории графов
71
I 0Приделсние 3.1.10 Пусть дан диграф G = (X.f). Подграф
I / - {X'.F') С G будем называть тюдгрш/юм, оперированным
F 1и11(х»ееегпвом	С сс',,<	= X" П t'{x} для любого
^Пример 3.1.13 X = {аС|.Ж2,хз}5 ^’(xi) = {хь^г}, F(i2) -
I },/'(уз) — {xi}- Пусть X' = {х2,хз}- Тогда подграф, гспери-
I крайний подмножеством вершин X'. это (Х'т F'), где	-
[ X' П ^'(хз) = 0 = X' П F(x3)-
Рис. 3.1.12а. Исходный граф примера 3.1.13
Рис. 3.1.126. Подпжф, генерированный {x21Tj}
Определение 3-1.11 Пусть дан граф G = (Х.(/, М) и |Х <
+°с. Подграф G' = (X1 .U1, М') будем называть скелетны.» или
О(-И1овн?14.и. если этот подграф простой. X' X и каждая вершина
и,1ЦЦдептпа хотя бы одной ветке из U'. Скелетных подграфов в
72
2 Элементы теории графов
з. Элсл,е,„ь, 7ТОрии ( I
графе может бы ть нй*к<>п1.т,
определение 3.4.6).	Э МОЖС1 пс быть вообще (см.
Пример 3 1.14. Пусть <7 - I у и
2.13а. ГГ	_ /"v, ТТ, X?U,M), где граф G дан кз
товным.	’ ,2?)> Данный па рис. 2.136, буЧе^И
рис. 3.1,136
Х3
Рис. 3.1.13а
Определение 3.1.12 ГпИ<+. ст
конечным, если XI < и р? , ~ (^П,М) будем называв
веток конечно. В нро1ив11ом случа? ™ ЧИ“° I
< + !}•- 1,2,. Тогда диграф Gl J Й'Ч '1' ПуМ‘ : I
Р Р - (A,F) - бесконечный. I
73
Рис. 3.1.14 к примеру 3-1
Пример 3.1.16. Пусть X = {Л/} и [0,1]- Точка М соединена
ребрами со всеми точками отрезка [0,1]. Граф имест несчетное мно-
жество вершин и веток. В дальнейшем *ь! будем рассматривать,
если не оговорено гцютивнос, только конечные графы.
Рис. 3.1.15 к примеру 31 16
Определение 3 1.13. Пусть дан граф G = (X,U,M), вершина
г G %. Число веток инцидентных вершине х, называется erne-
Пмгъю вершины. Это число обозначается р(х)- Чисто дуг, имеющих
"«чало в вершине .г, назовем полуотепе-нью ncxt>^a (обозначение
М), чиню дуг, имеющих конец в вершине х, назовем полусте-
ъ?-къю захода (обозначение р (х)).
74
3 Элементы теории {..
Если G диграф без петель, то для любой вершины
справедливо
р(х) = р+(х) + р-(ж).
Пример 3.1.17, Пусть X =	U ~ {« «2,и3}, Af
{(2Г1,П|,.Т2), (тьЦ2,Х2), (Х1,из,Хз)}- ТоГДН р(Т]) = 3, р^Л 5
з, Р"(Х1) = 0, р(з:2) = 2, /Л(я2) = 0, р (т2) = 2. р(гл
1, Р+(*з) = 0, р-(®3) = 1.
Теорема 3.1.1 (Эйлера о сумме степеней). Пусть G -
(X. U, М) - граф без петель, тогда:
а)	сумма степеней всех его вершин равна удвоенному чихЛ
веток;
б)	количество вершин нечетной степени четно
Доказательство. Степень вершины - количество инци мзЛ
пых ей веток, поэтому, если сложить все степени. мы учтсм^И
ветки графа, причем дважды, так как каждая ветка инцидент»
ровно двум вершинам, отсюда следует а). Если бы количсся
вершин нечетной степени было нечетно, сумма всех степеней би
бы нечетным числом, что противоречит а). 
Определение 3.1.14. Пусть G = (X,U,M) - конечный гр»
|Х| — n > 1. п х n-матрипу R = (г^), где
J числу веток, инцидентных одновременно г, и х3. г /
(	числу петель, инцидентных вершине х,, i — М
rcoPlli1 1'рафоВ
_Bcw матрицей общей. смежности.
Р случае. когда G будет диграфом, п х n-матрицу К - (г0), где
[ числу дуг, ВЫХОДЯЩИХ ИЗ X* И ВХОДЯЩИХ В Jj, I / j.
гч ~~ ( числу петель, инцидентных вершине х„ i = j,
назовем матрицей смежности.
Замечание 3.1.4. Очевидно, диграф будет диграфом Бержа
тогда и только тогда, когда матрица смежности того диграфа
буиаг содержать только нули и единицы. При этом полному графу
Бержа с п вершинами и п петлями отвечает матрица смежности
вида п х и. состоящая из одних единиц.
Пример 3.1.18- Пусть Gi — (Xi.Ui,Mi) граф, изображен-
ный на рис. 3.1.17а, аСг = (Х-г^Уъ, М?) - па рис. 3 1.176. Тогда
(О	2 0\	/0	1	(А
2	0 1 ),/?<-;.=	I 1	0	1	.
0	12/	\0	0	1/
Рис. 3.1.17а
76
<3. Элементы теории гра(
Определение 3.1.15. Пусть G = (X, L/, М) конечный дш j
без петель, Х| = п > 1, |[7| = тп, п х rn-матрицу А = (а,Д где
{1, если вершина х, является началом дуги и3,
О, если вершина xt не инцидента дуге Uj,
—1, если вершина х, является концом дуги и3,
назовем матрицей инцидентности.
Пример 3.1.19 Пусть G = (X, U1 М) изображен на рис. 3.1.
Тогда
(1 1 -1
О -1	1
-10	0
о
-1
1
Рис. 3.1.18
Элементы теории графов
77
ЗГеорема 3-1-2 Любая матрица, в каждом столбце которой
дгржип я ровно два ненулевых элемента, один из которых ра-
*°л j а другой -1, является матрицей инцидентности некоторого
речного диграфа без петель.
Доказательство см. |10’]
Определение 3.1.16. Пусть даны два диграфа Gi — (A'i ,F\) и
С2 — (А2. F2). Биекция Т.Х} —» А2, такая, что для любой вершины
г б Х1 выполняется
Д^(х)) = F2(T(x)),
называется изоморфизмом между G’i и G2- Если существует изо-
морфизм между 6’1 и G’2. то такие диграфы называются изо-
морфными (Gi = G2).
Дадим также определение изоморфизма для общего случая
необязательно ориентированных графов.
Определение 3.1.17. Пусть даны два графа G’j = (Хь U\< Afj)
и G2 = (А2,62, М2). Будем говорить, что графы G] и С2 изомор-
фны (Gi — G2), если существуют две биекции 7i : Xi —+ А'2 и
7 г ’ Ъ\ > U2, такие что для любых вершин xi,x2 б Aj, и б Ui
выполняется
(xi,h,х2) С Mi о (Т|х ьТгД. 7ix2) € Л/2
Изоморфизм графа па себя называют автоморфизмом.
Пример 3.1.20. Пусть даны три диграфа: Gj = (A1.F1), G2 =
('V2-F2). G.4 = (Xj. F3), изображенные на рис. 3.1.19а),б),в). Тогда
д,’граг|>ы Gj и G2 изоморфны, в качестве и:юмо1х)шзма между G| и
G2 можно взять отображение 7’(х,) — х', i = 1,2,3. Диграфы Gi и
G.i не изоморфны, так как из вершины х\ диграфа Gi выходят три
-ХУ' и. а пи одна из вершин диграфа G3 не обладает этим свойством.
78
3 Элементы теории Гра
Рис. 3.1.19в
I 3 Элементы теории i рафов	79
3.2 Операции на графах (топологи-
ческие и алгебраические)
Определение 3.2.1. Пусп, Gt = (XlyUt,Mi) и G’2 =
(Х2.Г72: ^з) подграфы графа G = (X,U.M). Топологической
гумл<ой подграфов Gi и С2 (обозначение G\ UG2) будем называть
подграц’ G.3 (Хз,17з,Л/з) — Gi и (?2, где
Х3 =• Xi U Х-2, U3 = ГЛ U U2, МЛ Mi и М2.
Пример 3.2.1 Пусть Gi и G2 изображены на рис. 3.2.1а и
3.216. тогда их сумма G\ UGT2 изображена на рис. 3.2Дв.
Рис. 3-2.16
80
3 Элементы теория гра J
Pin. 3.2.1в
Определение 3.2.2 Пусть Gj = (Xi,{7i,Af|) и Gj =
(Лг>^2, Му) -подграфы графа G = (X, V, JW). Пересечением ина-
графов Gj и Gy (обозначение Gi П G?) будем называть под1раф
G3 = (Хз, U-3, Л1з) = Gi Г) G-2, где
Хз — X| П Х-j, Уз ~ Ui Г1 А^з -— Л/j П ЛТг-
Пример 3.2.2 Пусть Gi и Ga пол1-рафы, приведенные]
примере 3.2.1, тогда G\ О G2 = ({^2}. 0,0).
Определение 3.2.3. Пусть Gj = (X,	- подграф i-paJ
G = (X,t/,Af) (подчеркнем, что их множества вершин совпадаю!.
Дополнением G, в G назовем подграф Gj = (X, IfaMz) графа С
такой, что
П2 Г\1Д = 0, Му О Л1 = 0, G и Gi — G.

Пример 3 2.3 Пусть Си G| изображены на рис. 3.2.2а и 3-2-21
тогда Gi изображен на рис. 3.2.2в.
81
Рис. 3.2.2в
82
3.
Элементы теории
Предложение 3.2.1.
дополнение дополнения Gj
Пусп. Gi - подграф графа G,
в G совпадает с Gi, то есть
G1 = G ।.
Пусть Gl ~ (X,t/l,Afl) И G;
’ = (X, U,M). Разностью
Определение 3.2.4. Г.
(X, U^Mi) - подграфы графа G —
Пжфов Gj и G2 (обозначение G\ — G2) будем называть иплгпА
G3 = Gi — G2 — Gi П G2-
Пример 3.2.4. Пусп. G\ и G2 изображены па рис. 3 2jk N
3.2.36, тогда Gi — G2 изображен на рис. 3.2.Зв
Рис. 3.2.36
цементы теории графов
83
Теорема 3.2.1 Пусть Gi = X,Ui,Mi), G2 = (X.U2, М2),
G3 - (X,U-j,Ma) - подграфы графа Бержа Cl = (.¥,17, Л/)- Тогда
еыполняюпмм следующие свойства:
1.	С?) U Cj2 = G2 U
Gi P.G-2 = GzClGi (коммутативность).
2,	(Gj U Gj) U G3 = G| U (G2 U G;j);
(Gi П G2) П G3 = Gi П (G2 Г) G3) (ассоциативность).
3-	(Gj Г) G2) — Gi U Ga;
(Gi U G2) = Gi П G-а (правила де Моргана).
4.	(Gi U G2) Г) G3 — (Gj П G3) U (G2 Г1G3);
(G| D G2) U G3 = (Gi U G3) П (G-2 U G3) (дистрибутивность).
Замечание 3.2.1. Путь G - подграф некоторого 1рафа К с
Прежним множеством вершин. Обочначим 1 = К, 0 = (¥.0,0).
Тогда легко проверить, что
G и G = 1, G П G = О; G U G = СТ, GC\ Cl = G.
Определение 3.2.5. Пусть на множестве X / 0 определены
лве операции Ф и О, такие, что:
1.	Операция ® коммутативна и ассоциативна.
84
3. Элементы теории rpmfy
2.	Существует нейтральный элемент 0, такой, что для лю(
a G X выполняется йФО = а (таким образом. по сложенцЗ
X будет коммутативной полугруппой с единицей)
3.	Операция 0 ассоциативна и коммутативна.
4.	Сущее гвуег нейтральный элемент 1. такой, что для люГщ
a G X выполняется а © 1 = а.
5.	Для любых и. Ь, С Е X а<-> (6 ф с) = (« © Ь) ф (о 0 с)
6.	Для любого а G X а © 0 = О
Тогда (Х,Ф, 0) называется коммутативным полукольцом Ес
при этом для любого а Е X выполняегся и ©о - а, то полукеды
называется идемпотентным.
Пример 3.2.5. Пусть G — (X, F) - диграф Бержа. Обозначи
через G’x множество всех подграфов G с множеством вершин Л
Если ввести на множестве Сд операции ® = 11и0 = Л)Г
множество превращается н идемпотент нос полукольцо, при т
роль О выполняет вершинный граф (X, 0), а роль 1 сам i-раф
Замечание 3.2.2. Топологические операции U и П примени!
как правило, при построении моделей явлений одного уровня а
жности. При изучении иерархических структур применяют ал1
браические операции композиции и декомпозиции. В первом спуч
ст роятся более сложные структуры, а во втором сложные с грум
ры раскладываются на более простые.
Определение 3.2.6. Пусть G = (X,F) и К = (У, Р) про»
вольные диграфы
1.	Произведением GxK назовем диграф Q — (И7,Т), такой, ч
(a)	W = X х У;
(b)	Vx G X, у Е У Т(х,у) = F(x) х Р(у).
2.	Специальной суммой G + К назовем диграф L = (И7, i
такой, что
(а)	Иг - X х У;
(b)	Vt с X, у Е У Щх.у} (F(x) х {у}) U ({х} х Р(у)).
j Элементы теории грифон	85
3	G® К назовем диграф S — (W,L>), такой, что
(а)	IV - X х У;
(b)	Vx е А, у € У D(i,у) = (F(x) xY)U(X х Р(у)).
4	Если X = |У| = п 5 I, то суперпозицией G * К назовем
диграф S = (Ж С), такой, что
(а)	Hz = X х У:
(b)	Vx G X, у ё У С(х,у) = (F‘(x) х Р' (у)) U... U (Fn(x) х
F"(У)), где
{х}, если т.3 Е F(xt)
(3, если Xj £ F(xt) ’
Р?(У.) =
f у}1 если у3 Е P(yi)
I 0- «’-яи Уз i P(yt)
j = 1,... ,n.
Пример 3.2.6 Пусть G, = (X,F). G2 = (Y,P), RGl =
Iq 0 / ’	= I (j о) ‘	G’i x Gj, Gj + G'2, Gj 0 G‘2 и
Gi * G2. На рис. 3.2.4 приведены результаты этих операций. Здесь
wi = (^l.yi),W2 = (ii.y2),«’3 = (^2, У1), U’4 = (Х2,У2)-
Рис. 3.2.4а
92
3. Элементы теории граЛ
последовательное! и (*), кроме. может быть, первой и послсдтм
встречается роппо один раз	?
Определение 3.3.3. Если в грат(>е любые две вершины можц
связан ь цепью, такой граф будем называть связныл*
Определение 3-3.4. Две вершины графа будем называть едД
зонными, если существует связывающая их нет- Можно показац^
что отношение связанности будет отношением эквивалептносгЛ
Это отношение порождает разбиение множества вершин на кла^Н
экниваленпюсти, называемые компонентами связности
В случае ориентированных графов следует учитывать ориента-
цию веток в цени.
Определение 3.3.5 Пусть дан граф G = (X, 17, Л/) и д -
(«1, U2.  -.) цепь. Если все ветки цепи ц дуги (щ € 17) такие чю
конец дуги и,- совпадает с началом щ+1, то цепь называют ngn^H
Если в диграфе G любые две вершины можно соединить путем, ij
диграф называют сильно связным.	
Очевидно, сильно связный граф будет связным • и паобо^И
если этот граф - диграф Па практике для диграф>в различав
понятия связности и сильной связности, называя диграф < вязшЛ
если будет связным граф, полученный из исходного играфаЖ
меной всех дуг на ребра.
Пример 3.3.2 Пусть даны диграфы G\ и Gz (см. рис. 3.3-Я
3.3.3). Грас|т G’i связный, но не сильно связный; граф G? силЯ
связный.
Рис. 3.3.2
3.
Эдемснч’ы теории графов
93
Рис. 3.3.3
Теорема 3.3.1. Для любого конечного неориентированного
графа Бсржа G с числом вершин п связен либо сам граф, либо
его дополнение G в графе Кп
Доказательство. Если G связен, теорема доказала. Если G
несвязен, оп состоит хотя бы из двух компонент связности Рас-
смотрим произвольные вершины х и у. Если они принадлежат
разным компонентам связности, значит они нс соединены ребром в
графе G, поэтому соединены в графе G. Если же они лежат в одной
компоненте связности Kt, рассмотрим вершину х. принадлежащую
Другой компоненте связности Хг- Ребра С] = (x,_z) и ег = (z,y)
не принадлежат G, следовательно, принадлежат G, так что х и у
связаны цепью xe^ze^y длины 2. 
Иногда теорему 3.3 1 формулируют как "Теорему о двух видах
^Рапопорта”. Если дапы п городов, причем каждые два города
соединены либо автобусной, либо железнодорожной линией, то
из двух видов транспорта .можно убрать, не нарушив связ-
иости транспортной сети.
Определим теперь важный для приложений класс графов.
Определение 3.3.6 Пусть G = (X, U, М) конечный связный
Не°Рграф. |Х| = n > 1. Если |С/ = п — 1, то граф называется дере-
«ол| Вершины дерева, инцидентные только одному ребру' (степени
')•. называются листъя.ии12.
_ __
В некоторых книгах листом назынается связный граф, не содержа-
ли мостов (см. далее замечание 3.4.3).
8С
3. Элементы теории rpat
В cie.iyiomcfi теореме приводится характер и лаки я операций нам
теоРии графов
87
, на языке матриц смежности. Для этого введем некоторые
11Д । над матрицами.
f Определение 3.2.7 Пустт Д = (аф и R = (bv) матрицы
Тог ха объединением матриц называется матрица
0 * 1
A U В - (с,3), где ь3 = max(a,j, btJ),
пресечением матриц
называется матрица
4 п В = (<4>), где dij - min(«y,fr0), i = 1,.. - ,m; j - 1.
n.
Пример 3-2.7. Пусть
/2	3\	/-1	0\
Л =	I 1	4 I	,	В =	I 2	1 ] .
\0	1/	\ 3	1 /
Тогда
/2 3\	/-1 ()\
Лив=	I 2	4 I	,	ЛПВ=	1 1 I .
\3 1/	\° I/
Определение 3.2.8 Пусть A = (tty) и /3 = (bv) квадратные
матрицы n x n и m x т. Тогда их прасы.м прямым проихнедснием
назовем матрицу
(оцВ ... а,пД\
..............
Оп1В ... аппв)
Пример 3-2.8 Пусть
/2	1\	/3	1	Л
.4 = (f.	;),	в -	о	1	1
vu	V	\2	1	О/
Тогда
/6	2	2	3	1 1\
0	2	2	0	1 1
4	2	0	2	1 0
АсН-
0	0	0	3	11
0	0	0	0	1 1
\0	0	О	2	10/
88
3. Элементы теории
Определение 3.2.9. Пусть А = (а,}) и В = (Ьц) - .мнгШД|
одной и гой же размерности п х п. Строку и столбец матриц^Я
одинаковыми номерами назовем соотвегствукмцими. Матрицы Д?
В называются ихоморфными (записываем; А = В), се ih В поду^.
на из Д одновременной перестановкой соответствующих сгрок .
столбцов.
Теорема 3.2.2 (о синтезе графов). Пусть G — (X.F), /у 5
(У, К) - конечные диграфы Бержа, |Х| = п, Y = т. Rq и Ци
соответствующие, им матрицы смежности. Пусть Eq и Еу
единичные матрицы порядков п х п и т х т соотве.тстхи хне, <
Ес; и Гн ~ матрицы порядков п х п и тп х т, состоящие тгиыьл
из единиц,- Тогда:	I
Г Rcj>.h — Rc;oRh;
2- Eq j р ~ [Rq о Ен) U (Е’с с Ян)'-
3 Rcv>h - (Яс о Рц) U (Рс; о RhY
4- еслит п. moRchn — U Я^оК’н, где Rlc и Т?)7 матриии,
:—1
получающиеся из Rg и R-н заменой веет столбцов, храЯ
i-го, на нули.	I
Заметим, что матрица Pq - это матрица смежноечи полтД
диграфа Бержа с и вершинами, а Е(; матрица смежности графе!
п вершинами, каждая из которых инциден тна единственной неиф
Определение 3.2.10. Пусть G - (X, U, М) и Н = (У V' А’1
- конечные графы, |Х| = п, У — т, X Л У — 0. СоссАтнеммеЛ
графов Ci и II назовем граф В = (X L У, И'г. Аг), где
W = f uVu {множество ребер {u,j}, соединяющих каждую®
вершину из X с каждой вершиной из У},
Дг MuK\jMnTn, где Млт^{(х,,ц0,^), i 1
Соединение х G2 двух вершинных графов Gj - (X 0 <3)Ш
G-г (У, 0.0). где |Х| — п и У = гп, будем обозначать че.р®
Кп.щ и называть полным двг/долъным графом с п и т вершина-МР
в долях.	
Элементы теории графов
89
Пример 3-2.9 Пусть G — (Х,0,0), Н —	Х| —
,у| - 3 Два трехнерпигппых графа. Их соединением будет граЦ>
^з3 (см рис. 3.2.5).
Определение 3 2.11. Пусть G = (X, U. М) - диграф Диграф,
полученный из G изменением ориентации всех ду’ на противо-
положные. назовем асссщиироианшям с G (обозначение G*). Оче-
видно, ((7’)* = G.
Пример 3-2.10. Пусть G изображен на рис. 3-2.6. тогда G* на
рис 3.2.7.
Рис. 3.2.6
90
3. Элементы теории граф!
Рис. 3.2.7
Теорема 3-2.3. Пусть G,H,K конечные диграфы Бе]
Тогда, если обозначить через 0 любую из операций х, +,
когда число вершин в этих графах одинаковое, то и *, получи
1.	G О И = Н QG (коммутативность);
2	(G © Н) 0 К ~ G ® (Н 0 К) (ассоциативность);
3.	(G 0 II)* = G* 0 II*. При этом, если взять диграф Я
состоящий из одной петли, то J х G ~ G и G х J = GI
то есть J является нейтральным элементом для операции
х. Если рассмотреть диграф Т = (У, 0,0), состоящш^И
одной вершины, то G + T — G, G	G, так что ТК
нейтральный элемент для операций +, 0.
В и чхм е, множество диграфов образует относительно каждой в?
операций +, 0,0 коммутативную полугруппу с единицей
Замечание 3.2-3. Изучение идемпоч-енгных полугрупчч и ito-ijf'
колец привело и 80-90-х годах XX еека к появлению новой перспсК'
тивччой математической дисциплинч.ч - идемпотентного анализа А
нМасло1> В.П., Колокачьцсп В.Н. Идемпотентный анализ и
некие в оптимальном управлении- М.: Наука 1994. 144 с»
91
Элементы теории графов
J’
3.3 Связность и /с-связность гра-
фов. Метрики на графах
Определение 3-3.1. Пусть дан граф G = (X,U.M). Пусть
даНа последовательность вершин и веток
{*)
(jOjMi./Ei.ua,-- • n*+i,xjt+tl...),
такая, что любая тройка (xm n um, xtn) С М, тп = 1,... k Тогда бу-
1еМ говорить, что задана цепь, начинающаяся в вершине Хо. Цепь
будем обозначать р = (ць н2,..., и*,...), если последовательность
*) бесконечная, и р — (u|.u2,... , ttjt), если последовательность (*)
конечная В последнем случае будем говорить, что цепь Оканчи-
вается в вершине Количество веток в цепи будем называть ее
Уликой 
Далее, кроме параграфа 3.6, все графы, если особо не огоно
рено: НЕОРИЕНТИРОВАННЫЕ.
Пример 3.3 1 Пусть 67 = (76, U, М) граф, данный па рисунке
3.3.1. Тогда pi (ui,u2) будет цепью, а р2 = (1ц.и2,из) цепью нс
будет, так как в последовательности (x4,Ui,x1,и2,х2,нз,хд) тройка
(121и3.хз) $ М.
Рис. 3 3.1
Определение 3.3 2 Пусть в графе G = (X, U, М) дана пень р
Еуис.ч говорить, что цепь р простая, если все ветки в цепи ве чре
’[:11о1(;я ропно одни раз. и элсмситарпая если каждая вершина в
92
3. Элементы теории граЛ
последовательное! и (*), кроме. может быть, первой и послсдтм
встречается роппо один раз	?
Определение 3.3.3. Если в грат(>е любые две вершины можц
связан ь цепью, такой граф будем называть связныл*
Определение 3-3.4. Две вершины графа будем называть едД
зонными, если существует связывающая их нет- Можно показац^
что отношение связанности будет отношением эквивалептносгЛ
Это отношение порождает разбиение множества вершин на кла^Н
экниваленпюсти, называемые компонентами связности
В случае ориентированных графов следует учитывать ориента-
цию веток в цени.
Определение 3.3.5 Пусть дан граф G = (X, 17, Л/) и д -
(«1, U2.  -.) цепь. Если все ветки цепи ц дуги (щ € 17) такие чю
конец дуги и,- совпадает с началом щ+1, то цепь называют ngn^H
Если в диграфе G любые две вершины можно соединить путем, ij
диграф называют сильно связным.	
Очевидно, сильно связный граф будет связным • и паобо^И
если этот граф - диграф Па практике для диграф>в различав
понятия связности и сильной связности, называя диграф < вязшЛ
если будет связным граф, полученный из исходного играфаЖ
меной всех дуг на ребра.
Пример 3.3.2 Пусть даны диграфы G\ и Gz (см. рис. 3.3-Я
3.3.3). Грас|т G’i связный, но не сильно связный; граф G? силЯ
связный.
Рис. 3.3.2
3.
Эдемснч’ы теории графов
93
Рис. 3.3.3
Теорема 3.3.1. Для любого конечного неориентированного
графа Бсржа G с числом вершин п связен либо сам граф, либо
его дополнение G в графе Кп
Доказательство. Если G связен, теорема доказала. Если G
несвязен, оп состоит хотя бы из двух компонент связности Рас-
смотрим произвольные вершины х и у. Если они принадлежат
разным компонентам связности, значит они нс соединены ребром в
графе G, поэтому соединены в графе G. Если же они лежат в одной
компоненте связности Kt, рассмотрим вершину х. принадлежащую
Другой компоненте связности Хг- Ребра С] = (x,_z) и ег = (z,y)
не принадлежат G, следовательно, принадлежат G, так что х и у
связаны цепью xe^ze^y длины 2. 
Иногда теорему 3.3 1 формулируют как "Теорему о двух видах
^Рапопорта”. Если дапы п городов, причем каждые два города
соединены либо автобусной, либо железнодорожной линией, то
из двух видов транспорта .можно убрать, не нарушив связ-
иости транспортной сети.
Определим теперь важный для приложений класс графов.
Определение 3.3.6 Пусть G = (X, U, М) конечный связный
Не°Рграф. |Х| = n > 1. Если |С/ = п — 1, то граф называется дере-
«ол| Вершины дерева, инцидентные только одному ребру' (степени
')•. называются листъя.ии12.
_ __
В некоторых книгах листом назынается связный граф, не содержа-
ли мостов (см. далее замечание 3.4.3).
94
3. Элементы теории гр Л
Пример 3.3.3. Граф G’i на рис. 3.3.4а - дерево, а граф (J
рис. 3.3.46 не является деревом. Вершины Х],з:25^4}^5 графа 
листья.	1
Рис. 3.3.46
Определение 3.3.7. Если G - (X.U,M) - несвязный гре
каждая компонента связности кото{и)го является деревом, грае
называется лесом.
Пример 3.3.4. Граф G на рис. 3 3 5 - лес.
Элементы теории графой
95
Замечание 3.3.1. |10 | С помощью производящих функций мо-
жно 1>ешить задачу пересчета корневых деревьев то есть деревьев,
в которых выделена некоторая вершина, называемая корнем. Два
корневых дерева считаются изоморфными, если существует изо-
морфизм меж?1у ними, переводящий корень в корепь Обозначим
через Т„ число неигюморфпых корневых деревьев с п вершинами.
Легко видеть, что Т\ =1, Т? = 1. Т3 = 2, Т4 = 4.
Будем строип» дерево с п вершинами из более мелких (рис.
3.3.6). Если убрать корень, дерево разобьется на несколько под-
деревьев, каж.ре из которых может содержать любое количество
вершин, меньшее п. Сопоставим n-вершинному де|>еву или лес/,
содержащему некоторое количество изоморфг ых деревьев, общее
количество вершин которых равно п, одночлен тп. Тогда серии,
состоящей из всевозможных набо{Юв корневых де{>евьев из одной
вершины, соответствует ряд
I + х + -т2 + .. - + хп + ... = (1 — ж) *,
а всевозможным наборам трехвершинных деревьев
(1 Н3 +i6 + ... + ?" L..)2 = (1 - а:3)-2
(получается вторая степень, гак как есть 2 вида неизоморфпых
’[‘’Рпевых деревьев с 3 вершинами). Эти сообража ия приводят к
Формуле
'F(y)	7’13.7^2-2	। тпхп + ...—
96
3 Элементы теории гра,
Приравнивая коэффициенты при одинаковых степенях iiepJ
ной, вычисляем 7’п. Приведем несколько первых членов ряда;!
7’(аг) = х + х2 + 2х3 + 4а:4 + 9.т5 + 20zc + 48.т7 + 115а:8 Р
+ 286х9 + 719а:10 <-.
Явной формулы для чисел Тп до сих вор не получено.
Рис. 3.3.6а (на рисунке корень дерева отмечен стрелкой)
rWYY)
Рис. 3.3-66
Приведем оценку количества ребер неориентированного ip
Бержа без петель.
Предложение 3.3.1. Полный неориентированный граф
и п— I) с
tie.puiuHOstu имеет ~	Р^^Р-
3
Элементы теории графов
97
Доказательство. Так как граф полный, существует биекция
ж'1'г ребрами и неупорядоченными парами вершин, а их количс-
(тво равно сп -	2~  
Теорема 3.3.2. Число ребер Р непустого неориентированного
графа Ьсржа без петель, содержащего п вершин и к компонент
^яяиости, удовлетворяв.™ неравенству
п — к^Р hii.
Доказательство. Рассмотрим связный граф с п вершинами
в минимальным количеством ребер. Очевидно, это дерево, содер-
жащее п — 1 pe6j>o- При вычеркивании из дерева каждого 1>ебра
количество компонент связности увеличивается па 1, поэтому для
того, чтобы получить к компонент связности, необходимо исклю-
чить к — 1 ребро, поэтому минимальное количество ребер равно
п — 1 (А, — 1) — п — к.
Рассмотрим теперь граф с максимальным количеством ребер.
Очевидно, каждая его компонента связности - полный подграф.
Докажем, что все компоненты связности нашего i-рафа, кроме од-
ной, СОСТОЯТ ИЗ ОДНОЙ ТОЧКИ Пусть /("i И К-2 _ компоненты связнос-
1и,	= р, |/<2 = Q, р q > 1. Выберем вершину г € К?, уберем
из графа все ребра, выходящие из х в К% и соединим х со всеми
вершинами из К\. Количество компонент связности не изменится,
а количество ребер изменится на р — (у — 1) = р — <7 + 1 >0, что
чротиворечит максимальности количества ребер Таким образом.
к-1 компонента связности одноточечна, а одна - полный подграф
Си — к 4- 1 вершиной и C„_fc+I ребрами. 
Следствие 3.3.1. Граф с п вершинами, для которого Р >
связен.
Это следует из предыдущего результата при к = 2.
Приведем еще одно достаточное условие связности графа.
Т юрема 3-3.3. Неориентированный граф Gen вершинами
п‘акой, что для любых двух его вершин х и у сумма р(х) +р{у)
~ 1 связен, причем любые две его вершины могут быть соединены
длины нс больше, двух.
Доказательство. Степень каждой вершины графа удовле-
1е°ряет условию р(а) п — 1. Пусть х и у вершины, которые
лезя соединить цепью длины 1 или 2. Тогда эти вершины не
98
3 Элементы теории графг^
связаны между собой и каждая из остальных п — 2 вершин
не связана либо с х. либо с у, таким образом.
Р(я) + Р(у) < 2(п - 1) - 2 - (п - 2) = п - 2,
что противоречит условию теоремы. 
Определение 3.3.8 Пусть к € Н Связный граф G
(X,U,M) называется к-связным если:
1) существует подмножество До С А’, |Лр = к, такое, чад
подграф, порожденный Х\Ло, несвязный или одноточечный
2) никакое подмножество Л С А, Ч < к не обладает таким
свойством.
Число к называется числом связности графа.
Пример 3.3.5 Граф G па рис. 3.3.7 2-связный, а граф G, «в
рис. 3.3 8 3-связный
Рис. 3.3.7
Элементы теории i ряфов
99
Определение 3.3.9. Пусть G = (X, U, М) - связный граф. Вер-
шина Е А' называется точкой (вершиной) сочленения, если
подграф, порожденный X \ xq, несвязен.
Замечание 3.3.2 Граф G будет 1-связным тогда и только
тогда, когда он содержит хотя бы одну точку сочленения
Пример 3.3.6. Очевидно, что в графе G на рис. 3 3 9 вершина
*5 будет точкой сочленения, гак как се удаление приводит к появ-
лению грех компонент связности в новом графе (7| (см. рис. 3 3.9,
33.10).
Рис. 3.3.9
100
3 Элементы теории гр»
Рис- 3.3.10
Определение 3.3.10 Пусть G = (X, U, М) связный граф
и Xq € X - точка сочленения. Вершина j-q называется точке!
простого сочленения, если &та вершина связала с каждой комы-,
нентой связности подграфа, порожденного X \ zq, ровно едины
ребром.
Пример 3-3.7 а) Вершина щ графа G из примера 3.3 6 буди
точкой сочленения, но не точкой простого сочленения, йк как оно
инцидентна двум веткам ui и и?. которые связывают се с одмяД
компонентой связности в графе G'i (см. рис. 3 3 9).
б) Вершина (см. граф G? на рис. 3.3 11) будет точи®
простого сочленения.
Рис. 3.3.11
з.
Цементы теории графов
101
Пример 3.3.8. Каждая вершина дерева, не являющаяся ли-
	_ точка простого сочленения.
Теорема 3.3.4 Пусть 67 — (X. U, М) - связный граф, X 3.
, л чтобы zo Е X была точкой сочленения, необходимо и
достаточно, чтобы существовали вершины а,Ь^Х, такие, что
^^'.дал цепь, их соединяющая, проходит через вершину zq.
Доказательство. Пусть zq точка сочленения Тогда граф
- G \ Я!(Ь полученный из G удалением вершины zo и всех инци-
делтных ей ребер, будет несвязным, следовательно, содержит хотя
бы две компоненты связности. Возьмем в одной из них вершину а, в
другой вершину Ь. В исходном графе G каждая цепь, соединяющая
с и Ь, будет щюходить через zq, иначе эта цепь соединяла бы их
р в графе (7[, что противоречит тому, что они лежат в разных
компонентах связности.
Обратно, пусть существуют такие вершины а и Ь, что каждая
Кив, их соединяющая, проходит через Xq. Рассмотрим граф Gi =
G\xe- В этом графе а и b не соединены никакой цепью, следова-
тельно, Gi несвязен и - точка сочленения. 
Определение 3.3.11 Пусть G = (X.U,M) - связный граф.
Рассмотрим отображение р : X х X > No, сопоставляющее каждой
паре вершин наименьшую из длин соединяющих их цепей. Будем
считать, что p(z,z)=0. Это отображение будем называть рассто
«иис.и или геодезической метрикой на графе
Предложение 3-3.2. Расстояние обладает следующими тре-
мя свойствами;
I. p(z.y) 0; р(х,у) = 0&х = у,
2 р(х,у) = р(у,х\,
•3. р(х, z) р(х, у) + р(у. г).
Эти трИ свойства известны как аксиомы расстояния. Данное
’Федложсние позволяет сказать, что связный граф с введенной
’аким образом метрикой представляет собой метрическое про-
CJ1lPancmeo.
Определение 3.3.12 Пусть G — (X,U,M) - конечный связ-
*|,>1й граф, х С X. Величину
tl(x) = max р(х, у)
у£А'
(3.3.1)
102
3. Элементы теории /]
назовем удаленностью вершины х.
Вершину ice с X. такую, что
d(:r.o) =Biind(3:),
XGX
(З.з:
назовем центральной вершиной графа, а величину г<; — тшф
- радиусом графа
Аналогично вершину xi £1, такую, что
d(xi) = maxd(x),
(3.3.3)
назовем периферийной вершиной графа, а величину R^ = inaxtKi'.
хех 1
- диаметром графа.
Предложение 3.3.3. Для любого конечного святого графа G
fG На < 2ГС-
Доказательство. Первое неравенство очевидно. Для докиф
тельства второго рассмотрим периферийную вершину То, для М
торой	।
d(xo) — Rr, — max d(y) — max max p(y. z}.
yex yeX xgx
Так как граф конечен, все максимумы и минимумы достигахяв
поэтому существует такая z$ Е X  Rc - р(хо,2ц). Пусть |Л
центральпая вершина, тогда
Rc - p(^u,zo) р(хо.?/о) + р(уо,ло) $
maxp(x,yo) + uiaxpQ/o.z) = 2d(i/0) = 2гсЧ
гСА'	z(.A'	<
Пример 3.3.9 В графе G на рис. 3.3.12 р(х2,хв) = 4, «/(г?)0
4, d(x\) — 3, d(xa - 2), d(xr.) = 3, d(n) = 3, d(xe) =* 4. Всрни”я
X2 и Хб периферийные, вершина xj центральная, г — 2. R
Элементы теории графов
103
Теорема 3-3.5. Пусть G = (X, U, М) - конечный связный
граф, То € X. Если То периферийная вершина, то она не явля-
ется точкой сочленения.
Доказательство. Так как граф конечен, найдется вершина
z Е X : Rfl = p(tq, z). Пусть то - точка сочленения, тогда в графе
G'j — G’\t0 суиучтгвуют по крайней ме.]>е две компоненты связности,
причем вершина z принадлежит одной из этих компонен т. В другой
компоненте возьмем произвольную вершину у. В исходном графе
любая цепь, соединяющая у н г, проходит через то (Т.3-3.4), отсюда
р(у, z) = р(у, То) + р(то: z) > р(то, z) = Re. что противоречит
определению диаметра. 
Теорема 3.3.G (К.Жордана). Пусти G = (X,U,М) ко-
нечный связный граф, в котором существует центральная вер-
^иини. являющаяся точкой простого сочленения. Тогда множе-
ство центральных вершин графа состоит из одной или двух
wPiuuh. В последнем случае эти вершины будут соседними.
Замечание 3.3.3. Условие о существовании точки простого
с°чденения существенно- В графе G на рис. 3.3.13 центр состоит
1рех точек {т1,Х2,Тз}. каждая из которых является точкой
сочленения, по не простого.
10-1
3. Элементы теории граф!
3.4 Цикломатическое число. Де-
ревья. Алгоритм Краскала
Определение 3.4 1. Пусть G = (X,U,M) конечный граф
|Х| = n, U = m и пусть число компонент связности графа ра«й
р. Число
p(G) == тп — п + р	3.111
будем называть цпкломатичсским числом графа.
Пример 3.4.1. В графе G на рис. 3.4.1 имеем: п = 5, тп =4
р 2, v(G) = 4-512 = 1.
Рис. 3 4.1
я Элементы теории графов	105
Предложение 3.4.1. Пусть G = (X, U, М) - конечный г^пф,
и£| — п, [/| = т, число компонент связности графа равно р.
Пусть G' граф образующийся из G добавлением одного ребра
0 Соответствующие параметры графт G' будем обозначать со
^трихом. Положим
p(G) = п- р.	(3.4.2)
Тогда
1) если в графе G' ребро w соединяет вершины из разных ком-
понент связности, то
о(С) = */(67), p(G') = p{G) + 1;	(3.4.3)
2) если в графе G' ребро v соединяет вершины из одной компо-
ненты связности, то
o(G') = o(G) + 1, p(G') = p(G).	(3 4 4)
Доказательство. В первом случае р' — р — 1, п' = п, т’ =
т + 1; во втором случае 2 р' = р, п' = n, rn' = т + 1; из (3 4 1) и
(3.4.2) следует требуемое.. 
Следствие 3.4.1. Для любого конечного графа G v(G) 0.
P(G) > 0.
Доказательство- Рассмотрим вершинным граф Gx,e =
(76,0,0) с гем же, что и у G множеством вершин. Заметим, что
е(СА :сз) — 0, p(Gx,b) = 0. Так как граф G можно получить из
С.г.и добавлением последовательно т ребер, из предложения 3.4.1
получаем требуемое. 
Определение 3.4.2. Рассмотрим цепь р — (хо,щ,Х1,и2,-,
г*1--). Если вершины гц и хк совпадают, цепь р будем пазы-
еак, замкнутой цепью, илп циклом. В дальнейшем мы пс будем
Различать циклы, содержащие олли и те же вершины и ветки и
Сличающиеся только выбором начальной вершины.
Простую замкнутую цепь, содержащую хота бы одпу ветку, на-
чнем простым циклом; если цепь элементарная, цикл элемеитар-
^й. Элементарный цикл также называется контуром™.
13 р	~
л некоторых книгах контуром называют ориентированный эле-
^•‘тарный цикл, то есть такой цикл, псе ветки которого - дуги и конец
>Мой .гути является началом следующей.
106
3. Элементы теории грщ
Цикл, состоящий из вершин и веток любой цени, прохцд^И
одинаковое число раз в противоположных направлениях, i азып?
ется тривиальным. Вес тривиальные циклы отождествим мех»
собой.
Заметим, что элементарный цикл в графе G является прсхдщ,
подграфом G (с.м. определение 3.1.6). Если G граф Бержа, лю!^*
простой цикл в G также является простым подграфом.
Пример 3-4.2. Пусть G - граф на рис. 3-4.2. Рассмотрим д
(ui,U2,U3,u/i,u^,u^). Это простой, но не? элементарный цикл, 
вершина х-z встречается дважды
Определение 3 4.3. Пусть G — (X,U, М) конечный грИ
|{7 = m 1. Предпоаржим, что граф имеет хотя бы один пет}
опальный цикл. Обозначим через AG множество циклов гр»
G (|Д(?| > 0). Введем па всех ветках графа G произвольи
ориентацию (возможно, не совпадающую с исходной) Занумер?
все ветки графа. Пусть теперь для каждого цикла ц и каждой вЯ
nt графа ск это число прохождений цикла через ик в направлен
ориентации, a rjt против ориентации. Определим число
ск - г к. ик G р,
0, ик р.
Тем самым каждому циклу р G Д(7 сопоставляется вектор р &
Й = (p(ui),..., p(w„J).
^.цементы теории графов
107
Замечание 3.4.1. При указанном отображении тривиальному
,(V и только ему соответствует нулевой вектор 0 — (0. ...,0).
ЦИЮ1..
Таким образом, двум циклам р1 и р2 соответствует один и тот
вектор тогда и только тогда, когда один из них получается из
ппутого добавлением тривиального цикла
Определение 3.4.4. Пусть G — (X,U,M) конечный граф,
вакой.что Д(7 > 0. Введем на множестве циклов AG графа
две операции: сложение циклов и умножение на целое число.
Произведением цикла на целое число к 0 будем называть цикл,
пройденный к раз в том же направлении, что и исходный, если
д. > 0, и в противоположном направлении, если к < 0. Если к — 0,
произведением будем считать тривиальный цикл. Суммой циклов
Pi I- Д2 будем называть цикл, который отвечает сумме pi + Дг-
Замечание 3.4.2. Если отождествлять циклы, отличающиеся
на тривиальный цикл, сложение определено однозначно. Можно
показать. что множество ДБ’ относительно операции сложения
циклов образует коммутативную (абелеву) группу.
Определение 3.4.5. Пусть G — (X.U,M) конечный трас}),
гакой.что AG’| > 0 Пусть Д|,...,д^ 6 AG Будем говорить,
но никлы pi.....Цк независимы, есии векторы Д1,. -линейно
независимы.
Набор циклов	будем называть базисом в AG, если
Ръ..../х& независимы и любой цикл р G ДС можно единствен-
ным образом представить в виде линейной комбинации циклов из
йь--,мь;
р = «1 pi + ,.. + «fcPk, где «j,.... at G Z. (3.4.5)
Заметим, что при этом Д ~ 52 atfii
i=l
Теорема 3.4.1. Пусти G = (X, U, М) - конечный граф, тогда
^исло циклов, образующих базис в Дб'. равно цикломатическому
^исЛу pfQ
Доказательство. В доказательстве будем обозначать число
®Чппии через п, веток через т. число компонент связности через р.
’а,1Омннм, что r(G) = rn — п + р. Будем проводить доказательство
”н акцией но т. Если т = 0, то граф вершинный, р = n, v(G) = 0.
1л”стов нет, поэтому теорема справедлива. Пусть равенство верно
Лля т = I — 1. Рассмотрим граф G = (X,U, М), |С/| = I. Этот
108
3 Элементы теории /раз
граф может быть получен из графа G' -	с п±мц L
вершинами содержащего на одну ветку меньше, так что U'} Л
и дтя графа G' ин.чукционное предложение выполнено. ОГюзиа»^
дополнительную ветку нс- Будем считать что при иумерашш
из определения 3.4 2 се номер I. Рас смотрим два случая
«о соединяет две компоненты связности и фа G гогдД»
предложению 3-4.1 u(G') — v(G) Заметим, что число петя^
симых циклов в A(G) от добавления ветки «о не изменит^
так как л избой новый цикл н G проходит через uq одинаковд,
число раз в противоположные стороны, поскольку w0 - ЫЯК
Поэтому векторы, соответствующие этим циклам, имеют
компоненту, равную 0. Значит, базис в AG состоит из и(б')
элементов.
«о соединяет две вершины одной компоненты связности гра-
фа G', тогда по щэедложению 3.4.1 v(G) — v(G') I. Пусть в
графе G' циклы Д1,.... /xt_|, где t— 1 = r'(G'), образуют бжпг.
Добавление uq приводит к появлению в A(G) новых циклов,
для которых в соответствующих векторах t-я компонента ив
равна 0. Без нарушения общности можно считать^ что срцЬ
них есть хотя бы один цикл х, щюхидящий через uq
один раз, тогда в векторе х xj = ±1. Будем считать, 1
х( 1. Базисным векторам jl\,...,/it_| G A(G') । оотвегсхвуют
t-вскторы pi,... ,/xt_| € A(G), для которых t-я компонент
равна 0, поэтому х нс является их линейной комбинаций
значит, число независимых циклов в A(G) по крайней мер
па 1 больше, чем н A(G')- Докажем теперь, что век юры
/11,.. , /Д 1, х образуют базис в A(G) Любой цикл из А(и)
для которого t-я компонента равна 0, линейно вырзжаот
через /1 j,.... /7 j. Пусть у G A (G). а — у( / 0. Рассмот®
/3 = 7 сгх. Pt — 0, поэтому /3 липейпо выражается чс^
Д1,... ,/it-i, а 7 через Дъ- --, Де-i, х- Итак, базис в А.
состоит из t = i/(G) элементов.
Замечание 3.4.3. Можно также доказать, что I) всегда К
жпо выбрать базис состоящий из элементарных циклов; 2) mJ®
базиса не зависит от ориентации и нумерации веток графа. I
L Элементы теории грифов
109
Следствие 3.4.2. Любой набор независимых циклов, число
вторых Р10110 ,jl(G), будет базисом в AG.
Пример 3.4.3. В графе G на рис.3.4.3 рассмотрим циклы щ =
I	и № ~	23,3:4]. Тогда циклом (—pi) будет цикл
L	а суммой pi + Р2 цикл [a:4,xi,X2, ^з,я?4]> г*к как
Р'^'(1,1,0.0,1), М2 - (0,0,1,1,-1), Ml +/22 = (1,1,1,1,0). Эти
никлы будут независимы, так как o(G) = 5- 4 + 1= 2, эти циклы
образуют базис ио следствию 3.4.2.
Теорема 3.4.2 (о дереве). Пусть G = (X,U,M) конечный
Ф*ф, X | — п 2. Тогда следующие условия равное илъны:
1-	G связный граф и не содержит нетривиальных циклов
2-	G не содержит нетривиальных циклов и имеет п - 1 ветку.
2-	G - связный граф и имеет п — 1 ветку.
4	G не. содержит нетривиальных циклов, но добавление любой
ветки приводит к их появлению.
5	G - связный граф, по удаление любой ветки нарушает связ
хостъ.
б-	Любые две вершины графа G люжно соединить единствен-
н</й простой цепью.
110	3. Элементы теории jp
Доказательство. В доказательстве будем обозначать —и
весок через т, число компонент связности через р.	11
1.	=> 2. Так как граф связей, р — 1; G не содержит негрищ,
ааьпых циклоп, поэтому по теореме 3.4.1 ь((7) = 0. отсюда tn-п
p = m-n + l—0итп=п — 1.
2.	3. С? нс содержит нетривиальных циклов, поэтому m(G) -
0, отсюда, так как тп — п — 1, тп п + р = п - 1 - п + р -- 0 и р ]
3.	=> 4. По условию р = I и m - п — 1. Тогда м(G) - m-п -|-р -
п - 1 - п + 1 = 0 и граф не содержит нетривиальных пик*^
По предложению 3.1.1 добавление любой ветки в связном граф-
увеличивает никломатическос число на 1, отсюда по теореме 3.4 [
появляется хотя бы один нетривиальный никл.
4.	5. По теореме. 3.4.1 i/(G) = 0. Предположим, что G со-
держит хотя бы 2 компоненты связности. Тогда по предложению
3 4.1 добавление ветки, соединяющей вершины разных компонент
связности, нс увеличивает цикломагическое число, что противоре-
чит 4. Значит, граф G связен ир=1, отсюда гл. = p(G)+n-p — п-1.
Если теперь удалить из G произвольную ветку, в новом графе!?
получим Тп' = тп — 1 — п — 1 — 1 = п — 2,	= X/(G), п' = .fb
отсюда р' = v(G') ~ m' I- п' = 0 - (п - 2) + п = 2, то есть граф С
несвязен.
5.	6. По условию грае}? G связен, следовательно, любые jjft
его вершины можно соединить цепью, причем можно выбрать
простую цепь, соединяющую эти вершины. Предположим, чтиИ
шествует пара вершин, которые можно соединить двумя разли*
ными простыми цепями. Тогда существует хотя бы одна ветка»,
принадлежащая одной из цепей, но не принадлежащая другС?.-
Удалив ее, мы пе нарушим связности графа, что противоречит 5.
6.	=> 1. Из условия G. следует, что граф G связен. Если 6й
граф G содержал хотя бы один нетривиальный цикл, то удзл®8
из него ветки, по которым никл проходит одинаковое число раз -
рашых направлениях, а также заменив 2 и более прохождения ?
одном направлении па одно, получим простой цикл. Любые две си
вершины можно соединить двумя различными простыми цепями.
что противоречит 6. 
Замечание 3.4.4. Ветка, при удалении которой число к<
цент связности графа увеличивается на единицу, назыпастся^И
стом. Утверждение 5 предыдущей теоремы утверждает, что
Элементы теории графов
111
’ Lk» дерева - мосг-
Определение 3.4.6 Пусть G — (X, U, М) конечный связный
I гРаФ- Подсраф = (Аг, П'.М'), являющийся деревом, называется
(Гидм?йньсм деревом.
Пример 3.4.4 Пусть дан граф G на рис. 3 4.4 Тогда на
рисунке 3-4.5 изображено одно из его остовных деревьев Tj.
Определение 3.4.7. Пусть G —	- конечный граф.
’Ъсгь р : U > RF U {0} - функция на V, которую мы назовем
Особой, а значение р(ц), где u С U, весом ветки и. Если G' =
- подграф, то его весом назовем £2 р(и)-
uelJ'
Теорема 3.4.3 (алгоритм Краскала). Пусть G —
конечный свявчый граф, |Х1 = п, U / 0. Пусть р ; U 4 U
112
3. Элементы теории /рЛ
{0} некоторая весовая функция на U- Для того чтобы!нл^|
остотюс дерево Т с минимальным весом, достаточно собл^о^^
следующий иморитм:
1) выбираем ветку щ с минимальным весом
2) выбираем последовательно ветки uj,_>мп-ь при эгпо^
кам-дом шаге < ыбираем ветку с минимал ным из нсвы^зГ
нъсс весом такую, что она не образует цикла с выбранным^
ранее.
Доказательство. Из теоремы 3.4.2 (пункт 3) следует, что йьв.
|раф, построенный по алгоритму Краскала, - дерево. Докажем,
что Т дерево с минимальным весом. П]>едположим, что р(Г) =
п -1
52 р(п,) пс минимально, то есть существует ос тонное дсрсво^^И
p(S) < р(Т).	(3.4.6)
Пу 1ь - первая ветка в Т, которая пс принадлежит S. Рассмо-
трим Sk = S U tzfc- Очевидно, что Sf- содержит цикл С (в ЭД
теоремы 3.4.2(4)), который проходит через Ufc, заметим также. W
С содержит ветку и такую что и 6 S. и $ Т. (Если бы L1M
целиком содержался в Т, эго противоречило бы теореме 3.4.2(ljr,
Заманим в S ветку и па ветку Uk- Получим подграф S', котс^В
будет деревом, так как связность не нарушена, мы удалил» вЯв>'
принадлежащую циклу С, кроме того, граф S' = St \ {и} имеет*
вершин и п 1 ветку, что достаточно по 1еоре.ме 3.4.2(3). j
Но по выбору щ в алгоритме Краскала p(ujt) р(«)> зна^В
p(S )	p(S), при этом число общих веток у S' и 7’ на одну
чем у S и Т. Продолжая этот процесс, можно преобразования?
Т. при этом вес подграфа не может возрасти. В итоге ПО-ЧУЖ*
р(Т} р(5), что противоречит (3-4.6). 
Пример 3.4.3. Найти Минимальное остовное дерево в гра<1Я
з.
Элсменэ ы теории графов
из
3.4-6. По алгоритму Краскала находим: п = 7;
ни РиС_
1- «1 = (х5, Т6)
2. е2 = (хц, i2)
3. е3 = (х31х4)
4. е4 = (з2, л?)
5- «5 = (zi,z2)
6. ее = (а:6, гг4)
P(ci) = 1
р(с2) = 2
р(е3) = 3
pfej) = 4
р(е5) = 5
р(«б) = 5
р(Т) = 21
3.5 Планарные графы. Формула
Эйлера. Хроматическое число
Определение 3.5.1. Пусть G = (X,U М) - граф. Назовем
?е° метрической реализацией графа G в трехмерном евклидовом
пространстве К3 множество G, состоящее:
I) из множества точек Ус К3 (эти точки называют узловыми),
при этом существует взаимно однозначное соответствие
(биекция) между X и Y f : X -ь Y -,
2) из множества линий (конечной длины) V с К3 (эти ли-
нии называют реберными линиями), при этом сущегтвуег
взаимно однозначное соответствие между U и V h : U —» V.
114
3 Элементы теории граф^
При этом отображения f и h связаны между собой гак, чТо
тройка (x,u,y) е М, то точки /(х) и /(у) будут концами
Л(н)
Теорема 3.5.1. Пусть G = (X, U, М) граф, мнпакеаГ^
ee.pw.wi и веток которого конечны или счетны. Тогда ущестнуец
такая геометрическая реализация G С К3, что реберные лтщП11
будут пересекаться только в узловых точках. (Такую геометр»,
ческую реализацию графа назовем правильной )
Доказательство. Возьмем в пространстве R3 прямую L к
нанесем на нее на равных расстояниях в любом порядке точки
соответствующие точкам х, 6 X (см. рис. 3.5.1). Построим гспе^
столько плоскостей [)„ содержащих прямую L, сколько веток о,
содержится в U (если U счетно, то число плоскостей также счетйЫ»
Каждой тройке (xbUj.xjt) € М сопоставим тройку y,.i>j,yjt. В
v} € Dj - полуокружность в плоскости D31 соединяющая точки у,
и Ук- Множество G =	U {yi,y2i } будет правилыюР
реализацией графа G, так как различные реберные линии моп |
пересекаться только в точках прямой L, причем в узловых точка*
Замечание 3.5.1. Заметим, что не каждый граф может бы'
прави.'1ьно реализован в R2 Граф, который имеет правиль’*
реализацию в IR2, называется планарным а его правильная
зация G - плоским графом.
л Элементы теории графов
115
Пример 3.5.1 Мы докажем ниже, что полный граф с 5 вср-
)Пинами Л5 и граф с 6 вершинами К^з не планарны (см. рис 3.5.2
и 3-5-3).
Определение 3.5-2. Пусть 67 — (У. V) - правильная реали-
зация конечного графа G — (X U, М) на плоскости R2. Рассмотрим
0 -- X2 \ G дополнение G. Назовем точки из G линейно свя-
яО’«нял<п, если их можно соединить непрерывной кривой конечной
Л’ины, не пересекающей линий из G.
Легко доказать, что линейная связанность является отноше-
нием эквивалентности. Соответствующие классы эквивалентности
^овем регионами, или гранями. Очевидно, существует не больше
°АНо110 неограниченного региона. Назовем его внешним регионом,
^Тальпые - внутренними регионами-
116
•3. Элементы теории /раф0
Пример 3.5.2, У графа G на рис. 3.5.4 имеем 2 внутреним
1 внешний регион.

Теорема 3.5 2 Цикломатическое число связного конечного
планарного графа G =	равно числу внутренних реги-
онов его плоской реализации G'. В качестве, базиса циклов можно
шятъ циклы, отвечающие границам регионов.
Пример 3.5.3 Нусгь G' - плоская реализация графа G, пред-
ставленная на рис. 3-5.5- Тогда р((7') - v((7) = 4; i/(G) = т-п+р-
9-6 + 1- 4-
Теорема 3.5.3 (Формула Эйлера). Пусть G = (X В
конечный связный планарный граф. G' - его плоская
трическая реализация. Пусть |Х — п, |£) = т, количв^Ш
3
Э лементы теории графов
117
^^щнов G', включая бесконечный, равно J. Тогда
п — тп + f = 2.
Доказательство. v(G) = тп—п+р, где р = 1 По теореме 3 5-2
1/(6') = / — 1, отсюда / — 1 = m п + 1 и n-m + / - 2 
Замечание 3.5.2. Так как формула Эйлера один из важ-
нейших общематематических результатов, приведем се доказатель-
ство. не опирающееся на теоремы 3 4.1 и 3.5.2.
Доказательство. Преобразуем i-раф в остовное дерево, удаляя
по очереди его ребра так, чтобы при удалении каждого ребра
граф оставался связным. Заметим, что при удалении |>ебра число
регионов уменьшается па 1, так как при эгом либо пропадав!
один простой цикл, либо два простых цикла превращаются в
один. Следовательно, тп — f не изменяется. Для осговпого дерева
п' - n, т' = и — 1, f = 1, поэтому п' — тп! + /' = 2, а гак как
п' = я, тп' — f = m — f, то и п — тп +- f = 2. 
Предложение 3.5-1. Каждый планарный граф мооюет быть
правильно реализован на сфере и обратно, если граф моэккт быть
правильно реализован на сфере то он планарен.
Доказательство. Опишем отображение из сферы на пло-
скость, называемое стереографической проекцией Пусть плоскость
касается сферы в точке S (в "южном полюсе"). Диаметрально
чрогииоположпую точку сферы обозначим /V ("северный полюс").
Рассмотрим центральную проекцию с ценцюм N Она взаимно
одно шачно отображав! сферу без точки ;V па плоскость. Пусть
т*‘перь граф имеег плоское представление. Расположим сферу так,
чт бы точка S была бы внутренней точкой какого-нибудь регио-
на Тогда отображение, обратное14 стереографической проекции,
Переведет правильную реализацию па плоскости в правильную
Реализацию на сфере Обратно, правильная реализации на cc|>ej>e
“преходи г в плоскую при стереоцэафичсской проекции, если точка
лежит внутри какого-то региона. 
бесконечно удаленная точка плоскости перейдет при этом и точку
118
3. Элементы теории
Следствие 3.5.1. Для правильной реализации грифа G насфе
ре. справедлива фюрмула Эйлера п~ тп i- f — 2
Определение 3.5.3. Пусть К многогранник в R Назовем
его звездным, если существует внутренняя точка многогранно®
хо, такая, что для любой точки х, лежащей на поверхности много-
грапника. весь отрезок [хо,х] принадлежит К. В частности. з»Л
свойством обладают выпуклые многогранники.
Следствие 3 5.2. Пусть дан звездный многогранник А' сп
вершинами т ребрами и f гранями. Тогда справедлива фор^В
Эйлера п - т 4 f = 2. (Именно эту теорему Эйлер опубликовал*
1758 году.)
Доказательство Возьмем такую сферу М, что многогрннн|11
К лежит внутри соответствующего шара, и рассмотрим ценграву
ную проекцию сферы на многогранник с центром в точке то-
этой проекции остов многогранника, го есть все его вершины
бра, перейдет в правильную сферическую реализацию HCKOicPf*1
графа G для которого справедлива формула Эйлера 
3-
Элементы теории графов
119
Формула Эйлера даст необходимое условие планарности графа.
Предложение 3.5.2. Графы и Кз,з не планарны.
Доказательство. 1. Рассмотрим граф К$ (см. рис. 3.5.2) -
полный псорграф Бержа без петель. Здесь п = 5, тп = 10. Пусть
существует его плоская реализация тогда по формуле Эйлера
/ = 2 - п. + m — 7. Так как граф не имеет кратпых |>ебср. каждый
регион ограничен не менее чем 3 ребрами, при этом каждое ребро
граница двух регионов. Поэтому, просуммировав границы всех
регионов, получим
2m = 20 > 3/ = 21.
Это противоречие доказывает, что К$ не планами.
2. Граф Ддз (см. рис. 3.5.3) содержит 6 вершив и 9 ребер.
Это двудольный 1раф: множество его вершин разбито па два
подмножеств Xi — {Х1,т2,ягз} и Х2 = {х4,Т5,Хб}, причем каждая
вершина из Xi соединена с каждой вершиной из Х%. Аналогично
случаю I предполагаем планарность графа и получаем из формулы
Эйлера / = 2 — 6 + 9 — 5- Заметим, что двудольный граф не можег
содержать циклов длины 3, поэтому каждый регион ограничен не
менее чем 4 ребрами, поэтому
2m = 18 > 4/ = 20.
Это противоречие доказывает, что Кзд не планарен 
Замечание 3.5.3. В практике школьных математических
кружков традиционна интерпретация задач о пепланарпости гра-
фов и Кз.з как задач "о пяти столицах'' и "о 3 домах и
3. Элементы теории 1раф (
й \ццах". Первая задача обычно формулируется так: из tJ,
’чти государств отправились послы к соседям. Возможно д*.
дороги, по которым едут послы, ис пересекаются нщ*.
>столиц? Формулировка btojwS задачи. в деревне три
\*вдлодц» г. разной водой. Можно ли соединить каждый дом.
У > катодном дорожками так, чтобы они пересекались голы,,,
Чв и колодцев9
к^%зывастся, по крайней мере один из двух ЭТЙХ rpacU^K\
S смысле содержится в любом непланарном графе.
ес4Чеде.чение 3.5.4. Назовем граф G\ редукцией грЯМ
пн.’’ может быть получен из G следующей операцией: вссЛ,
соц' Тепени 2 вычеркиваются, а проходящая через вершину пар-.
ред%; ребер заменяется на одну (см. рис 3.5.8, там гр^^И
Чуется до графа Gj).
Рис 3.5.8
Тсор
(136)) Ча 3.5.3 (К КураТОВСкий (1930), Л.С.ПонтряЧР’
o£s*> ль, (ля того чтобы конечный нсорграф был планаряылг. ж
Чц i достаточно, чтобы он нс содержал подграфов,
чеобз^ или i^'j.3-
Зиме, имость этого условия следует из предложения 3 5—
гокям |1’’Иие 3.5.4. Теорема 3.5.3 была опубликована К KyF*
кежров J930 г. За 4 года до эгого профессор МГУ П
эт<4 TtJpi 1>едл<>жи.1 студен гам задачу: доказать утверждай
пойТС.Г1,Ч1. Через неделю один из студентов, 18-летпий с*
'грягип. принес решение. П С.Александров решил, W
Элементы теории графой
121
аДача б,,,иа '-'ишком проса ой и публикации нс заслуживает. В
5 пад1,ой литературе теорема называется теоремой Куратовского,
р отечественной - Понтрягина-Куратовского.
Теорема 3 5.3 оказалась чрезвычайно важной при конструиро-
вании печатных плат, в частности материнских плат компьютеров.
Так как линии соединения не изолируются, существенно размес-
тить их па плоскости без пересечений
Следствие 3.5.3. Если G - дерево, mo G планарный граф.
Доказательство. Так как G дерево, оно не содержит циклов,
поэтому не может быть редуцировано к графам Kt, или Адз, со-
держащим циклы. По теореме 3.5.3 граф G планарен. 
Замечание 3.5-5. Операция ]х*дукпии графов используется
также для нахождения дипломатического числа графа v(G) (см.
опр. 3.4 I). Можно доказать, что любой связный граф может
быть редуцирован до букета петель графа с одной вершиной и
г петлями, при этом м(б») — г |8 ]. Заметим также, что операция
редукции переводит простой граф в простой (см. опр. 3.1.6).
Определение 3.5.5. Будем говорить, что связный граф G =
(-V. (У, М) допускает правильную раскраску вершин, если можно
окрасить все eix» вершины так, что любые две соседние вершины
окрашены в разные цвета. Граф будем называть р-хромагическим,
он может быть правильно раскрашен в р цветов, по любая его
раскраска в р — 1 цвет по будет правильной. В этом случае чисто р
1^зываегся хроматическим числом графа G и обозначается 7(G).
-ели р = 2, граф называется дихроматическим.
Пример 3.5.4. Графы СЛ и (7? на рис. 3.5.9 и 3.5.10
дут соответственно 3-хроматическим и 2-хроматичсским (би-
•Уматическим).
122
3.
Элементы теории
тРафпн
Теорема 3.5.4. Пусть G = (X,U,M) хонпный связный
граф- Для тони чтобы граф G был бихроматическим, н обходи#
и достаточно, чтобы он не содержал циклов нечетной длины, I
Доказательство. Пусть граф G - бихроматический, тогл*
каждый ело цикл также бихроматический. поэтому между вери1й'
нами, окрашенными в один цвет, буДст четное чиспо ребер отсюД*
длина всего цикла четна.
Обратно, пусть все циклы в G имеют четную длину. Окра**
произвольную вершину х € X в белый цвет, все соседние t г
вершины в красный и гак далее. Так как число вершин коне"11*’,
в результате либо все вершины будут правильно окрашены,
в процессе окрашивания дойдем до вершины у, которую пу*^
окрасить в два цвета. Если что произойдет, значит х и у соСД*1*
ны двумя цепями одна из которых имеет четную длину, ДРУ01*
з.
Элементы теории графов
Г23
сче1ную. Объединение этих целей образует цикл, который имеет
e4eTfTVio длину, что противоречит условию. 
Замечание 3.5.6. Отметим, что в общем случае граф назы-
вается двудольным, если множество его вершин разбито па два
ислсрссекающихся подмножества (доли) так, что вершины из одной
Доли не являются соседними Очевидно, бихроматический граф
Двудольный. Таким образом, теорема 3-5-4 дает необходимое и
Достаточное условие того, чтобы граф был двудольным. В этой
Формулировке теорема была доказана Д.Кёнигом в 1936 г.
Определение 3.5.6. Граф G = (X,U,M) будем называть
гН1фом р-го рода, р Е No, если существует правильная реализация
Фафа G на двумерной замкнутой ориентированной поверхности
Рола р. то есть на сфере с р ручками (обозначение этой сферы Sp)
124
.3- Элементы теории i-Л
Аналогично случаю плоскости можно определить понятие1рсги
она, только здесь не будет внешнего 1>егиона Два региона на ыва-
югся соседними, если у них есть общая линия границы.
Назовем правильную реализацию связного графа G без моСЛ®
на Sp картой (обозначение G). Будем говорить, что карт прлвиЛ*’
но окрашена, если любые два соседних региона имеют разные Ц»г
та. Обозначим через 7(G) минимальное число цветов, необходим**
для раскраски карты G. Например, на рис. 3.5.14 мяч правязь**1'
раскрашен в 4 цвета.
j Элемсити теории графов
125
Назовем минимальное число цветов, необходимое для правиль-
ной раскраски любой карты на поверхности Sp ароматическим
числом поверхности (обозначение 7(.S’p))_ Очевидно, что
7(SP) = max 7(G).
Лс.н,
В 1890 году П.Хивуд выдвинул гипотезу, которая была дока-
зана в 1968 году для всех р, кроме р = 0, немецким .математиком
Г.Рингслем и американцем Дж. Япгсом.
Теорема 3.5.5 (Рингсль, Янгс). Пусть Sp двумернаяламк
путая ориентируемая поверхность рода р 1. Тогда
1(SP) =
7 + ф1 + 48р
2
7(Sj) =
7 + v/97
2
= 8.
Замечание 3.5.7 (о гипотезе 4 красок). Первым истори-
1е<:ки наиболее трудным и интересным является случай обычной
4*ры (р — 0). Легко доказать, что задачи о раскраске карты
сфере и плоскости эквивалентны. Гипотеза о том, что для
равилыюй окраски плоской карты достаточно 4 красок, связана
: именами нескольких выдающихся математиков: А. де Моргана.
126
3 Элементы теории гр^
Л.Кэли, сэра У.Гамильтона (создателя кватернионов). Вопрос Мо*
тавиди пс1>ед де Морганом его студенты братья Гутри в 1852 го.- '
Дс MopifeH сообщи* его Гамильтону, который также не знал лоидта
тельства этого факта. Второй раз вопрос о 4 красках был по<чацдС(3
А.Кэли в 1878 году на доедании Лондонского математически^
общества.
Независимо от них проблему четырех красок поставил ещс в
1840 году немецкий математик Август Мёбиус.
Замечание 3.5.8. Очевидно, трех красок недостаточно Н
раскраски произвольной карты (см. рис. 3.5.15). При этом из-
вестно, что любой планарный i раф, пе содержащий треугольников.
3-раскрашиваем (результат М.Грёчела).
При попытке доказать гипотезу 4 красок П.Хивуд доказал 
1890 г. следующую теорему.
Теорема 3.5.6 (о пяти красках). Любую плоскую
можно правильно раскрасить в 5 цветов.
Доказательство. Сопоставим карте плоский граф следу»°^рУ
образом внутри каждой области отметим по точке, это ЭДУ
вершины графа соединим две вершины 1>ебром тогда и тл
тогда, когда страпы граничат друг с другом Очевидно, пР8вЯ^д1
раскрашсппон карте соответствует правильно раскрашенный
и наоборот. Этот 1раф не содержит петель, но может садеР3^ь
кратные ребра. Однако если мы умеем правильно раскратн1ПЧ
з.
Элементы ТСОрИИ 1 рифов
127
граф бег кратных ребер, этого будет достаточно для доказатель-
ства теоремы. Таким образом, нам надо доказать что каждый
jjiocKKii граф Ьержа без нетель нс более чем 5-хроматический
Докажем сначала следующее утверждение: в любом плоском
граф'* найдется вершила степени не больше чем 5 Действительно,
по формуле Эйлера (теорема 3.5.2)) число регионов f = 2 — п 4-т.
у го же время каждый регион ограничен по менее чем 3 ребрами,
поэтому 3/ $ 2m отсюда 3(2 п + m) 2m и m Зп — б Если
иь» предположим, что степени всех вершин б, то по теореме
3.1.1 получим 2m бп и m Зп, что противоречит только что
установленному неравенству.
Теорему будем доказывать индукцией но числу вершин Если
в < 5, утверждение очевиднб Пусть теорема верна для любого
графа с не более чем п вершинами, п Э 5. Рассмотрим граф G с
n-| 1 вершиной. Пусть хо - вершина G со степенью не больше 5.
Обозначим через Лг множество вершин, смежных с хо. Возможны
2 случая.
1. |Л'	4. Граф G \ t.q по предположению раскрашиваем в
5 цветов, причем вершины из Лг раскрашены только в 4.
Раскрасим вершину xq в оставшийся цвет.
2 \| = 5 В множестве Лг найдутся две несмежные вершины
X) и х-2, иначе N = К5 и граф (7 не плоский (предложение
3.5.2). Граф G', полученный из G'\xo слиянием этих вершин
в одну вершину х, плоский, и но предположению раскраши-
ваем в 5 цветов, причем вершин, смежных с Хц, осталось 4.
Вернувшись к графу G. окрасим X] и х-2 в цвет вершины х,
а Хц в оставшийся пятый цвет. 
Замечание 3.5.9. В 1976 г появилось доказательство гипотезы
красок, основанное па применении компьютерной программы
I Appel W Пакет Every planar graph is Four-Colourable., Bull
•^ruer. Math. Soc., v.82(1976)). Однако при тестировании програм-
была найдена ошибка. До сих пор не ясно, нет ли там других
°Шибок.
Сеорсма 3.5.7 (Ф.Рамсей). Пусти г,Ь 2 - натуральные
^*сла, n _	2. Сели ребра полного неориентированного графа
п покрасить в два цвета (например, с красный и синий), то в Кп
128
3. Элементы теории графой
существует либо покрашенный в один из цветов полный
Кг, либо покрашенный в другой цвет полный под раф К/,.
Замечание 3 5 10. В простейшем случае г = б — 3 п= С2 -
6 теорема Рамсея часто формулируется так: "В любой колпипо^
из 6 человек найдется либо 5 попарно знакомых, либо 3 попарь
незнакомых" Докажем это утверждение.
Доказательство. Сопоставим людям вершины рафа, если
люди знакомы, соединим соответствующие вершины красным реб
ром если незнакомы, сипим. Получим полный граф ребра кото-
рого раскрашены в два цвета. Возьмем произвольную вершину 4
Ее степень равна 5, поэтому из нес выходят но крайней мере 3 ребра
АВ, AC, AD одного цвета допустим красного. Если хотя бы одно
из ребер ВС, BD, CD красное, получим красный ^угольник
вершиной А. Если нет, треугольник BCD синий (см. рис. 3 5.16)
Доказательство общего случая приведено в при южении 2
Замечание 3 5.11. Теорема Рамсея, несмотря на внсшнс ’tf*
стой вид, лежит в основе многих результатов комбинаторна
тематики В частности па. пей основан один из методов при*5"
{ичпепий в экспертных системах.	Н
3 Элементы теории графов
129
Франк Рамсей (1903-1930)
3.6 Внешняя и внутренняя устойчи-
вость диграфов. Ядра графов.
Игры на графах
Определение 3.6.1. Пусть G = (X, h') диграф (см. стр. 71-
'2). Подмножество S С Л будем называть внутренне устпойчи
ew.*i, если
/’(.$’) П S 0.
Обозначим множество всех внутренне устойчивых подмножеств
’1*'1фа б; через 71(G). Числом внутренней устойчивости диграфа
Назовем число
«(G) — max I Si.
Sfc.4(<?)
( Пример 3.6 1. Пусть X некоторая группа людей. Построим
^РЙФ мнений G - (A. F), где i с Е(у) тогда и только тогда.
'til г ихкх'т гот же взгляд на то или иное яв.|Сни<‘. чю и у. Из
130
3. Элементы теории граф^
определения следует, что граф мнений симметричен. Кликен] граф,
G назовем некоторое подмножество So С X, состоящее из лк>ам
имеющих один и тот же взгляд на данное явление. Очевидце
все вершины клики попарно связаны, так что клика это полищ^
подграф Можно доказать, что задача нахождения наибольшей ц
численности клики сводится к нахождению наибольшего ннутрецас
устойчивого подмножества в G — (X, F) дополнении графа С до
полного графа без нетель
Теорема 3.6.1. Пусть G - (X, F) конечный диграф. Тогда
|X|<«(G)-7(G).
(3.6.1)
Доказательство. Пусть р — ^(G) - хроматическое число. То-
гда вершины диграфа G можно правильно раскрасить в р rrwnie
Пусть Si множество вершин, окрашенных в t-й цвет (» — 1,.. р
Тогда
X = St IJ S-2 U... U Sp, Si П Sj - 0 при t j.
Отсюда, учи тывая, что каждое множество St внутренне устойчиво
получаем
|Х| - |Si| + S2| + ... 1- |SP| С p«(G) = 7(G) • o(G).e
Отмстим, что неравенство (3.6.1) используется для нилв*
оценки как «(G). так и 7(G).
Пример 3.6.2 Пусть G - диграф, данный на рис. 3 61 НУ*
S = {х2,^4}- Очевидно, что S - внутренне устойчивое мноЖ*^1 .
Так как любое множество, содержащее 3 вершины графа 6<
будет внутренне устойчивым, то «(G) — 2. Так как 7(G $
нашем случае. 7(G) 5 2 На самом деле 7(G) = 2
3 Элементы теории грифон
131
Рис. 3,6.1
Замечание 3-6-1. Понятие внутренней устойчивости играет
важную роль в теории кодирования, теории архивации информа-
пии и т.д. Впервые понятие внутренней устойчивости применил и
информатике в копие 30-х начале 10-х годов XX века выдающийся
американский .математик и информатик Клод Шеннон- В соци-
ологии понятие внутренне устойчивого множества используется с
середины 50-х годов XX иска
Определение 3.6-2. Пусть G = (X.F) диграф Подмноже-
ство $ С А будем называть внешне устойчивым, ecjin Vx .S'
Выполняется
F(x) П S 0
Или. цТ0 ранноси-п.но
(X\S')c F '($).
Обо 1ничи.м множество всех внешне устойчивых подмножеств гра-
*^а G через H(G). Числом внешней устойчивости диграфа G
Н;1‘овсм число
(3(G) = min SI.
5(.Ц(6'}
3-
цметим, что если .множество .4 впейте устойчиво. любое иодмно
*'Т1пи .-Г .4 с .4' С V также внешне устойчиво
Пример 3.G.3. Ilycib G| диграф, данный на рис. 3.6.2 Toi да
’'•taKoe одноточечное множество вершин нс будет впейте у<тойчи-
'1м .Любое двухточечное множество, например 5=	будет
'"‘iiiDc устойчивым. Значит. — 2.
132
3 Элементы с рии
Клод Шеннон (1916-2001)
Если же рассмотреть граф G па рис. 3 6.1, то мпожегпю
S = {х1,хз} будв! вне..... устойчивым. Так как одноточечны
множества в G пс будут внешне устойчивыми /1(G) = 2.
Замечание 3.6.2. Исторически задача, связанная с поняти’*’
^лсмситы теории графов
133
I |Е1 внешней устойчивости, возникла в средневековой Италии
""^.р^дсвие минимальною числа надзирателей в тюрьме) В на-
Lonuice в!Н;мя понятие внешней устойчивое! и п]>именяе1СЯ на nj><>
1£1е (создание приборов контроля), в цмономикс (удобство
Га,-,.подения панели приборов) и г.д.
' Оир|!Дсленис 3.6.3. Пусть G (X F) - диграф. Подмно-
^рерно S С X будем называть ядром графа G. если оно одно-
5ремепно и внешне, и внутренне устойчиво, го octi
1. Е(5)П5 = 0;
2. V® Ь' выполняется Е(т) П S 0.
Пример 3 6 4. Если G граф из примера 3.6.2, то 5 {яи^з}
будет ядром.
Замечание 3.6.3. Из определения ядра следует, что диграф,
у которого н каждой вершине петля не имеет ядра. Бывают it
Ьграфы без петель, не имеющие ядра. С другой стороны, ди-
П>аф из примера 3.6.2 имеет два различных ядра: 5\ = {^1,13}
Замечание 3.6.4. Понятие ядра оказалось чрезвычайно важ-
ным в теории игр (в частности, в конфликтологии), в экономике,
ядро равновесия) и т.д. Поэтому столь важной оказалась зала ia
нахождения ядра.
Теорема 3.6.2. Если Sa ядро диграфа G = (X, F), то
/?((?) |So| С o(G).
Доказательство. Так как So внутренне устойчиво |5’п|
KG). Гак как So внешне устойчиво, fl{G) С '5’и'.И
Пример 3 6 5. Пусгь G’i диграф, данный па рис. 3-6.2 Тогда
“(С) — ]] /?(<?) — 2. Значит, в силу теоремы 3.6.2 G не имеет ядра.
Теорема 3.6.3. Пусть G = (X, F) диграф с ядром S. Тоади S
-Максимальное (по включению) подмножество среди внутренне,
тойчивых подмножеств в /1(G) п*о есть если -V/ С 4(5’) и S С
то Af — S.
Доказательство. Предположим противное, пусто сущее-гнует
£ 4(5), S С А/, Al / S. то есть существует х Е Af, х S- Так
•$' - ядро, то но определению внешне устойчивого множества
134
3 Элементы теории трафо
F(x) Г S # 0, тем более Р(т.) С\М / 0, но это противоречит го
что М внутренне устойчиво. 
Теорема 3.6 4. Пусть G = (X, F) - симметричный15
бел петель. Пусть S максимальное (по включению) подмноэ^
ство среди внутренне устойчивых подмножеств в A(G Тогда. S
- ядро
Доказательство. Пусть x$S. Предположим что F(x)f\S’=0
В силу симметричности 1рафа G имеем F(S) П х — 0. Пол )жин
М = S U х. Тогда F(M) Г) М — 0, гак как F(M) fl Al — (F(S) и
F(x)) П (5 U ж) = (F(S) П S) U (F(x) Г) S) U (F(x) П х) U (F(S) л«).
Каждое из этих четырех множеств пусто: F(S) Л S — 0, гак как $
внутренне устойчиво, F(x) CiS = 0 по предположению, F(x, ? I
0, так как нет петель, F(S) Л х = 0, так как граф симметричен.
Следовательно, F(Af) Л М = 0, то есть М внутренне устойчивое
множество, содержащее S, что противоречил максимальности S
Значит, F(x) Л S / 0 для любого х G X \ S, это означает’ что S
внешне устойчиво, то есть S ядро. 
Предложение 3.6.1 (Алгоритм нахождения ядра » к0
нечном симметричном диграфе без петель). Пусть
(X, F) - описанный в условии дигрш|>. Возьмем произвО-ЧьИ.
вершину Х| С X. Если при всех х G X \ {ii} F(x) Лх1 / 0, Я i1'
- ядро. Иначе существует x~i G X \ {х|} такой что Ffx-j) П
В силу симметричности графа тогда и F(xt) Л t-j = 0- т0
,0То есть его матрица смежности симметрична.
^.чемснгы теории i рлфов
133
-- {-ti-.'tj} внутренне устойчиво. Если не существует .т3 6 -V \S|
акого. чт<)	=	ЯЛР°? иначе рассмотрим -S’j —
|rj. тз}- Так как Е(х.з) П.5’| — 0, то и ?'(S’i)Пяз = 0. то есть
вНУ1р<‘нпе устойчиво. Продолжим этот процесс. В силу конечное-
и гриф** он закончится на максимальном внутренне устойчивом
мно>ке< тие S*fc = {xi,.... Jk ]} По тещэеме 3.6.4 это я ipo.
Замечание 3.6.5. Для несимметричных конечных диграфов
: 5ез петель был разработан другой метод нахождения ядра (если
()цо существует), основанный на понятии рекурсивной функции.
Предложи.! этот метод в 1939 г. английский математик Гранди,
занимавшийся теорией игр.
Определение 3.6-4 (функция Гранди). Пусть С = (X.F)
диграф Бержа бел нйячь. Функцию д : X —> Nq будем называт ь
функцией /'ратной. если
£/(х.) = min{fc € No : к £ </(Е(х,))}, г = 1 ••, А' ,
где у|7’(х,)) множество значений функции G’ на множестве k'(xt).
Замечание 3-6-6- В диграфе Бержа иногда можно определ-
ить лиг функции Гранди, иногда ни одной. Например. ;inrpatj) на
рисунке 3 6-3 пс имеет функции Гран,1И. а граф на рис. 3-6.4. 3.6.5
имеет две функции Гранди.
Рис. 3.6.1
136
3 Элементы теории гр^
Предложение 3.6.2. Если диграф G = (X, F) имеет функции
Гранди g и для некоторого ж € X оказывается что Е(х) = 0, mu
ff(-r) = 0.
Теорема 3.6.5. Пусть G = (X F) связный конечный сим-
метричный диграф без петель. Для того чтобы диграф G был
р хроматическим с р |Х необходимо и достаточно, чтобы он
обладал функцией Гранди со значениями 0,1,... ,р - 1 и не <уще-
стоовало бы функции Гранди с максимальным значением меньше
Р- 1.
Доказательство необходимости. Пусть G обладает фупк-
цией Гранди. Раскрасим вершины, для которых д(х) — 0 в первой
цвет, вершины, для которых д(х) — 1, во второй цвет, вершины,
для которых д(х) = р — 1, в р-й цвет. В силу симметричности i рафа
эта раскраска правильная Для доказательства того, что G целым*
раскрасить в q цветов при q < р, нужно использовать связиОСТ*
графа G и отсутствие функции Гранди с максимальным значС1и,Г1'
</<р-1. 
Определение 3.6.5. Диграф G = (X, F) называется прояр^~
сивно конечным если существует fcgH такое, что для любой
шины х б X любой (необязательно простой) путь, начинают*’^
в этой вершине, имеет длину не больше к
Пример 3.6.6. Пусп, G = (X.F) - бесконечный
данный па рис. 3.6.7. X = Z, F(2n) = {2п — 1,27г 4- 1}, п
.Длина любого пути не больше I, поэтому G щюгрессивно копе**'
у Элементы теории графов
137
G
-3	-2-10	1	2	3
Рис. 3-6.7
Замечание 3.6.7. Если диграф G - конечный и связный, го
прогрессивная конечность означает, что G не имеет замкнутых
путей.
Теорема 3.6.6. Пусть G — (A', F) - связный диграф Бержа
без петель, при лтом G прогрессивно конечен. Тогда G имеет
функцию Гранди, притом только одну.
Следствие 3.6.1. Пусть G = (A, U,M) конечное дерево.
Пусть G дигрмф». полученный из G заданием произвольной
ориентации на его ребрах. Тогда G имеет функцию Гранди, при-
пю,и только одну.
Доказательство. Пусть | [7] = т Тогда любой путь на G имеет
Длину не больше т, го есть G прогрессивно конечен и по георе.ме
3.6.6 обладав! функцией I ранди. иритом единственной. 
Теорема 3.6.7. Пусть G = (X, F) - диграф, имеющий функцию
• ранди. Пусть S — {z € X : g(x) = 0}. Тогда S будет ядром графа
G
Доказательство. Из определения функции Гранди следует,
что множество S внутренне устойчиво. Пусть теперь х € X \ S.
Г<»гда у(х) > 0, это означает, что y(F(x)) Э 0. В силу этого найдется
дУга из х до у G S- Следовательно, S внешне устойчиво, значит, S
Ядро 
Следствие 3-6.2. Пусть G — (X, F) - связный, прогрессивно
конечный диграф Бержа бея петель. Тогда G имеет ядро.
Следствие 3.6.3. Пусть G — (X, F) - конечное ojmenmupo-
^нное дерево. Тогда G имеет ядро.
138
3 Элементы теории ipafa
Определение 3.6 6. Пусть G = (X,F) конечный связиад
диграф и а"о G X. Определим игру двух участников А и В
G Жеребьевкой определяется игрок, делающий первый ход (д?°
пустим, это Л). Тогда Л выбираег вершину Х| 6 F(rn). Участии».
В делает следующий ход. выбирая х2 G ^(^1) и т.д. Выпгрываед
тот из участников, который выбирает вершину у е X, такую
что F(y) = 0 (таким образом, его противник не может одела
очередного хода)
Игру, описанную выше, назовем простейшей игрой двух
участников па графе.
Теорема 3.6.8. Пусть связный конечный диграф G ~ (X Г
имеет ядро S и хд $ 8- Тогда игрок, делающий первый ход, имеет
стратегию, которая приводит либо к победе, либо к бесконечной
игре (то есть этот игрок о любом случае не проиграем). Выиг-
рышная стратегия состоит в том, что на кам-дом шаге первый
игрок должен выбирать вершину, принадлем-ищую ядру.
Доказательство. Пусть А делает верный ход. Так как хо$ *>
и S внешне устойчиво, А может выбрать xj G S О F(xq) Ecni
F(xi) = 0, А выиграл. Если пет, в силу внут^геппей устойчивоеш
S игрок В может выбрать х2 только в X \ S. Отметим, что тот, кто
находится в X \S, нс может выиграть так как для любого х£ Х\^
имеем F(x)C\S 0, т.е. F(x) / 0 Значит, А, придерживаясь свое®
страте! ин ибо выиграет, либо игра будет бесконечной. 
Пример 3.6.7 Пусть G - диграф, данный на рис. 3 6.8-
ядром будет S = {хз,з:5,2:7,19,з:1С}. Если хо S, го игрок. Э1
лающий первый ход. имеет- вепможноеп. по проиграть (Kc^W
этот граф не будет процюс.сивпо конечным.)
I Элементы теории графов
139
Следствие 3-6.4. Пусть G = (X, F) связный, прогрессивно
конечный диграф Бе.ржа без петель и Хц е X. Пусть задана
простейшая игра двух лиц на G. Тогда существует стратегия,
позволяющая одному из .этих лиц не проиграть.
Доказательство Но теореме 3 6.6 диграф G имеет единствен
ную фуркцию Гранди, и множество S = {х G X : д{х) = 0} в
силу теоремы 3.6 7 будет его ядром. Если xq ф S то оптимальную
нс1уи>нгрышную стратегию имеет игрок, делающий первый ход, а
если xq G S и F(xq) 0, то эту стратегию имеет второй игрок, так
как X] £ F(xq) и Xi G X \ S (см теорему 3 6 8) 
Пример 3.6.8 (Простая игра Ним). Пусть даны п кучек
камней (ракушек, спичек). Два игрока по очереди выбирают любое
число камней, но только из одной кучки. (Разные игроки могут
брать из разных кучек.) Выигрывает тот, кто забрал последний
камень.
Для каждой кучки составим дерево состояний. Например, если
р- кучке было 3 камня, ее дерево состояний дано на рис. 3 6 9
'India соответствуют числу камней, которое останется в кучке
'«осле очередного хода). Число вершин дерева 23 В общем случае,
ес,'И! в кучке было к камней, число вершин в графе состояний
Обозначим число камней в i-й кучке, записанное в двоичной
системе, через р(г), например для трех камней g(i) = 11, для 5
g(i} — 101 и т.д Можно доказать, что оптимальной стратегией
«
’Идет такая, при которой при каждом ходе y(i) = 0 (mod 2) в
Фондом двоичном разряде.
ппг
3. Элементы теории граф™»
3.7 Эйлеровы и гамильтоновы
графы. Двудольные графы.
Теорема Кёнига
Определение 3.7.1. Пусть G — (X, U, М) - связный конечш. П
граф. Ц^хкгой никл, содержащий все ветки графа, будем называть
эйлеровым Граф, для которого существует эйлеров цикл, будем
называть эйлеровым, графом.
Теорема 3.7.1 (Эйлер, 1736.) Для того чтобы связный ко-
нечный граф без петель G = (X. U, М) был эйлеровым, необходима
и достаточно, чтобы степени всех его вершин были четными.
Доказательство. Пусть граф эйлеров. Так как i-раф связей,
через каждую его вершину проводит эйлеров цикл, который входит
в вершину но одной ветке, а выходит по другой, поэтому степень
каждой вершины четна.
Пусть теперь все вершины графа имеют четные степени н
Те € X произвольная вершина. Рассмотрим простую нет»
p(xq. tt| ,xt. иг, - -.)- Гак как степени всех вершин четны, эта псы-
может закончиться только в вершине xq. таким образом, чгр®
t.q проходит простой цикл р. Если он содержит все ветки графа-
цикл эйлеров, если нет, удалим все ветки этого цикла из грифе* G
Получим подграф G’i, все вершины которого также имеют чеп'У*0
степень Так как G связен, существует гт € X. через которУ**
Элементы теории графой
141
проходят легки графя G\- Найдем простой цикл /ц, проходящий
через вершину лц в графе Gy. Объединение циклов Ц2 ~ pU/ii будет
циклом в исходном графе. Так как граф конечен, данная процедура
должна закончиться; полученный цикл будет эйлеровым. 
Следствие 3.7.1. Для того чтобы о связном конечном гра
фс без петель G — (X, 17, М) существовала простая цепь, про-
водящая через все ветки гршфа и соединяющая вершины Эд u rj
(такая цепь также называется эйлеровой), необходимо и доста-
точно, чтобы Xi и zo были единственными вершинами нечетной
степени.
Доказательство. Необходимость данного условия очевидна.
Пусть zi и %2 - единственные вершины нечетной степени. Если они
соединены веткой, удалим ее из графа G Получим эйлеров граф.
Дополнив эйлеров цикл веткой (zi, £2), получим искомую эйлерову
цепь. Если же вершины Z; и х? не соединены, соединим их, получим
эйлеров граф и удалим ветку (Z|,Z2) из эйлерова цикла. 
Замечание 3.7.1. В 30-х годах XVIII века была популярна
задача о Кенигсбергских мостах. В фарватере реки Прегель на
холятся два острова Л и В. которые соединены друг с другом и с
берепили С и D семью мостами (рис. 3.7.1). Можно ли пройти по
одному разу по всем мостам и вернуться в исходную точку? Эйлер
доказал невозможность такого обхода, нарисовав граф, вершинами
которого служат берега и острова, а ветками мосты (рис. 3 7.2).
Граф не эйлеров, так как степени всех вершин нечетны, значит,
такой обход невозможен даже без требования вернуться в исходную
точку.
Рис. 3.7.1
142
3. Элементы теории
Замечание 3.7.2. Теорема и следствие 3.7.1 верны даже дм
графа с петлями, если считать, что каждая петля учитывается в
степени вершины с кратностью 2.
Теорема 3.7 1 имеет интересное приложение к задаче обхода
лабиринта. С каждым лабиринтом можно связать граф, верши-
нами которого будут зады лабирин та и точки входа, а ветками
коридоры. Следующая теорема показывает, что любой лабиринт
можно обойти, пройдя по всем коридорам и вернувшись обратно.
Следствие 3.7.2. Я связном конечном графе всегда можно
построить ориентированный цикл, проходящий через все ветки
графп по одному разу в каждом из двух противоположных^'
правлений.
Доказательство/Удвоим данный граф. заменив каждую его
ветку па пару дуг, соединяющих вершины этой ветки в противо-
положных направлениях. В полученном мультиграфе степени всех
вершип четны, поэтому он эйлеров. 
Приведем описание алгоритма Гарри, предложенного в 189а г
для построения цикла ив следствия 3.7.2 Исходя из произвольной
вершины идем по произвольному ребру, причем отмечаем У’*’’
пройденные ребра. В каждой вершине соблюдаем единственное
правило: ребро, по которому впервые попади в эту вершину, пе"
пользуем для выхода только тогда, когда оно является единствен-
ным выходом из этой вершины, все прочие ребра уже пройден^
дважды.
Определение 3.7.2 Пусть G =	- связный коне’’
ный граф. Элементарный цикл, содержащий все вершины 1раФЧ
Элементы теории 1рафон
143
5удем называть гамильтоновым. граф. для которого существует
Цильтонов цикл, также назовем гамильтоновым. Будем налы
9ТЪ тамильтоновой и элементарную цепь, проходящую через псе
?сргпины графя.
Замечание 3.7.3. Гамильтоновы графы ввел в 1857 году
ур Гамильтон. Он предложил игру, названную путешествие по
додекаэдру. Предлагалось обойти по ребрам додекаэдра все его
вершины, ;аходя в каждую но одному разу.
Рис. 3.7.3 Додекаэдр
Замечание 3-7.4. Гамильтоновы циклы имеют прикладное
значение при составлении оптимальных программ совместной ра-
боты машин, в задаче коммивояжера о кратчайшем пути, по ко-
торому он может объехать несколько городов, заезжая в каждый
только по одному разу.
Несмотря на то. что определения эйлеровости и гамиль-
ттжовости внешне схожи, пока не получено необходимого и дос-
таточного условия гамильт о новости графа- Приведем п<*которые
Достаточные условия.
Теорема 3-7.2 (О.Оре, I960.) Пусть G = (X,U, М) прос-
конечный граф, X = п 3. Если для любых двух вершин
выполняется неравенство
р(г.) + р(у) п - \,	(3.7.1)
H'l	3. Элементы теории грЯ
граф будет содержать гамильтонову цепь. Если euuo^i
неравенство
р(х) 4- р(у) > n,	f3 7^
граф будет содержать гамильтонов цикл
Доказательство. Пронумеруем произвольным образом пи,
шины G  г01 ®],.. •, zn -1- Если любая вершина в этой последом,
дельности соединена ребром со следующей, мы имеем гамильтонопу
цепь. Иначе какие-нибудь я* и ^fc+i не связаны ребром Б\ д
говорить, что между ними существует разрыв. Пусть разрыв будет
между жо и Tj. Докажем, что существует такой номер i : 2 i
п— 2, что вершина я, связана с Жо> a rl+i с ц. Если это не так х ц
связана с го, так как между ними разрыв, и еще с р(«о) вершинам
тогда p(«i) < п — 1 — р(ао) ~ 1, что противоречит (3.7.1). Итак,
рассмотрим найденные вершины х, и г|+] и рассмотрим новую
последовательность вершин: To,Tt.х, 1,...,x1,Si+i,Zi+2,... n 1
Эта последовательность содержит на один разрыв меньше. Так как
граф конечен, за конечное число шагов придем к гамильтоновой
цепи.
Пусть теперь выполнено (3.7.2). Существует гамильтонова цепь,
соединяющая две произвольные вершины г и у. Из неравенства
(3.7.2) следует, что найдется вершина z, связанная с х, такая, что
смежная с ней вершина t связана с у. Добавляя к цепи ребра
и (ty) и убирая (fz), получим гамильтонов цикл. 
Следствие 3.7.3 (Г.Дирак, 1952). Пусть G = (X, i Af)
простой конечный граф, |Х| — п 3. Если для любой вершины
выполняется неравенство
р(*) > ”,	373
граф будет гамильтоновы.*.
Пример 3.7.1. Пусть G дан па рис. 3.7 4. Очевидно р(%д
3 > £. Значит, G гамильтонов.
145
I Элемст ы теории 1 рафон
V'
Следующая теорема обобщает теорему 3-7.2.
Теорема 3 7.3 (В.Хватал, 1972.) Пусть G - граф < п верши-
нами, обозначим через di степени его вершин. Расположим эти
степени в порядке возрастания:
d] dz ... dn.
&ли для всякого к такого, что 1 к < 2, истинна 1смпликаиия
dk к drj jt п к
граф G гамильтонов.
Следующая теорема - один из наиболее сильных результатов,
касающихся 1ами.1ьтоновых графов.
Теорема 3-7.4 (У.Татт, 1946). Всякий ^-связный простой
Тючный планарный граф гамильтонов.
Рассмотрим теперь двудольные графы (см замечание 3.5.6).
Определение 3.7.3. Пусть G’ = (Xi U X?,U.M) двудольный
Ф^ф. Набор веток U' с U назовем независимым паросочетаписм,
Сс-1и ветки из U' не имеют ни одной общей вершины. Паросочетание
Чазываетея максимальным, если оно нс содержится ни в каком
другом паросочетании. Максимальное паросочетание называется
Свершенным, если любая вершина графа инцидентна какой-либо
веток паросочетания.
Пример 3.7.2. Пусть G дан на рис. 3.7.5. Набор U1 —
«3,115} будет независимым паросочетанисм
146
3. Элементы теории rp^)]t
Замечание 3.7.5. Описание максимальных независимых па
росочетаний оказалось весьма полезным во многих физических,
химических, биологических проблемах.
Центральное место в теории паросочетаний занимает теорема,
первая версия которой была доказана в 1917 году Фробениусом
Впоследствии тсо{«ма была обобщена Ф.Холлом и Д.Кёнигом (В
некоторых кишах ага теорема называется теоремой Кёпша.)
Теорема 3.7.5 (Ф.Фробениус, Ф.Холл, Д.Ксиш). Путь
G = (X| U X-z,U, М) = (Xi U Xz, F) - связный двудольный dw-
граф причем |Xj = IX2L — « « начала веет, дуг находятся О
X1 Для того чтобы существовало совершенное паросочетанис
U' С U: U’\ — п, необходимо и достаточно, чтобы для любого
Sax, |F(S)| > |5|.
Замечание 3.7.5. Теорема 3.7.5 известна как теорема о свидь-
бах. Вариант формулировки: если есть п юношей и п девушек,
причем для любого подмножества из к юношей, 1 к п, количе-
ство знакомых девушек больше или ранпо к, тогда каждый юноша
может жениться на знакомой ему девушке. Можно придума ь и
более серьезное применение: если п человек должны занять п ДР-'*'
жпостей, причем каждая группа из к человек, 1 к $ п, можгг
заня ть не меньше, чем к должностей, можно сопоставить каждо^У
человеку должность, с которой он справится.
Доказательство Необходимость условия теоремы очсвиД114
- если каждому S С Xi сопоставить множество Si концов ЛУГ’
исходящих из S и принадлежащих совершенному паросочсташ*10’
Элсм^'н гм теории графой
147
к#'”111*1	। -= 1*^ и ^1	^ (**’)- Достаточность (в свадебной фор-
пгровке) докажем индукцией ио п. Если п - 1, имеется 1 юноша
к'одна девушка результат очевиден. Пусть для п — I-1 результат
рфаведлив Рассмотрим n — I. Если найдется такое множество
юношей S, |5| к<1. такое, что множество знакомых им девушек
тоже имеет мощность к, по индукционному предположению
вХ можно переженить друг с другом. Тогда множество Xi \ S
гос1оит из I — к элементов и для него теорема также выполнена,
рассмотрим теперь случай, когда для любых S С Ai |F(5)| > |S .
Выберем одного юношу то и женим его на какой-нибудь из его зна-
комых девушек у0. Для всех S С Х]\{то} выполняется неравенство
I |S’i ? E(S) \ {ро}|, повтому по индукционному предположению
остальных 1 — 1 юношей тоже можно переженить. 
3.8 Упражнения
1.	Привести пример:
(а)	бесконечного диграфа с двумя вершинами;
(Ь)	диграфа Бержа с двумя вершинами и двумя петлями;
(с)	просто™ неориентированно™ графа с двумя вершина-
ми.
2.	(а) Граф G па рис 3.8.1 описать с помощью мультнфунк
пни;
(Ь)	Нарисовать граф, если А' — {11,2:2,3:3}, /•'(ai) =
{Х],х2,я:з}, F(x2) — хь Е(з:3) - 0;
(с)	Найти остов ipacfxi G
148
Элементы теории графов
149
7.	Для графов G и G из предыдущего упражнения построить
матрицы смежности, а для графа G еще и матрицу инци
дентности.
8.	Пусть Gi = (_X'11F1), G-i = (X2.F2) подграфы диграфа
G = (X,F). Переформулировать на языке мультифункций
определение Gj Л G2 и G) U G2.
9.	Пусть Gj дан на рис. 3.8 3. Найги G — G\, если G - полный
граф с 4 вершинами и 4 петлями.
3	Доказать, что в любом простом гра<}ю содержащем хотя бы
две вершины, существуют две вершины одинаковой степени
4	Пусть
/1	2	1\	/1	2	1\
А =	I 2	1	0	,	В = I О	0	0 .
\1	0	0/	\0	0	0/
Найти A U В, Л Г) В,	Ло В,	оА.
5.	Найги такие А и В. что А о В = В о А.
6 13 rpa<J>e G на рис. 3.8.2 ввести ориентацию ребер так чтобы
он превратился в силыю связный диграф G
10.	Пусть (71 и G? даны на рис. 3.8 4. Найт и:
(a)	Gi х G2;
(Ь)	Gi +G2;
(с)	Gj ® G2;
(<i) g^g2-,
(е)	Gi и G2.
150
3. Элементы теории граф^
11,	Пусть J и 'Г даны на рис. 3-8.5. Проверить, что для любого
графа G J х G G, Т + G = G, Т ® G’ “ G.
графов 5 правильных многогрзН'
12.	Составить таблицу попарно неизоморфпых простых связных
графов не более чем с 5 вершинами.	*
13.	Найти числа свя-шости для
ников.
14.	Каково наибольшее число точек сочленении у графа С и
вершинами?	в
151
j. Элементы теории графов
15.	Пусп» G дан на рис. 3.8.6 Найти:
(а)	удаленность каждой вершины;
(Ь)	центральные и периферийные вершины,
(с)	радиус и диаметр графа;
(d)	точки сочленения графа.
16.	Пусть G дан на рис. 3 8 7.
(а)	Найти цикломатическое число графа.
(Ь)	В графе G даны циклы /ij = (ii,X2,^3>^i) и 14 =
(х3,ж5,Х1,хз). Найти pi + р2 € &G-
(с)	Будет ли {рьдг} базисом в AG?
152
Элементы теории
1'Р^фс/ь
17 Состави ть таблицу попарно неизоморфных деревьев с числом
вершин не более 9
8 В i-рафе G на рис. 3.8.8 найти минимальное основное де; ей
Г.
Рис. 3-8.8
19 Доказать, что в полном графе Kr содержится гг~2 остовп»*
деревьев.
20.	В графах Gi — G.j на рис. 3.8.9:
(а)	найти a(G,) и /5(G\), t = 1,2,3,4;
£ Элементы теории грифов
153
(Ь)	найти, если имеются, ядра графов G{, i = 1,2,3,
Pt + Р2 G ДС
4 и
21.	Построить функцию Гранди в графах G] и G2 на рис. 3.8.10.
154
3.
Элементы теории
1Р^фол
h Элементы теории графов
155
23.	Найти все ядра графов Gi, G2, G%, Gi, Gs, Ge, заданных на
рисунках 3.8.10 - 3.8.12.
22. Найти хроматическое число графов G3 и G4 на рис. 3.8 И
156
3. Элементы теории трафОв
24.	Привес-ги примеры графов:
*
(а)	эйлеровых и гамильтоновых;
(Ь)	эйлеровых, по по гамильтоновых;
(с)	гамильтоновых, по не эйлеровых;
(d)	не эйлеровых и не гамильтоновых.
25-	Доказать, что если число вершин графа нс меньше чем
3 - 4П- — 1, то либо сам этот граф, либо его дополнение
содержит полный подграф Кп с п вершинами.
С помощью графов решается большое количество задач для
школьных математических кружков16.
1.	Можег ли в государстве, в котором из каждого города выхо-
дит ровно 3 дороги. быть ровно 100 дорог?
2.	У короля 11 вассалов, каждый из которых живет в своем
поместье. Может- ли случиться так, что у каждого вассал»
либо 1, либо 3, либо 5 соседей?
3.	Собралась компания. Некоторые люди обменялись рукопо-
жатиями Доказать, что число людей, сделавших нечетное
число рукопожатий, четно.
|В Следующие задачи предоставила авторам Е А. Рисе, за что авторы
выражают ей глубокую благодарность.
5. Элементы теории графов
157
4.	Можно ли нарисовать на плоскости 9 отрезков так, чтобы
каждый пересекался ровно с 3 другими?
5.	Из одной заготовки можно сделать одну деталь, а из стружек
от 6 заготовок можно изготовить целую заготовку. Сколько
деталей можно сделать из 181 заготовки?
6.	У царя Гвидона было 3 сына. Из его потомков 100 имели по
2 сына, а остальные умерли бездетными. Сколько потомков
было у царя Гвидона?
7.	Имеется 5 ящиков. В некоторых из них по 5 ящиков по-
меньше, в некоторых из этих ящиков еще по 5 ящиков еще
меньшего размера и т.д. Всего имеется 12 непустых ящиков.
Сколько всего ящиков?
8.	В государстве из всех городов выходит по 100 дорог, и из
каждого города можно проехать в каждый. Одну дорогу
закрыли на ремонт. Доказать, что по-прежнему из каждого
гощща можно проехать в каждый.
9	В математическом кружке у каждого кружковца есть jwbiio
1 друг и ровно 1 враг. Доказать, что:
(а)	число членов кружка четно;
(Ь)	кружок можно разделить на 2 нейтральных кружка, в
которых нет ни пар друзей, пи пар врагов.
10.	В стране любые два города соединены или железной доро-
гой, или авиалинией. Доказать, что один из видов транспорта
позволяет добраться из любог-о города в любой
11.	В гра<]>е каждая вершина синяя или зеленая. Каждая синяя
вершина соединена с 5 сипими и 10 зелеными, а каждая
зеленая с 9 синими и 6 зелеными. Каких вершин больше
- синих или зеленых?
12.	В классе больше 30, но меньше 40 человек. «Любой мальчик
дружит с 3 девочками, а любая девочка - с 5 мальчиками.
Сколько человек в классе?
158
4 П
13.	В кружке 30 человек, каждый из которых любит батг^т
ровно с 15 друт ими. Доказать, что есть хотя бы двое, которы
любят болтать дру! с другом
14	Усадьбы 20 джентльменов соединены 172 дорогами. Дока-
зать, что от любого из них можно проехать к любому др Г( ы.
(возможно, в объезд).
15.	На планете 20 государств. Известно, что из любых 3 хотя бы
2 не обменялись посольствами. Докажите, что посольств пт
более 200.
16.	В квадрате отметили 20 точек. Их соединили друг с другом
и с вершинами квадрата непсресекаютцимися отрезками гак,
что квадрат разбился на треугольники. Сколько получилось
треугольников7
4 Приложения
4.1 Приложение 1. Формула вклю-
чений и исключений
Зафиксируем некоторое непустое множество X. До коп «а
приложения все множества будем считать подмножествами X, в
частности А будет обозначал, дополнение подмножества А до X
Определение Пусть Л С X Функция хл X —> 0 1}
определенная формулой
Ха(х) =
J 1, если х € Л,
1 0, сели х £ А,
называется характеристической функцией множест ва А.
Рассмотрим некоторые свойства характеристической функции
1	. Характеристическая функция пересечения любых подмно-
жеств X равна произведению характеристических функций этих
подмножеств.
„I Приложения
159
Действительно, для любого х G X f] (т) - I тогда и только
i£l
тогда, когда все сомножители равны 1, то есть х €	/ А,.
2	Если А с X, то Хд(г) =1 - »(т) для любого х Е X
Любой х Е X принадлежит либо А, либо А, поэтому уд(.т) +
Хд(г) = L
3	Пусть {Л, : i Е 1} семейство подмножеств X, С = UieJ'^’
Тогда для любого х Е X
1 - хс(х) = ПО - ХА («))•
if/
Так как дополнение С совпадает с пересечением дополнений А,,
утверждение прямо следует из 1. и 2.
4. Пусть Л конечное подмножество X. Тогда
|А| = £ хл(т).
zC-A
Если х Л, то ул(х) = 0, поэтому
52	= 12 Ха(х) = |А| • 1 = |Л .
тех	zea
Формула включений и исключений для характери-
стических функций. Пусть {А, . г Е 1} конечное семейство
подмножеств X, С = (Jig/ А Да* подмножества S С I обоз-
начим через As пересечение Dses -^5- Тогда для любого элемента
ХЕ X
|/|
хс(х)= 52 ( l)JS’,T,xAb(x) = D’l)i+1 52 xAs(x).
sci s-f я	t-i	sc/,'S|—t
Доказательство По третьему свойству характеристических
функций
1 - хг(.т) = Пи - ХлЛт)).
4. Приложения
160
Раскрывая скобки в щюизведенин биномов и собирая вмести сла
гасмыс, соответствующие каждому подмножеству S С I, получаем
г-хС(х) = 52(-1)!5|П<1 **(*))*
5'С/	S6.S
Среди слагаемых правой части одно, соответствующее пустому
множеству, равно 1. Сокращаем его с I в левой части и умножаем
обе части на (—1); пользуясь свойством 1, заменяем Хл.(х) па
scs I
получаем первое равенство. Второе получается группиров-
кой слагаемых по подмножествам одинаковой мощности. 
Пусть теперь все подмножества Л, конечны; просуммировав по-
лученные равенства по всем л Е (J Л, получим следующий резуль-
«е/
17
i <11
Формула включений и исключений для множеств
Пусть {Л, : t £ /} - конечное семейство конечных подмножеств
X. Тогда
и А = Е	Пл-
iel SCl,S/0	sCS
и
=£<-ir' £ Da
Пример. Задача о шляпах.
п джентльменов оставили iijjh входе в клуб свои цилиндры.
Проведя в клубе некоторое время, ни забрали свои шляпы случай-
ным образом. Какова вероятность того, что хотя бы один джентль-
мен вернулся домой в своем цилиндре?
Пересчитаем не1»естановки множества М из п элементов, ос
тавляющис неподвижным хотя бы один элемент. Множество таких
перестановок обозначим через А. Для каждого тп Е М обозначим
через Лт множество всех перестановок, оставляющих на месте
элемент т. Очевидно, А — (J Ат Для каждого подмножества
mfM
ScM перестановки из /Is — A As оставляют на месте множество
S. Очевидно каждая такая пиреегаповка является перестановкой
множества M\S, поэтому |Л$| = (n— S|)L Но формуле включений
,7Данпый метод доказательства известен авторам от А.В.Яковлева.
161
4. Приложения
и исключений, пользуясь тем, что п-злементное множество имеет
6„ i-элсменгных подмножеств, получаем
me М
= E(-1)i+1 £ (п-«)! = Н-1Г1^("-0’ =
«-I	Sc/,JS|-t	«=1

Таким образом, отношение
n! 1!	2!	1	1	(п+1)!
Это частичная сумма ряда для 1 — е *, так что при больших п
вероятность стремится к 1 — е-1 ~ 0,63 ~
4.2 Приложение 2. Доказательство
теоремы Рамсея
Напомним формулировку теоремы 3-5-7.
Теорема 1 (Рамсея). Пусть г,Ь 2 натуральные числа,
п =	Если ребра полного неориентированного графа Кп
покрасить в два цвета (например, в красный и синий), то в Кп
существует либо покрашенный в один из цветов полный подграф
КТ, либо покрашенный в другой цвет полный подграф Кь-
Доказательство. Пусть г. Ь 2 натуральные числа. Обоз-
начим через N = N(r,b) наименьшее натуральное число со сле-
дующим свойством: если ребра полного нсориен ! ированното графа
Kn — (X, U, М) покрасить в два цвета (красный и синий), то в Кдг
существует либо покрашенный в красный цвет полный подграф
КТ, либо покрашенный в синий полный подграф Кь- Докажем, что
число N(r,b) существует. Оченидно, 1V(2. b) - 1> и /V(r. 2) = г для
162
4 Приложения
любых г, b 2. Действительно, либо все ребра графи Кт красные
либо сеть хотя бы одно синее ребро, которое можно рассматривать
как полный граф К^.
Докажем теперь, что
ЛГ(г, Ь) < Лг(г - 1. />) + N(r, b - 1).	(Pi)
Пусть N = Аг(г — 1,6) + Лг(г, b — 1). Предположим, в полном
раскрашенном в два цвета графе Kn найдется такая вертпипа X
что подграф G, порожденный X \ х, не содержит пи красного
подграфа Кг, ни синего Кь (предположение *). Рассмотрим все
ребра, выходящие из вершины я, и покрасим концы красных ре-
бер в красный цвет, а конпы синих - в синий. Множество X \ х
содержит N(r — },b)+N(r,b — 1) —1 элемент, поэтому существует
либо N(r — 1,6)-элементное подмножество красных вершин U с
X \ х, либо N(r,b — 1)-элементное подмножество синих вершин
V С Х\х. Рассмотрим первую возможность. По определению числа
N(r,b- 1) в подграфе, порожденном множеством 17, существует
либо красный подграф KT-i (случай а), либо синий подграф Кь
(случай б). В случае а) добавим к подграфу KT-i вершину х и все
ребра, соединяющие х и U (они красные) Получим красный под-
граф Кт i-рафа Kn- Случай б) невозможен, так как противоречит
(*). Аналогично предположение о существовании подмножества V
приводит к существованию синего подграфа Кь графа KN- Таким
образом, неравенство (Р1) для Аг(г,б) доказано.
Докажем теперь, что
(F2)
Применим двойную индукцию по г и Ь. При г—2 (6 = 2) обе части
неравенства равпы Ъ (г). Для ипдукционохх) перехода применим
(Р1):
A(r,6) < N(r -1,6) + N(r,b-1) с?;62_34	3 =
Пример Аг(3.4) < С| = 10. Можно доказать, что па самом
деле А(3 4) — 9. Таким образом, полный граф Кд, раскрашенный
в два цвета, содержит либо красный треугольник, либо синий "за-
крытый конверт" ^4)-
5. Библиографический список
163
Замечание. Данный }>езультат может быть обобщен в различ-
ных направлениях. Можно раскрашивать ребра латного графа в
tn цветов Тогда получаем следующее утверждение.
Теорема 2 (Рамсея для нескольких цветов). Пусть
mi,. -., nifc 2 - натуральные. числа, тогда существует такое
натуральное Л7 — N(mi,... ,т^), что если ребра полного неори-
ентированного графа Kn покрасить в к цветов, то существует
такое i : 1 i к, что Kn содержит полный подграф Kmi,
покрашенный в i-й цвет.
Дальнейшее обобщение уводит нас от графов. Так, мы можем
рассматривать ребро как двухэлементное подмножество множества
вершин. Естественно перейти к г-элементиым подмножествам.
Теорема 3 (Рамсея для нескольких классов). Пусть все
г-элемеитные. подмножества К элементного множества X раз
биты на к непе.ресекающихся классов М„ 1 i к, тогда
существует такое, натуральное N(m\,... ,ть,г) (m, > г), что
при N N(mIt... ,T7ijt,r) найдется такое i : 1 ii fc, что
существует такое тщ-эле.ментнос множество Ui С X, что все
его г-элементные. подмноже.ства лежат в М,.
Можно обобщить этот результат и на бесконечные множества.
Теорема 4 (Рамсея для бесконечных множеств). Пусть
все. г-элементные подмножества бесконечного множества X раз-
биты на к непересе.кающихея классов А/<, 1 г к, тогда
существует бесконечное множество U С X, такое, что все его
г элементные, подмноже.ства лежат в одном из этих классов.
Именно эту теорему доказал английский математик и философ
Рамсей, исследуя выводы в формальных исчислениях.
5 Библиографический список
5.1 Основной
1. Бобровски Д. Введение в теорию динамических систем с
дискретным временем М. Ижевск: НИЦ "Регулярная и хаоти-
ческая динамика": Ин-т компьютерных исследований, 2006. 360 е.
2 Фихтенгольц Г.М. Курс дифференциального и интегрального
исчисления: В 3 т. СПб. Невский диалект, 2005. 731 с.
Прсдмеч’ный указатель
165
164	5. Библиографический сипс.с>к
3.	Романовский 14 В Дискрет пый анализ Зе изд СПг
Невский диалект, 2004. 320 с.
4.	Биркгоф Г., Барти Т. Сощ>еменная прикладная алгебр», м
Мир, 1976. 400 с.
5.	Хаггарти Р. Дискретная математика для программистов. М
Техносфера. 2005. 400 с.
6	Од и пен В.П., Поспелов М.В. Введение в теорию алгоритмов
Сыктывкар: Изд. Коми пединститута, 2006 140 с.
7.	Оре О Теория графов М : Паука, 1968 352 с.
8.	Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич
Р.И. Лекции по теории графов. М. Наука 1990 383 с.
Предметный указатель
5.2 Дополнительный
1’ Горбатов В.А., Горбатов AJ3., Горбатова М.В. Дискретная
математика: Учебник для студентов втузов М Астрель, 2003
447 с.
2 Кристофидсс М. Теория i-рафов. Алгоритмический подход
М.: Мир, 1978. 432 с.
3’ Мелихов Л.Н. Ориентированные графы и конечные автома-
ты М.: Наука, 1971. 416 с.
4 Одипсц В.11. Зарисовки ш> истории математики Сыктывкар
Изд. Коми пединститута, 2005 232 с.
5’ Колосов В Л Теоремы и задачи алгебры, теории тиссл и
комбинаторики. М.: Гелиос APR, 2001. 256 с.
6' Ловягин Ю-Н. Дискретная математика: Учебное пособие.
Сыктывкар: СЛИ, 2003 243 с.
7 Воробьёв Н Н Числа Фибоначчи М.: Наука 1992. 192 с.
8’ Нежинский В М Конечные графы. СПб : Изд. РГПУ им
А.И. Герцена, 2003- 58 с.
9’ Рейнгольд Э., Нивергельт Ю-, Део Н. Комбинаторные алго-
ритмы Теория и практика. М . Мир, 1980. 476 с.
10’ Белов В В., Воробьев Е М., Шаталов В Е Теория графов.
М.: Высшая школа, 1976
11’ Ловаш Л.. Пламмер М. Прикладные задачи теории графов.
М.: Мир, 1999. 654 с.
12’ Рингель Г. Теорема о раскраске карт. М.: Мир, 1977. 256 С-
ав томорфизм 77
алгоритм 65
-	Краскала 111
-	Тарри 142
алфавит 69
базис циклов 107
бином Ньютона 14
букет петель 121
ветка 60
вершина 60
периферийная 102
центральная 102
вершины связанные 92
вес
ветки 111
подграфа 111
вход 65
выборка 9
-	неупорядоченная 9
упорядоченная 9
выход 65
топотеза 4 красок 125
грапь 115
граф» 60
-	Ьсржа 62
бесконечный 72
бихроматический 121
-	вершинный (пустой) 60
-	гамильтонов 143
двудольный 119
конечный 72
-	неориентированный 63
-	ориентированный 63
планарный 114
плоский 114
-	полный (насыщенный) 66
прогрессивно конечный 136
простой 67
-	связный 92
-	Л-связный 98
-	смешанный 63
собственно неориентиро-
ванный 63
--ориентированный 63
-	эйлеров 140
р-го рода 123
р-хроматичсский 121
дерево 93
- корневое 95
остовпос 111
диаметр 102
диграф 63
ассоциированный с G 89
сильно связный 92
длина цепи 91
дополнение подграфа 80
дуга 61
задача
-	о семи Кепигсбвртоких мос-
тах 141
о кроликах Фибоначчи 32
- о шляпах 160
-	о 3 домах и 3 колодцах 120
о 5 столицах 119
Гамильтона "путешествие
по додекаэдру" 143
изоморфизм
- гра<)юв 77
- диграфов 77
игра
на графе 138
Ним 139
инцидентность 60
карта 124
166
комбинаторика 7
композиции диграфов 85
компонента связности 92
контур 105
конфигурация комбинатор-
ная 8
корень 95
козффи циент би номиальн ый
(бинома Ньютона) 13
лес 94
линия
-	реберная 113
лист 93
матрица
-	инцидентности 76
Казорати 37
общей смежное ги 75
-	смежности 75
метод
-	неопределенных коэффи-
циентов 39
Ньютона 59
многогранник
выпуклый 118
-	звездный 118
многочлен
-	характеристический 27
Чебышёна 55
моет 110
мультиграф 68
мультифункция (словарная
функция) 69
неорграф 63
объединение матриц 87
определитель
-	Казорати 37
орграф 63
паросочетание 145
Предметный указатель
- максимальное 145
совершенное 145
пересечение
матриц 87
подграфов 80
перестановка 10
с повторениями 10
петля 62
подграф 65
генерированный подмно-
жеством 71
скелетный (остовпый) 71
подмножество
ннешне устойчивое 131
внутренне устойчивое 129
полугруппа 84
паз укольцо
-	идемпотентное 84
-	коммутативное. 84
полустепепь
-	захода 73
-	исхода 73
not ледовательпости
линейно зависимые 37
-	независимые 37
-	одното порядка 42
-	эквивалентные 40
последовательность
бесконечно малая 40
более высокого поряд-
ка 40
максимального периода 27
ограниченная 41
-	разностей 53
-	рекуррентная 22
- линейная с постоянными
коэффициентами (ЛРП) 22
— однородная 22
1Трсдметный указатель
- неоднородная 22
Фибоначчи 33
постоянная
-	золотого сечения 49
правило
-	произведения 8
-	суммы 7
прогрессия
- ярифметико-шометриче-
ская 23
арифметическая 23
геометрическая 23
проекция стереографичес-
кая 117
произведение
диграфов 84
матриц правое прямое 87
пространство
- метрическое 101
псевдограф 68
путь 92
радиус 102
размещение 9
с повторениями 9
разность подграфов 82
раскраска правильная
- вершин 121
- карты 124
расстояние 101
ртализация
геометрическая 113
правильная 114
ребро 62
регион 115
- внешний 115
-внутренний 115
редукция графа 120
решение
167
рекуррентного уравне-
ния 22
— общее 31
--------асимптотически стаци-
онарное 48
стацирнарнос 48
-	тривиальное 22
ряд
-	асимптотический 46
-	Лейбница 55
свойство
Пуанкаре 49
слово 69
соединение графов 88
соотношение
рткуррентное 22
сочетание 11
-	с повторениями 11
степень вершины 73
сумма
-	специальная 84
степенная 16
топологическая 79
суперпозиция диграфов 85
тсортма
-	о 5 красках 126
-	о свадьбах 146
Понтрягипа-Куратовско-
го 120
-	Пуанкаре 49
-	Рамсея 127
-	Чебышева 43
Эйлера о сумме степеней 74
точка
простого сочленения 100
-	сочленения 99
-	узловая 113
точки
168
линейно связанные 115
треупмьпик Паскаля 13
удаленность вершины 102
узел
-	ветвления 65
-	вычислительный 65
уравнение
-	рекуррентное 22
-	харак герпетическое 32
условия начальные 22
формула
-	Бине 34
-	включений и исключений 7
Стирлинга 47
Эйлера 53
-	- для графов 116
- суммирования рядов 53
функция
автокорреляционная 27
весовая 111
Гранди 135
-	дробная часть 30
-	производящая 18
характеристическая мно-
жества 158
-	целая часть 28
---- верхняя 29
— нижняя 28
цепь 91
замкнутая 105
простая 91
-	элементарная 91
цикл 105
-	гамильтонов 143
-	простой 105
-	тривиальный 106
-	чйлеров 110
элементарный 105
Предметный указатель
циклы
—	независимые 107
число
-	внешней у<той швостм 13]
внутренней устойчивое
ти 129
связности 98
-	цикломатичсское 104
хроматическое 121
поверхности 125
ядро 133
Именном указатель
169
Именной указатель
.Александров II.С. (Павел Сергеевич) (1876, Богородск (ныне
Ногинск) Московской губ., Российская империя - 1982. Москва.
СССР) 120
Абель Н.Х (Abd Nils Henric) (1802, Ставангера, Датское коро-
левство (ныне Норвегия) - 1829. Арендаль, Шведско-Норвежская
уния (пыне Норвегия)) 55
Аппель К (Appel Kcnnet I.) (1932, Нью-Йорк, США) 127
Барти Т. (Bartee Т С.) 164
Белов В В. (Владимир Владимирович) 164
Берж К. (Berge Claude Jacques) (1926, Париж. Франция) 62
Бине Ж Ф. (Binet Jacques Philippe Marie) (1786, Рен 1856
Париж, Франция) 34
Биркгоф Г. (Birkhoff Garrett) (1911, Принстон, США) 164
Бобровски Д. (Bobrwski Domieslaw) (1927, Збошппн, Польша)
163
Вандермонд A (Wanderrnondc Alexandre.) (1735, Париж 1796.
Париж, Франция) 37
Воробьёв F.M (Евгений Михайлович) 164
Воробьев Н.Н (Николай Николаевич) (1925 Ленинград, СССР
1995, Санкт-Петербург, Россия) 164
Гамильтон У.Р. (Hamilton William Rowan) (1805, Дублин - 1865,
Дублин, Великобритания (ныне Ирландия)) 143
Го|»батов А.В. (Александр Вячеславич) 164
Горбатов В А. (Вячеслав Афанасьевич) 164
Горбатова М.В (Марина Вячеславпа) 164
Гранди П. (Grandy Р М.) 135
Грёчсл М (Grotschel Martin) (1948, Швельм, Германия) 126
Гутри Фрчнрис (Gutrie Francis) 126
Гутри Фредерик (Gutrie Frederick) 126
Део Н (Deo Narsingh) 164
Дирак Г (Dirak Gabriel Andrew) 144
Емеличсв В.А. (Владимир /Алексеевич) (1930, Макаров Кост-
ромской оба., СССР) 164
Жордан К. (Jordan Marie Camille) (1838, .Пион - 1922. Париж.
Франция) 103
170
Именной указате;/ь
Казорати Ф. (Gasorati Felice.) (1835, Павия - 1890, Касте окно
Италия) 37
ал-Кщпи Гнйяс-ад-Дин Джамшид (?, Катан 1436, Самар-
кандское государство Тимуридов (ныне Узбекистан)) 15
Кёниг Д. (Konig D^nes) (1884, Будапешт, Авелю-Венгрия (нын
Венгрия) - 1944, Будапешт. Венгрия) 60
Кожима Т. (Kojima Tetsuro) (1886-1921, Япония) 55
Колокольное В.Н. (Василий Никитич) 90
Колосов В А. (Вадим Александрович) (1965, СССР) 164
Краскал Дж.Б (Kruskal Joseph Bernard) (1928, Нью-Йорк
2006, Принстон, США) 111
Кристофидес II. (Christofides Nicos) 164
Куратовекий К (Kuratowski Kazimierz) (1896, Варшава, (Поль-
ша) Российская империя - 1980, Варшава, Польша) 120
Кэли A. (Cayley Arthur) (1821, Ричмонд - 1895 Кембридж, Ве-
ликобритания) 126
Лейбниц Г В. (Leibniz Gottfried Wilhelm) (1646, Лейпни! 1716,
Ганновер, Германия 15, 55
Ловаш Л. (Loviksz Laszld) (1947, Венгрия) 164
Ловягин Ю Н. (Юрий Никитич) (1958, и. Уеть-Нсра, Якутская
АССР, СССР) 164
Лопиталь Г. (L’Hospital Guillaume Francois (1661, Париж 1704.
Париж, Франция) 44
Маслов В.П. (Виктор Павлович) (1930, Москва, СССР) 90
Мелихов А.Н (Аскольд Николаевич) (1939, СССР) 164
Мельников О.И. (Олег Исидорович) 164
Мёбиус A. (Mobius August F.) (1790, Шульцфорт - 1868. Лейп-
циг, Германия) 126
де MopiaH A (de Morgan Augustus) (1806, Мадура, Индия -
1871, Лондон, Британская империя) 125
де Муавр A. (de Moivrc Abraham) (1667, Витри-ле-Фрянсуа,
Франция - 1754 Лопдон, Великобритания) 47
Нежинский В М. (Владимир Михайлович) (1951, Одесса,
СССР) 6, 164
Нивергельт Ю. (Nievcrgclt Jurg) 164
Ньютон И. (Newton Isaac) (1643 Вулсторп 1727, Кснснигтои.
Англия, Великобритания) 14, 59
[Ыспной указатель
171
Одипец В.П (Владимир Петрович) (Odyniec W ) (1945, Ленин-
град, СССР) 2, 61, 164, 164
Оре О. (Ore Oystcin) (1899. Христиания (ныне Осло), Шнедско-
Норвсжская уния 1968, Осло, Норвегия) 143. 164
Паскаль Б. (Pascal Blaise) (1623, Клермон-Ферран 1662,
Париж, Франция) 13
Пламмер М. (Plummer Michael D.) 164
Перрон О (Perron Oskar) (1880, Франкенталь - 1975, Мюнхен,
Германия) 50
Понтрягин Л.С. (Лев Семенович) (1908, Москва, Российская
империя 1988, Москва, СССР) 120
Поспелов М.В (Михаил Владимирович) (1973 Ленинград,
СССР) 164
Пуанкаре Ж A (Poincare Jules Henry) (1854. Нанси - 1912,
Париж, Франция) 49
Пуассон С.Д. (Poisson Simeon Denis) (1781, Питив|>е - 1840,
Париж, Франция) 55
Рамсей Ф.П (Ramsey Frank Plumpton) (1903, Кембридж 1930,
Лондон, Великобритания) 127
Рейнгольд 9 (Reingold Edward М ) 164
Рингель Г (Ringel Gerhard) (1919, Коллнбрунн, Австрия) 125,
164
Рисе Е.А (Елена Артуровна) (1961, Волжский Волгоградской
обл., СССР) 156
Романовский И.В (Иосиф Владимирович) (1935, Ленинград.
СССР) 164
Сарванов В И. (Владимир Иванович) 164
Смейл С. (Smale Stephen) (1930, Флинт. США) 65
Стирлинг Дж. (Stirling James) (1692. Гарден - 1770, Эдинбург,
Шотландия, Великобритания) 47
Тарри Г. (Татту Gaston) (1843, Виллсфранш 1913, Франция)
142
Татт У. (Tnlte William Thomas) (1917, Ньюпорт. Велнкобрита-
ния 2002, Ватерлоо, Канада) 145
Таубер A. (Tauber Allred) (1866, llpecbypi Австро Венгрия (цы-
пе Братислава, Словакия) - 1942, Терезиеннггадт, Германия (ныне
Терезин, Чехия)) 55
172
Именпой указатель
Теплиц О. (Toplitz Otto) (1881, Бреслау, Германия (ныне Вроц-
лав, Польша) 1940, ?) 55
Тышкевич Р.И (Регина Иосифовна) (1929, Минск, СССР) 164
Фибоначчи Л. (Леонардо Пизанский) (Fibonacci Leonardo
(Pisano)) (1180, Пиза - 1240. Пиза, Италия) 32
Фихтенгольц I М (Григорий Михайлович) (1888 Одесса, Рос-
сийская империя (пыпе Украина) 1959, Лениш-рад, СССР) 163
Флегонтов А В (Александр Владимирович) (1953, Ленинград,
СССР) 6
Фокип РР (Роман Романович) (1957, Ленинград, СССР) 6
Фробениус Ф.1 (Frobenius Ferdinand Georg) (1849, Берлин -
1917, Шварцлоттенбург, Германская империя) 146
Хаггарти Р. (Haggarty Rod) 164
ал-Хайям У.мар (1048. Нишапур - 1131, Нишапур, Хорасан
(ныне Иран)) 15
Хакен В. (Haken Wolfgang) (1928, Берлин, Гсрмапия) 127
Хватал В. (Chvdtal Vladimir) 145
Хивуд П (Heawood Percy John) (1861, Ньюпорт - 1955. Вели
кобритаяия) 126
Холл Ф. (Hall Philip) (1904 Лондон - 1982, Лондон, Велико-
британия) 146
Чебышев П.Л. (Пафнутий Львович) (1821, с Окатово Калуж-
ской губ. - 1894, Санкт-Петербург, Российская империя) 55
Чвзаро 9 (Ccsaro Ernesto) (1859, Неаполь - 1906, Торре-
Анунциато, Италия) 55
Шагалов В.Е. (Виктор Евгеньевич) 164
Швспкий М.В. (Михаил Владимирович) (1954, Одесса.
СССР) 6
ТНлензак В (Skjnzak VVlodzimierz) (1952, Быдгощ, Польша) 61
Шеннон К. (Shannon Claude Elwood) (1916, Гейлорд, - 2001-
Бштон. США) 131
Эйлер Л. (Euler Leonard) (1707, Базель, Швейцария - 1783,
Санкт-Петербург. Ршхийекая империя) 47, 53, 116
Яковлев АВ (Анатолий Владимирович) (1940, Ленинград,
СССР) 160
Якубсоп М.Я (Михаил Яковлевич) (1959, Ленинград, СССР) 2
Янге Дж.УТ. (Yoims John W.T) (?	1970, Санта-Круз,
США) 125
Указатель обозначений
173
Указатель обозначений
1Л' ।
и
л
\
с
0
Gi =G2
А^В
(irn) - о(уп)	—
(З'П — О(уп)
(х„) X (уп
(хп) = О*(уп)	—
N	-
No
Z	-
IR
IR2
R”
Ы
{х,.}
число элементов п множестве X
объединение множеств
пересечение множеств
разность множеств
подм ножест во
пустое множество
символ отображения
оператор суммирования
оператор произведения
декартово произведение
отношение эквивалентности
изоморфизм графов Gi и G2, 79
изоморфизм квадратных матриц
одного порядка, 90
(тп) бесконечно малая более высокого
порядка, чем (уп)
(хп) ограничена относительно (уп)
(тп) и (уп) одного порядка
(хп) и (уп) одного порядка
множество натуральных чисел
множество натуральных чисел с нулем
множество целых чисел
множество вещественных чисел
евклидова плоскость (двумерное
евклидово пространство)
n-мернос евклидово пространство, п 2
число размещений, 9
число размещений с повторениями, 9
число сочетаний, 11
число сочетаний с повторениями, 12
число перестановок, 10
число перестановок с повторениями, И
целая часть числа х
верхняя целая часть числа х. 30
нижняя целая часть числа аг. 29
множество чисел xj,..., жп,...
174
Указатель обозначений
Un)
(fn)
7г(п)
(Apafc)
G = (X,t/,M)
й
и
й
pU)
p+U)
р U)
Яс
G] U G2
G । П (?2
Gi - G2
G
Gi х G2
Gi i-G2
G| ® G2
Gi * (j-2
C i м G2
G*
Лов
д
p(z-. у)
<*U)
rG
Яс
^(G)
A(G)
p(«)
G
Kn
последовательность чисел Хц. , хп,..
последовагельносгь чисел Фибоначчи. 34
количество простых чисел, не превосходящих
п, 44
последовательность разностей, 54
граф, X - множество вершин, V множество
веток, а М - подмножество в X х U х X, 61
множество дуг, 63
множество петель, 63
множество ребер, 63
степень вершины, 75
1юлустепснь исхода, 75
полустепень захода, 75
матрица смежности графа G, 76
матрица общей смежности графа G, 76
топологическая сумма графюв, 80
пересечение графов, 82
разность графов, 83
дополнение графа, 82
произведение графов, 86
специальная сумма графов, 86
композиция графов, 86
суперпозиция графов 86
соединение графов, 90
ассоциированный диграф, 91
правое прямое произведение матриц, 89
цепь, 93
расстояние между вершинами х и у, 104
удаленность вершины х, 104
радиус графа G, 104
диаметр графа G, 104
цикломагическое число граф>а G, 116
пространство циклов графа G 109
весовая функция G, 114
геометрическая реализация |рафа G,l!6
полный граф с п вершинами без нетель, 67
полный двудольный граф с т и п вершинами
в долях, 91
Указатель обозначения	175
7(G) 5;J 7(5р) «(G) tf(G) И' ХЛ tc{x)	хроматическое число графа G, 124 — сф>ера с р ручками, 126 — хроматическое число поверхности SJt 128 число внутренней устойчивости графа G, 133 — число внешней устойчивости графа G, 135 паросочетапис характеристическая функция мпожесгва Л — мультифункиия, соответствующая
{Х,р}	графу G, 71 — диграф, задаваемый с помощью мультифункции F, 72
Владимир Петрович Олинец
Михаил Яковлевич Якубсон
ЭЛЕМЕНТЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Учебное пособие
Главный редактор В. А.Попов
Редактор ЕМ.Насирова
Компьютерный макет В А. Попов
Компьютерный набор М.Я.Якубсон
Подписано в печать 30.12.2006 г.
Формаз 60x84/16 Тираж 200 экз. (1-й завод).
Печать ризография. Усл печ.л. 10.2. Уч.-изд.л 9,8.
Редакционно-издательский отдел
Коми государственного педагогического ипстигута
167982. Сыктывкар, ул. Коммунистическая, 25
Заказ 415/2007 от 14.05.07 г.
Отпечатано с готовых оригинал-макетов
в ООО «Типография «ПОЛИГРАФ-СЕРВИС»
г Сыктывкар ул. -Пенина 4, тел 21-48-36.

Одннец Владимир Петрович доктор
физико-математических иаук лауреат
Государственной премии Польши, профессор
кафедры прикладной математики РГПУ
им. А.И. Герцена (Санкт-Петербург) и кафедры
алгебры и геометрии Коми государственного
педагогического института (Сыктывкар)

Якубсои Михаил Яковлевич - кандидат физико-
математических иаук доцент кафедры
математического анализа КГПУ им А.И Герцена
заведующий кафедрой математических и
естественнонаучных дисциплин филиала РГПУ
им. А. И. Герцена в г. Волхове.