• Название:

    Дискретная математика (продолж.)

  • Размер: 2.14 Мб
  • Формат: PDF
  • или
  • Название: 1 Начальные понятия теории множеств и математической логики
  • Автор: Владимир

ФИНАНСОВАЯ АКАДЕМИЯ
ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ
Кафедра «Математика и финансовые приложения»

В.Б. Гисин

Лекции по дискретной математике

(часть 2)

МОСКВА 2002 ГОД

2

Аннотация
Пособие предназначено студентам, изучающим дискретную
математику,

и

преподавателям,

проводящим

занятия

по

указанной дисциплине. Дисциплина «Дискретная математика»
является обязательной для студентов дневного отделения
института «Антикризисное управление и математические
методы в экономике». Настоящее пособие содержит вторую
часть курса лекций по дискретной математике. В этой части
излагаются комбинаторика (включая производящие функции,
рекуррентные последовательности и числа Фибоначчи) и
теория графов. Значительное место уделено финансовым
приложениям изучаемого материала.

3

Оглавление
8. Элементы комбинаторики .

.

.

6

8.1. Предварительные сведения

.

.

6

8.2. Размещения и перестановки

.

.

10

8.3. Сочетания .

.

.

15

.

.

20

.

24

.

.

.

.

8.4. Некоторые свойства чисел Cnk

8.5. Принцип включения и исключения
9. Биномиальная модель
ценообразования активов .

.

.

.

28

9.1. Биномиальная решетка

.

.

.

28

9.2. Опционы. Основные понятия

.

.

29

9.3. Однопериодная модель

.

.

31

9.4. Двух- и трехпериодные модели .

.

36

9.5. Многопериодная модель

.

41

.
.

.

4
10. Биномиальный ряд. Производящие
функции .

.

.

.

.

.

.

47

10.1. Степенные ряды

.

.

.

.

47

10.2. Биномиальный ряд .

.

.

.

50

10.3. Производящие функции и примеры их
применения при решении комбинаторных
задач

.

.

.

.

.

54

11. Рекуррентные последовательности .

.

61

11.1. Рекуррентные соотношения

.

.

61

.

.

63

рекуррентных последовательностей .

67

11.2. Линейные рекуррентные
соотношения

.

.

.

11.3. Производящие функции линейных
11.4. Числа Каталана. Случайное
блуждание

.

.

.

.

.

74

.

.

.

.

.

82

12.1. Простейшие свойства

.

.

.

82

.

.

84

.

.

88

12. Числа Фибоначчи

12.2. Формула Бине и некоторые
ее применения
12.3. Золотое сечение

.
.

.

12.4. Числа Фибоначчи и поиск экстремума

92

5
13. Графы. Основные понятия

.

.

104

.

.

104

13.2. Маршруты, цепи и циклы .

.

.

108

13.3. Эйлеровы цепи и циклы .

.

.

111

.

.

113

13.1. Понятие графа .

.

.

13.4. Матрицы смежности
и инцидентности

.

.

13.5. Булевы матрицы и операции над ними

119

13.6. Бинарные отношения и графы .

.

120

14. Деревья

.

.

.

.

.

.

.

126

.

.

.

126

14.2. Остовное дерево связного графа

.

129

14.1. Общее понятие дерева

14.3. Ориентированные и упорядоченные
деревья

.

.

.

.

.

.

133

.

.

.

.

137

внешняя устойчивость в графах

.

.

142

15.1. Порядковая функция графа

.

.

142

15.2. Внешняя устойчивость

.

.

.

145

15.3. Внутренняя устойчивость .

.

.

149

15.4. Ядро графа

.

.

152

14.4. Бинарные деревья

15. Доминирование. Внутренняя и

.

.

.

6

8. Элементы комбинаторики
8. 1. Предварительные сведения
Целью комбинаторики является изучение комбинаторных
конфигураций – конструкций, построенных из элементов
некоторого (как правило, конечного) множества в соответствии
с заданными правилами. Важный класс комбинаторных задач
составляют задачи перечисления и, в частности, определения
числа конфигураций данного типа. Простейшими примерами
комбинаторных

конфигураций

являются

перестановки,

размещения и сочетания, представляющие собой различного
рода выборки.
Конечное

множество,

содержащее

n

элементов,

в

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

правилах,

называемых

соответственно

правилами суммы и произведения.
Правило суммы. Если X1 и X2 – непересекающиеся конечные
множества, содержащие соответственно n1 и n2 элементов, то

7
объединение X1∪X2 содержит n1 + n2 элементов.
Сформулированное правило можно распространить на
случай произвольного числа слагаемых:
если

множества

множества X,
элементов

то

X1, X2, …,Xk

n = n1 + n2 +…+ nk,

множества

X,

а

образуют
где

ni = |Xi| –

разбиение

n = |X| –
число

число

элементов

множества Xi, i = 1, 2,…, k.
Правило суммы можно приспособить и для подсчета числа
элементов

объединения

двух

множеств

с

непустым

пересечением:
|X1∪X2| = |X1| + |X2| – |X1∩X2|.

(1)

В самом деле, множества X1\X2 и X1∩X2 образуют разбиение
множества X1, поэтому
|X1| = |X1\X2| + |X1∩X2|.
Аналогично
|X2| = |X2\X1| + |X1∩X2|.
Кроме того, множества X1\X2, X2\X1 и X1∩X2 образуют разбиение
множества X1∪X2, так что
|X1∪X2| = |X1\X2| + |X2\X1| + |X1∩X2|.
Соотношение (1) является следствием трех последних формул.
Формула (1) обобщается на произвольное число слагаемых с
помощью так называемого принципа включения и исключения
(см. п. 8.4).
Пример. Найдем число правильных несократимых дробей
со знаменателем 100. Числителем правильной несократимой

8
дроби со знаменателем 100 должно быть целое число в
промежутке от 1 до 100, не имеющее среди своих делителей
чисел 2 и 5. Обозначим через X2, X5 и X10 множества чисел из
промежутка от 1 до 100, делящихся соответственно на 2, на 5 и
на 10. Легко видеть, что |X2| = 100/2 = 50 и |X5| = 100/5 = 20 и
|X10| = 100/10 = 10. Так как X2 ∩X5 = X10, то по формуле (1)
получаем |X2 ∪ X5| = 50 + 20 – 10 = 60. Таким образом, среди
чисел от 1 до 100 имеется 60 чисел, делящихся на 2 или 5, и
100 – 60 = 40

чисел,

взаимно

простых

с

числом

100.

Следовательно, среди правильных дробей со знаменателем 100
ровно 40 являются несократимыми.
Правило

произведения.

Будем

рассматривать

упорядоченные наборы (кортежи) вида (a1, a2,…, ak) заданной
длины k. Предположим, что элемент a1 может быть выбран n1
способами; при фиксированном a1 элемент a2 может быть
выбран n2 способами; при фиксированных a1 и a2 элемент a3
может быть выбран n3 способами и т. д. (при фиксированных
a1, a2,…, ak–1 элемент ak может быть выбран nk способами).
Тогда

число

различных

кортежей

равно

произведению

n1n2⋅…⋅nk. В частности, по правилу произведения для конечных
множеств X1, X2, …, Xk имеем:
|X1×X2×…×Xk| = |X1|×|X2|×…×|Xk|.
Пример. Используя правило произведения и правило
суммы, найдем число различных трехзначных чисел, не

9
содержащих одинаковых цифр, и число различных трехзначных
чисел, содержащих хотя бы две одинаковые цифры.
Пусть a1, a2, a3 – цифры трехзначного числа. Первую цифру
a1 можно выбрать девятью способами (в качестве нее можно
взять любую цифру, кроме нуля); при фиксированной первой
цифре вторую цифру a2 можно выбрать также девятью
способами (в качестве нее можно взять любую цифру, кроме
a1); наконец, при фиксированных первой и второй цифрах
третью цифру можно выбрать восемью способами. По правилу
произведения число трехзначных чисел, не содержащих
одинаковых цифр, равно 9⋅9⋅8 = 648. Всего имеется 900
различных трехзначных чисел. Каждое из них либо содержит
две одинаковых цифры, либо нет. Следовательно, имеется 900 –
648 = 252 различных трехзначных числа, содержащих хотя бы
две одинаковые цифры.
Факториалы.
положительного

Напомним,
числа

n

что

факториалом

(обозначение

n!)

целого

называется

произведение 1⋅2⋅...⋅n. По определению считается, что 0! = 1.
Факториал как функция натурального аргумента может быть
однозначно определен рекурсивно:
0! = 1; (n + 1)! = n!⋅(n + 1).
Приближенное значение n! при больших n дает следующая
формула Стирлинга:

10
n! ∼

n

n
2 рn   .
e

(2)

Символ ∼ означает здесь, что отношение
n

n
2 рn   /n!
e
стремится к единице при n, стремящемся к бесконечности. Хотя
разность правой и левой частей в формуле Стирлинга
неограниченно возрастает, относительная ошибка быстро
убывает. Например, уже при n = 10 относительная ошибка
составляет менее одного процента:
10

10! = 3628800;

 10 
2 р ⋅ 10 ⋅  
e

≈ 3598696.

8. 2. Размещения и перестановки

Размещения с повторениями объема k из n-множества X, или
размещения с повторениями из n элементов по k, – это
упорядоченные выборки вида (a1, a2,…, ak), где ai, i = 1, 2,…, k,
– произвольные элементы множества X.
Каждый элемент ai может быть выбран n способами. По
правилу

произведения

общее

число

размещений

с

повторениями из n элементов по k равно nk.
Размещения (без повторений) объема k из n-множества X,
или размещения из n элементов по k, – это упорядоченные
выборки вида (a1, a2,…, ak), где ai, i = 1, 2,…, k, – различные
элементы множества X.

11
Элемент a1 может быть выбран n способами. При n ≥ 2
элемент a2 может быть выбран n – 1 способами: в качестве a2
можно взять любой элемент из (n – 1)-множества X\{a1}. По
правилу произведения число упорядоченных пар различных
элементов вида (a1, a2) равно n(n – 1). Аналогично (при n ≥ 3)
элемент a3 может быть произвольно выбран из (n – 2)множества X\{a1, a2}, так что число упорядоченных троек
(a1, a2, a3) равно n(n – 1)(n – 2).
Число размещений из n по k, n ≥ k, обозначается через Ank .
Как мы видели, An1 = n . Естественно считать, что
An0 = 1

(3)

(имеется ровно одна, не содержащая ни одного элемента, т. е.
пустая выборка).
Несложно показать, что при k < n имеет место соотношение
Ank +1 = (n − k ) Ank .

В

самом

деле,

упорядоченную

(4)
выборку

вида

(a1, a2,…, ak, ak+1) можно рассматривать как упорядоченную
пару, в которой первым элементом служит размещение
(a1, a2,…, ak), а вторым – ak+1. Размещение из n элементов по k
может быть составлено Ank способами, элемент ak+1 может быть
произвольно выбран из (n – k)-множества X\{ a1, a2,…, ak}.
Формула (3) получается теперь по правилу произведения.

12
Используя формулы (3) и (4), получаем:
An1 = n , An2 = n(n − 1) , An3 = n(n − 1)(n − 2) , … ,

и, в общем случае:
Ank = n(n − 1) ⋅ K ⋅ (n − k + 1) .

(5)

Предыдущую формулу можно записать следующим образом:
Ank =
Пример.

Найдем

число

n!
.
(n − k )!

всех

(6)

отображений

и

число

инъективных отображений из k-множества X в n-множество Y.
Перенумеруем элементы множества X, X = {a1, a2,…, ak}.
Всякое отображение f из X в Y однозначно определяется
упорядоченным
(b1, b2, …, bk),

набором
в

элементов

котором

bi = f(ai).

множества
Значит,

Y

вида

число

всех

отображений из X в Y равно числу размещений с повторениями
из n элементов по k, то есть числу nk. Таким образом, получаем
формулу:
|YX|= nk,
где через YX обозначено множество всех отображений из X в Y.
Если k > n, инъективных отображений из X в Y нет. При k ≤ n
отображение f из X в Y инъективно, если в наборе (b1, b2, …, bk)
все элементы различны, т. е. набор (b1, b2, …, bk) является
размещением
инъективных

без

повторений.

отображений

размещений Ank .

из

Следовательно,
X

в

Y

равно

число
числу

13
Размещения
n-множества

объема
X

n,

составленные

называются

из

элементов

перестановками

элементов

множества X.
Задать перестановку элементов множества X – это значит
линейно упорядочить элементы этого множества. Число всех
перестановок из n элементов обозначается через Pn. Используя
формулу (5) при k = n, получаем:
Pn = n!.
Пример.

Перечислим

(7)
перестановки

элементов

множества X = {1, 2, 3}:
123;

132; 213; 231; 312; 321.

В заключение рассмотрим перестановки с повторениями.
Пусть X = {a1, a2,…, ak} – некоторое k-множество. Перестановкой с повторениями типа (n1, n2,…, nk) называется упорядоченный набор элементов множества X вида (x1, x2,…, xn), в котором
элемент a1 встречается n1 раз, элемент a2 встречается n2 раз, …,
элемент ak встречается nk раз. Естественно, n1 + n2 +…+ nk = n.
Число

перестановок

типа

(n1, n2,…, nk)

обозначается

через P(n1, n2,…, nk).
Пример. Перечислим все перестановки типа (2, 2) из

элементов множества X = {a, b}:
aabb;

abab;

abba;

baab;

baba;

bbaa.

14
Чтобы получить формулу для вычисления P(n1, n2,…, nk),
воспользуемся следующей метафорой. Элементы множества X
будем считать буквами, а перестановки с повторениями –
словами. Для определенности будем считать, что X содержит
три буквы a, b, c. Рассмотрим произвольное слово w длины n,
содержащее n1 букв a, n2 букв b и n3 букв c. Подсчитаем число
перестановок букв, при которых слово w не меняется. Буквы a
можно произвольно переставлять на n1 местах, на которых они
расположены. Это можно сделать n1! числом способов. Точно
так же буквы b можно переставить n2! способами, буквы c –
n3! способами. По правилу произведения число перестановок
букв, при которых слово w не меняется, равно n1!n2!n3!. Таким
образом, для каждого слова имеется n1!n2!n3! перестановок
букв, которые его не меняют. Общее число перестановок букв
равно n!. Следовательно, число слов, т. е. перестановок типа
(n1, n2, n3), равно

n!
.
n1!n2!n3!
Предыдущее рассуждение легко переносится на общий
случай и приводит к следующей формуле:
P(n1, n2 ,K , nk ) =

n!
.
n1!n2!K nk !

(8)

Пример. Пакет акций состоит из акций четырех типов: 5

акций типа A, 3 акции типа B и по одной акции типов C и D.

15
Сколькими способами можно распродать этот пакет, продавая
по одной акции ежедневно?
Каждая

распродажа

однозначно

определяется

словом

длины 10, составленном из пяти букв A, трех букв B, одной
буквы C и одной буквы D (буква, стоящая на месте i, означает,
что в день i была продана акция соответствующего типа).
Значит, число всевозможных распродаж составляет
P(5,3,1,1) =

10!
= 5040 .
5! ⋅ 3!⋅1!⋅1!

8. 3. Сочетания

Сочетания

объема

неупорядоченные

k

выборки

из

n-множества
вида

X



{a1, a2,…, ak},

это
где

ai, i = 1, 2,…, k, – попарно различные элементы множества X.
В соответствии с определением сочетания объема k – это
k-подмножества множества X. Число сочетаний объема k из
n
n-множества X обозначают через Cnk или через   и называют
k 
числом сочетаний из n по k.

Легко видеть, что Cn0 = 1 , Cn1 = n , Cnn = 1. Чтобы получить
формулу для числа сочетаний в общем случае, докажем
сначала, что при k ≤ n справедливо следующее соотношение:
Ank = Cnk ⋅ Pk .

В самом деле, пусть X – n-множество. Каждому размещению
(a1, a2,…, ak)

16
поставим в соответствие сочетание
{a1, a2,…, ak}.
Одно и то же сочетание {a1, a2,…, ak} соответствует всем
размещениям,

полученным

перестановкой

элементов

a1, a2,…, ak. Число таких перестановок равно Pn. Таким образом,

вся совокупность размещений по k элементов разбивается
на Cnk классов, каждый из которых содержит Pn размещений.
Отсюда и следует доказываемая формула.
Используя (6), (7) получаем выражение для числа сочетаний
«в факториалах»:
Cnk =

n!
.
k!(n − k )!

(9)

Часто используется и следующее соотношение:
Cnk =

n(n − 1) ⋅ K ⋅ (n − k + 1)
.
k!

(10)

Пример. Найдем число сочетаний из 52 по 26.

В соответствии с (9) имеем:
26
C52
=

Используя

формулу

52!
(26 !) 2

.

Стирлинга

можно

приблизительную оценку:
26
ln C52
≈ 0,5(ln 2π + ln 52) +52(ln 52 –1) –

– (ln 2π + ln 26) – 52(ln 26 –1)
= 53ln 2 – 0,5ln(52⋅2π) ≈ 33,84.

получить

17
Значит,
26
C52
≈ e33,84 ≈ 4,98⋅1014
26
≈ 4,96⋅1014).
(прямое вычисление дает C52

Пример.

Найдем

число

монотонно

возрастающих

отображений из множества
X = {1 ,2 ,…, k}
в множество
Y = {1 ,2 ,…, n}.
Любое такое отображение f задает набор чисел
f(1) < f(2) < … <f(k).
Обратно,

любое

Y′ = {y1, y2,…, yk}

k-подмножество

множества Y однозначно определяет монотонно возрастающее
отображение из X в Y, для которого f(X) = Y′ . В самом деле,
упорядочим элементы множества Y′ по возрастанию так, что
Y′ = {y1, y2,…, yk},

причем

y1 < y2 <…< yk.

Полагая

f(i) = yi,

получаем соответствующее отображение. Таким образом, число
монотонно возрастающих отображений из X в Y равно числу
k-подмножеств множества Y, т. е. числу Cnk – числу сочетаний
из n по k.
Рассмотрим

теперь

вопрос

о

числе

сочетаний

с

повторениями. Сочетания с повторениями объема k из
n-множества X – это неупорядоченные выборки вида a1 a2… ak,
где ai, i = 1, 2,…, k, – произвольные элементы множества X,

18
среди которых могут быть и совпадающие. Примерами
сочетаний с повторениями из элементов a, b, c, d по три могут
служить выборки aaa; aab; dab.
Предположим для определенности, что X = {1, 2,…, n}.
Сочетание
однозначно

с

повторениями

из

определяется

элементов

множества

упорядоченным

X

набором

неотрицательных целых чисел (x1, x2,…, xn), где xi, i = 1, 2,…, n,
равно числу вхождений в выборку элемента i. Например,
выборка 1, 3, 2, 1, 3, 3 из множества X = {1, 2, 3, 4} задается
набором (2, 1, 3, 0), поскольку 1 встречается в ней два раза, 2 –
один раз, 3 – три раза, и 4 – ни разу. Сумма x1 + x2 +…+ xn – это
объем

выборки.

Таким

образом,

число

сочетаний

с

повторениями из n элементов по k равно числу решений
уравнения
x1 + x2 +…+ xn = k

(11)

в целых неотрицательных числах. Сделаем замену неизвестных.
Пусть yi =xi + 1. Относительно новых неизвестных уравнение
(11) запишется в следующем виде:
y1 + y2 +…+ yn = n + k.

(12)

Нас интересует число решений этого уравнения в целых
положительных числах. Если взять строчку из n + k точек и в
промежутках между ними поставить n – 1 разделительную
черточку, то можно считать y1 числом точек в первой группе,
y2 – числом точек во второй группе и т. д.:

19

.... | ..... | L | ....
y1

y2

.

yn

Таким образом, число решений уравнения (12) равно числу
способов расставить n – 1 черточек в n + k – 1 промежутках
между точками. Число способов выбрать n – 1 промежутков (в
которые ставятся черточки) из n + k – 1 промежутков равно
числу сочетаний из n + k – 1 по n – 1, то есть числу Cnn+−k1 −1 .
Следовательно, число сочетаний с повторениями из n элементов
по k равно Cnn+−k1 −1 .
Пример. Найдем число способов разложить 10 одинаковых

монет по трем карманам. Каждый расклад монет представляет
собой сочетание с повторениями из трех элементов по 10.
Каждый «карман» входит в выборку столько раз, сколько монет
в него положено. Таким образом, искомое число способов
2
расклада равно C12
=

12 ⋅ 11
= 66 .
2

Используя сочетания можно получить новое обоснование
формулы для числа перестановок с повторениям (8). В самом
деле, пусть рассматриваются перестановки с повторениями
типа (n1, n2,…, nk) из элементов множества X = {x1, x2,…, xk}.
Для определенности будем считать, что k = 3. Чтобы составить
перестановку с повторениями, нужно указать места, на которых
расположены элементы x1; места, на которых расположены
элементы x2, места, на которых расположены элементы x3. Для
расстановки

элементов

x1

можно

выбрать

любые

n1

20
из n1 + n2 +…+ nk

мест.

Это

можно

сделать

Cnn1+ n
1

2 + K+ n k

способами. Элементы x2 можно расставлять на незанятые места,
которых остается n2 +…+ nk. Значит, места для элементов x2
можно выбрать Cnn2 +K+ n
2

способами. Продолжая подобным

k

образом, приходим к тому, что элементы xk–1 должны быть
расставлены на nk–1 + nk мест, а элементы xk – на оставшиеся nk
мест. По правилу произведения получаем:
P(n1 , n2 , K, nk ) = Cnn1+ n
1

2

+ K+ n k

⋅ Cnn2 +K+ n ⋅ K ⋅ Cnnk .
2

k

k

Если теперь записать числа сочетаний в факториалах, то
после сокращений получится (8).
Заметим, кстати, что Cnk = P(k , n − k ) .
8. 4. Некоторые свойства чисел Cnk

Непосредственно из формулы (8) легко усмотреть, что при
любых n и k, 0 ≤ k ≤ n, верно равенство
Cnk = Cnn − k .

(13)

Если 0 ≤ k < n, то
Cnk + Cnk +1 = Cnk++11 .

(14)

21
С использованием (9) доказательство может быть получено
непосредственной проверкой:
Cnk + Cnk +1 =

=

n!
n!
n!(k + 1) + n!(n − k )
+
=
=
k!(n − k )! (k + 1)!(n − k − 1)!
(k + 1)!(n − k )!
n!(n + 1)
(n + 1)!
=
= Cnk++11 .
(k + 1)!(n − k )! (k + 1)!(n − k )!

Сумма
Cn0 + Cn1 + Cn2 + ... + Cnn

(15)

– это число всех подмножеств n-множества (число пустых
подмножеств Cn0 плюс число одноэлементных подмножеств C1n
и т. д.). Как было установлено ранее, n-множество имеет 2n
подмножеств. Следовательно,
Cn0 + Cn1 + Cn2 + ... + Cnn = 2 n .

(16)

Впрочем, с использованием (14) формула (16) может быть
получена

по

индукции.

справедливость (16)

легко

При

малых

проверяется

значениях

n

непосредственно.

Индуктивный шаг сводится к следующей несложной выкладке:
Cn0+1 + Cn1 +1 + Cn2+1 + ... + Cnn++11 =

= Cn0+1 + (Cn0 + Cn1 ) + (Cn1 + Cn2 ) + ... + (Cnn −1 + Cnn ) + Cnn++11 =
= (Cn0 + Cn1 + ... + Cnn −1 + Cnn++11 ) + (Cn0+1 + Cn1 + ... + Cnn ) =
= 2(Cn0 + Cn1 + Cn2 + ... + Cnn ) .
В последнем переходе использовалось то, что Cnn++11 = 1 = Cnn
и Cn0+1 = 1 = Cn0 .

22
Формула (14) позволяет последовательно заполнять строки
таблицы, называемой треугольником Паскаля. Рассмотрим
первые пять строк этой таблицы:

0
1
2
3
4

1
1
1
1
1

1
2 1
3 3 1
4 6 4 1

В строке с номером n (указанном слева от вертикальной
черты) расположены числа Cn0 , C1n , …, Cnn . В соответствии
с (14), складывая два соседних числа в строке n, мы получим
число в строке n + 1, стоящее под правым слагаемым.
Рассмотрим

бином

(x + y)n.

Для

любого

целого

неотрицательного числа n имеет место следующее тождество:
( x + y)n =

n

∑ Cnk x n − k y k ,

(17)

k =0

или в развернутом виде:
( x + y ) n = Cn0 x n y 0 + Cn1 x n −1 y1 + ... + Cnn x 0 y n ,
называемое формулой Ньютона.
Доказательство

этого

факта

несложно

провести

по

индукции, используя (14). Формула Ньютона, очевидно, верна
при n = 0. Чтобы выполнить индуктивный шаг, в равенстве
(x + y)n+1 = (x + y)n(x + y)

23
заменим (x + y)n суммой из правой части (17). После раскрытия
скобок и приведения подобных получаем:
( x + y ) n +1 =
=

xCn0 x n y 0

= x n +1 +

+

∑ (xCnk x n − k y k + yCnk −1 x n − k +1 y k −1 ) + yCnn x 0 y n =
n

k =1

∑ (Cnk + Cnk −1 )x n − k +1 y k + y n +1
n

k =1

В соответствии с (14),
Cnk + Cnk −1 = Cnk+1 ,
так что
( x + y ) n +1 = Cn0+1x n +1 y 0 + Cn1 +1x n y1 + ... + Cnn++11x 0 y n +1
и, следовательно, формула Ньютона верна и при показателе
степени равном n + 1.
Подставка в формулу Ньютона конкретных числовых
значений

переменных

позволяет

тождества. Вот некоторые из них:
n

∑ Cnk

= 2n ;

k =0
n

∑ (−1) k Cnk

= 0;

k =0
n

∑ 2k Cnk

k =0

= 3n .

получать

различные

24
В первом случае (полученное тождество совпадает с (16))
мы подставили в (17) x = 1, y = 1; во втором – x = 1, y = –1; в
третьем – x = 1, y = 2.
8. 5. Принцип включения и исключения

Пусть X – некоторое n-множество, а p1, p2, …, pk – свойства,
которыми могут обладать элементы множества X. Каждый
элемент множества X может обладать одним или несколькими
свойствами из числа перечисленных или не обладать ни одним
из них. Обозначим через ni число элементов со свойством pi,
i = 1, 2,…, k. Вообще, пусть

ni1i2 ...ir – число элементов со

свойствами pi1 , pi2 , …, pir . Тогда число элементов n0, не
обладающих ни одним из перечисленных свойств, задается
следующей формулой:
n0 = n –

∑ ni + ∑ ni1i2 +…
i1 < i2

i

∑ ni1i2 Kir +…+(–1)nn12…n.

…+(–1)r

(18)

i1 < i2 <K< ir

Элемент

a,

не

обладающий

ни

одним

свойством,

учитывается один раз в слагаемом n и ни одно другое слагаемое
вклад не вносит. Элемент a, обладающий ровно одним
свойством j, учитывается по одному разу в слагаемых n и

∑ ni ;
i

его вклад в правую часть (18) составляет 1 – 1=0. Рассмотрим
теперь элемент a, обладающий s ≥ 1 свойствами j1,…, js.

25
Элемент a дает вклад 1 в каждое слагаемое

∑ ni1i2 Kir

такое,

i1 < i2 <K< ir

что {i1,…, ir} ⊂ {j1,…, js}. Для каждого фиксированного r ≤ s
число таких слагаемых равно числу r-подмножеств s-множества
{j1,…, js}, т. е. числу сочетаний С sr . Следовательно, вклад
элемента a в правую часть (18) равен
1 – С1s + С s2 +…+(–1)r С sr +…+(–1)s С ss =(1 – 1)s = 0.
Таким образом, правая часть (18) учитывает каждый
элемент, не обладающий ни одним из указанных свойств ровно
один раз, а каждый элемент, обладающий хотя бы одним
свойством, – ноль раз. Но это и означает, что правая и левая
части (18) равны.
В качестве применения метода включения и исключения
рассмотрим известную задачу о беспорядках.
Перестановка

a1a2…an

чисел

1, 2, …, n

называется

беспорядком, если ai ≠ i для всех i = 1, 2, …, n. Таким образом,
беспорядок – это перестановка, в которой ни один элемент не
занимает «своего» места. Обозначим число беспорядков
через Dn.
Пример. Перечислим беспорядки из четырех элементов:

2143; 2341; 2413; 3142; 3412; 3421; 4123; 4312; 4321.
Значит, D4 = 9.

26
На множестве всех перестановок из элементов 1, 2, …, n
определим набор свойств pi, i = 1, 2, …, n. Перестановка

a1a2…an обладает свойством pi, если ai = i. Тогда число
беспорядков – это число перестановок, не обладающих ни
одним из указанных свойств. Число перестановок, оставляющих
на месте ровно r фиксированных символов (например, 1, 2,…, r)
равно (n – r)!. Выбрать r неподвижных символов можно Сnr
способами. Следовательно в формуле (18) каждое слагаемое

ni1i2 Kir равно (n – r)!, а общее число таких слагаемых Сnr .
Следовательно,

∑ ni1i2 Kir

i1 < i2 <K< ir

= (n − r )!Cnr =

n!
.
r!

Таким образом, в соответствии с формулой (18) имеем:

Dn = n!−
Последнее

n! n!
n!
n!
+ + ... + (−1) r + ... + (−1) n .
r!
n!
1! 2!

равенство

можно

переписать

следующим

образом:

Dn
1
1
1 1
= 1 − + + ... + (−1) r + ... + (−1) n .
n!
r!
n!
1! 2!

(19)

Как известно из анализа, правая часть (19) представляет
собой

приближение

Следовательно,

числа

e–1

по

формуле

Тейлора.

Dn
≈ e −1 и, значит, Dn ≈n!e–1. При этом
n!

27
абсолютная
превосходит
Пример.

величина

погрешности

приближения

не

1
.
n +1
При

n=4

имеем

D4 ≈ 4!e–1 = 24e–1 ≈ 8.83 .

Напомним, что выше мы непосредственно нашли точное
значение D4 ≈ 9.

28

9. Биномиальная модель ценообразования
активов
9. 1. Биномиальная решетка

Предположим, что за каждый период времени, скажем час,
стоимость

некоторого

актива

S0

увеличивается

или

уменьшается. Пусть u > 1 – повышающий коэффициент, а

d < 1 – понижающий, так что стоимость актива за единицу
времени либо увеличивается и становится равной S0u, либо
уменьшается и становится равной S0d. Если стоимость актива
повышалась p раз и понижалась q раз, то его стоимость станет
равной S0updq. При ud = 1 изменение стоимости актива может
быть графически представлено так называемой биномиальной

решеткой. На рис. 1 приведена трехпериодная биномиальная
решетка.
S0u3

S0u2
S0u
S0

S0u
S0
S0d

S0d
S0d2

S0d3

Рис. 1
Около каждого узла решетки указывается стоимость актива
при

соответствующем

варианте

развития

событий.

Максимальной стоимость актива окажется в том случае, когда в

29
каждом периоде его стоимость повышалась. Вообще, каждому
варианту развития событий, при которых стоимость актива
окажется равной S0updq, соответствует путь по стрелкам из
начального узла S0 в узел S0updq. Сопоставим каждому пути
последовательность букв d и u, в которой d соответствует
понижению стоимости, а u – повышению. Число всевозможных
путей из узла S0 в узел S0updq равно числу способов расставить p
букв u на p + q местах, т. е. числу сочетаний C pp+ q .
9. 2. Опционы. Основные понятия

Опционы относятся к числу так называемых производных

финансовых инструментов.
Опцион «колл» (call option) дает его владельцу право (но, в
отличие от контракта, не обязанность) купить определенный
актив по фиксированной цене, называемой ценой исполнения, в
установленное

время

в

будущем

или

до

наступления

установленной даты. В роли актива могут выступать товар,
ценная бумага, валюта и т. п. Опцион «пут» (put option) дает его
владельцу аналогичное право продать актив. Реализация права
на покупку (в случае опциона «колл») или продажу (в случае
опциона «пут») называется исполнением опциона.
Различают американские и европейские опционы. Если
опцион может быть исполнен в любой момент до даты
истечения

срока

Европейский

действия, его

опцион

может

называют

быть

американским.

исполнен

только

в

30
установленный срок. Не вдаваясь в детали опционной торговли,
мы ограничимся рассмотрением европейских опционов.
Величина выигрыша от исполнения опциона «колл» равна

C = max {0, S – X},
где S – цена актива в момент исполнения опциона, а X – цена
исполнения опциона. В самом деле, если в момент исполнения
опциона цена актива S превышает цену исполнения X, владелец
опциона использует свое право купить опцион по цене ниже
рыночной. При этом на разнице цен он получает выигрыш,
равный S – X. В случае если на момент исполнения цена актива
оказывается

ниже

цены

исполнения,

владелец

опциона

отказывается от покупки.
Пример. Стоимость актива в момент исполнения опциона

«колл» равна 60, цена исполнения равна 50. Купив по цене

X = 50 актив, продающийся на рынке по цене S = 60, владелец
опциона получает выигрыш C = 10. Если бы стоимость актива в
момент исполнения опциона оказалась ниже 50, владелец
опциона не стал бы использовать свое право на покупку актива
по цене X = 50.
Аналогичным образом величина выигрыша от исполнения
опциона «пут» составляет

P = max {0, X – S}.
За приобретение опциона, как и за всякое приобретение
права без обязательств, нужно платить. Далее биномиальная

31
модель

используется

для

того,

чтобы

определить

«справедливую» цену опциона, называемую премией за опцион.
9. 3. Однопериодная модель

Предположим, что инвестор в момент t = 0 покупает актив A
по цене S0. За единицу времени от t = 0 до t = 1 стоимость
актива может повыситься или понизиться. Пусть u и d –
повышающий и понижающий коэффициенты, r – безрисковая
процентная ставка и выполняется следующее условие:

d < 1 + r < u.
Инвестор хочет избежать риска, связанного с изменением
стоимости актива к моменту t = 1. С этой целью он продает
некоторое количество k (быть может, дробное) опционов
«колл» на актив A со сроком исполнения t = 1. Это означает, что
инвестор принимает на себя обязательство продать k активов A
в момент времени t = 1 по цене исполнения X. Требуется
определить значение k и величину премии за опцион (в
предположении, что транзакционные издержки отсутствуют).
Введем следующие обозначения (рис. 2):

S0 – цена актива в момент времени t = 0;
S1(u) = S0u – цена актива в момент времени t = 1 в случае
повышения;

S1(d) = S0d – цена актива в момент времени t = 1 в случае
понижения;

C0 – цена опциона в момент времени t = 0 (премия за
опцион);

32

X – цена исполнения опциона;
C1(u) = max{0, S0u – X} – цена опциона в момент времени t = 1 в случае повышения;

C1(u) = max{0, S0d – X} – цена опциона в момент времени t = 1 в случае понижения.

C1(u) =
= max{0,S0u–X}

S1(u) = S0u

S0

C0
C1(d) =
= max{0,S0d–X}

S1(d) = S0d

Рис. 2
На покупку актива инвестор затратил S0, от продажи k
опционов он получил kC0. В результате он стал владельцем
портфеля, состоящего из одного актива и k опционов. На
формирование

этого

портфеля

затрачено

S0 – kC0.

Величина S0 – kC0 составляет стоимость портфеля в момент
времени t = 0. Если бы эта сумма была размещена под
безрисковую процентную ставку, то к моменту времени t = 1
она бы выросла до
(1 + r)(S0 – kC0).

(1)

С другой стороны, стоимость портфеля в момент времени

t = 1 составит S1 – kC1, т. е.
S1(u) – kC1(u)

33
в случае повышения и

S1(d) – kC1(d)
в случае понижения. Если подобрать k так, чтобы выполнялось
равенство

S1(u) – kC1(u) = S1(d) – kC1(d),

(2)

то портфель окажется безрисковым. Из (2) находим:

k=

S1 (u ) − S1 (d )
.
C1 (u ) − C1 (d )

(3)

При таком k стоимость портфеля в момент времени t = 1
окажется равной

S1 (d )C1 (u ) − S1 (u )C1 (d )
.
C1 (u ) − C1 (d )

(4)

Так как портфель дает гарантированный доход, то в
соответствии с принципом безарбитражности (прибыль без
риска невозможна) его стоимость (4) должна совпадать
наращенной суммой (1). Таким образом, получаем следующее
равенство:

S (u ) − S1 (d )  S1 (d )C1 (u ) − S1 (u )C1 (d )
(1 + r ) S0 − 1
C0  =
.
C
u
C
d
(
)
(
)
C
(
u
)

C
(
d
)



1
1
1
1
После несложных преобразований, учитывая, что S1(u) = S0u
и S1(d) = S0d, находим:

C0 =
Полагая

1 1+ r − d
u − (1 + r )

C1 (u ) +
C1 (d )  .

1+ r  u − d
u−d


(5)

34

p=

1+ r − d
u − (1 + r )
, q=
,
u−d
u−d

(6)

формуле (5) можно придать следующий вид:

C0 =

1
( pC1 (u ) + qC1 (d ) ) .
1+ r

(7)

Пример. Пусть текущая стоимость актива равна 100 рублей.

За год его стоимость может повыситься на 20% или понизиться
на 15%.

Безрисковая

годовая

ставка

равна

10%.

Цена

исполнения опциона «колл» со сроком исполнения в конце года
равна 105 руб. Определим величину премии за опцион.
Если цена актива вырастет и составит 1,2⋅100 = 120 руб., то
владелец опциона воспользуется своим правом на покупку
актива за 105 рублей. Следовательно, цена опциона C1(u)
составит 120 –105 = 15 руб.
Если цена актива понизится и составит 0,85⋅100 = 85 руб., то
владелец опциона свое право на покупку актива за 105 рублей
использовать не станет, и цена опциона C1(d) будет равна нулю.
В соответствии с (6) и (7) находим коэффициенты:

p=

1,1 − 0,85
1,2 − 1,1
≈ 0,714 , q =
≈ 0,286
1,2 − 0,85
1,2 − 0,85

и премию за опцион:

C0 =

1
(0,714 ⋅15 + 0,286 ⋅ 0) = 9,74 руб.
1,1

35
По формуле (3) можно найти число опционов, которые
нужно

продать, чтобы хеджировать

риск, связанный

с

изменением цены актива за год:

k=

120 − 85
≈ 2,33 .

15 0

Предположим, в начале года инвестор покупает 30 единиц
актива A, заплатив 3000 рублей. Одновременно он продает 70
опционов с ценой исполнения 105 рублей. От продажи
опционов инвестор получает 9,74⋅70 = 681,80 руб., которые
размещает под 10%. К концу года сумма, полученная от
продажи опционов, вырастет до 749,98 рублей.
Если стоимость актива к концу года вырастет, то, продав
купленные им 30 единиц актива, инвестор может получить
120⋅30 = 3600

руб.

При

этом

ему

придется

выполнить

обязательства по 70 опционам, купив 70 единиц актива по
120 рублей. и продав их владельцам опционов по 105 рублей.
На это придется потратить 120⋅70 – 105⋅70 = 1050 руб.
Доход на конец года составит в этом случае
49,98 + 3600 – 1050 = 3299,98 руб.
Если стоимость актива к концу года понизится, то, продав
купленные им 30 единиц актива, инвестор может получить
85⋅30 = 2550 руб. Обязательств по опционам не возникнет, так
что

и

в

этом

случае

доход

составит 749,98 + 2550 = 3299,98 руб.

на

конец

года

36
9. 4. Двух- и трехпериодные модели

Рассмотрим

случай,

когда

срок

исполнения

опциона

наступает в конце второго периода.
Введем следующие обозначения (рис. 3):

S0 – цена актива в момент времени t = 0;
S1(d) = S0d, S1(u) = S0u – цены актива в момент времени t = 1
в случае соответственно понижения или повышения цены;

S1(u,u) = S0u2 , S1(u,d) = S0ud, S1(d,u) = S0du, S1(d,d) = S0d2 –
цены актива в момент времени t = 2 в зависимости от варианта
развития событий (повышение оба раза, повышение–понижение
и т.д.);

C0 – цена опциона в момент времени t = 0;
X – цена исполнения опциона;
C1(d), C1(u) – цены на опцион в момент времени t = 1 в
случае соответственно понижения или повышения цены;

C2(x1,x2) = max{0, S2(x1,x2) – X} – цена опциона в момент
времени t = 2 при изменении цены актива по сценарию (x1,x2)
(например, C1(u,d) = max{0, S2(u,d) – X}).
S0u
C1(u)
S0

S0ud
C1(d)
S0d

max(0,S0u2–X)

max(0,S0ud–X)
max(0,S0d2–X)

Рис. 3

37
Фрагменты двухпериодной решетки, представленные на
рис. 4, являются однопериодными решетками.
max(0,S0u2–X)

S0u
C1(u)
S0ud

max(0,S0ud–X)

S0d
C1(d)

max(0,S0d2–X)

Рис. 4
Применяя к ним формулу (7) для расчета цены опционов в
однопериодной модели, получаем:

C1 (u ) =

1
( pC2 (u, u ) + qC2 (u, d ) ) ;
1+ r

C1 (d ) =

1
( pC2 (d , u ) + qC2 (d , d ) ).
1+ r

Применим еще раз те же формулы к однопериодной
решетке, представленной на рис. 5, и воспользуемся тем,
что C2(d,u) = C2(u,d).

C1(u)
S0
C0
C1(d)

Рис. 5
Получаем:

38

C0 (u ) =

1
( pC1 (u ) + qC1 (d ) ) =
1+ r

=

1 
1
( pC2 (u, u ) + qC2 (u, d ) ) +
p
1+ r  1+ r
+q

=

1
(1 + r )

2

1
( pC2 (d , u ) + qC2 (d , d ) ) =
1+ r


(p 2C2 (u, u) + 2 pqC2 (u, d ) + q 2C2 (d , d )).

(8)

Пример. Пусть, как и в примере из предыдущего пункта,

текущая стоимость актива равна 100 руб. Но теперь мы
считаем, что изменения стоимости актива происходят дважды в
год. За полгода стоимость актива может повыситься на 9,54%
или понизиться на 7,80%. Полугодовой повышающий и
понижающий коэффициенты равны соответственно u = 1,0954
и d = 0,9220. Заметим, что u2 = 1,20 и d2 = 0,85.
Безрисковая годовая ставка равна 10%. Полугодовая ставка
определяется из равенства 1 + r = 1,1 = 1,0488 и равна 4,88%.

Цена исполнения опциона «колл» со сроком исполнения в
конце года равна 105 руб. Определим величину премии за
опцион.
Сначала вычислим коэффициенты p и q:
p=

1,0488 − 0,9220
1,0954 − 1,0488
≈ 0,731 , q =
≈ 0,269 .
1,0954 − 0,9220
1,0954 − 0,9220

Далее:
C2(u,u) = 120 – 105 = 15;

39
C2(u,d) = C2(d,u) = max{0, 100 – 105} = 0;
C2(d,d) = 0.

Таким образом (рис. 6):
C0 = 0,7312⋅15/1,1 = 7,29 руб.
C1(u) = 10,45

C0 =
= 7,29
C1(d) = 0

C2(u,u) = 15

C2(u,d) = 0
C2(d,d) = 0

Рис. 6
Пример. Опуская подробности, проведем расчеты для

трехпериодной модели. Исходные данные:
S0 = 100 –текущая цена актива;
u = 1,201/3 = 1,0627, d = 0,851/3 =0,9473 – повышающий и

понижающий коэффициенты изменения цены актива за 4
месяца;
r = 1,101/3 = 1,0323; 3,23% – безрисковая ставка за один

период;
X = 105 – цена исполнения опциона (со сроком исполнения в

конце года – через три периода).
Вычислим коэффициенты p и q:
p=

1,0323 − 0,9473
≈ 0,737 ,
1,0627 − 0,9473

q=

1,0627 − 1,0323
≈ 0,263 .
1,0627 − 0,9473

40
Используя

очевидные

обозначения,

последовательно

вычисляем:
C3(u,u,u) = 120 – 105 = 15;
C3(u,u,d) = C3(u,d,u) = C3(d,u,u) = 106,27 – 105} = 1,27;
C3(u,d,d) = C3(d,d,u) = C3(d,u,d) = max{0; 94,73 – 105} = 0;
C2(u,u) = (15⋅0,737 + 1,27⋅0,263)/1,0323 = 11,03;
C2(u,d) = C2(d,u) = 1,27⋅0,737/1,0323 = 0,91;
C2(d,d) = 0;
C1(u) = (11,03⋅0,737 + 0,91⋅0,263)/1,0323 = 8,11;
C1(d) = 0,91⋅0,737 /1,0323 = 0,65;
C0 = (8,11⋅0,737 + 0,65⋅0,263)/1,0323 = 5,96.

Нетрудно заметить, что в общем виде формула для расчета
премии

за

опцион

в

трехпериодной

модели

выглядит

следующим образом:
C0 =

p 3C3 (u ,u ,u ) + 3 p 2 qC3 (u ,u , d ) + 3 pq 2 C3 (u , d , d ) + q 3C3 ( d , d , d )

(1+ r )3

.

(9)

9. 5. Многопериодная модель
Теорема. Премия за опцион «колл» может быть вычислена

по следующей формуле:
C0 =

 n  n−k k n−k k
  p q (u d S0 − X ) ,

n
(1 + r ) u n − k d k S > X  k 
0
1

где
S0 – текущая цена актива A,

(10)

41
u и d – соответственно коэффициенты повышения и
понижения цены актива за один период;
r – безрисковая процентная ставка;
X – цена исполнения опциона «колл» на актив A;
n – число периодов до момента исполнения опциона.
Доказательство . Сначала заметим, что формула (10)
может быть записана следующим образом:
C0 =

n

 n  n−k k
n−k k

p
q
max(
u
d S0 − X ) =




n
k
(1 + r ) k = 0 
1

=

n

 n  n−k k
u , d ,..., d ) .
∑   p q Cn (un,...,
(1 + r ) n k = 0 k 
− k раз k раз
1

Теперь воспользуемся методом математической индукции.
Как было установлено ранее, формула (10) верна для одного и
для двух периодов (формулы (7), (8)), т. е. при n = 1 и n = 2.
Покажем, что если формула (10) верна для n и меньшего числа
периодов, то она верна и для n + 1 периода.
Итак, предположим, что срок исполнения опциона наступает
через n + 1 период.
Как было установлено при анализе однопериодной модели,
справедливо следующее равенство:
C0 =

1
( pC1 (u ) + qC1 (d ) ) .
1+ r

(11)

От момента t = 1 до момента t = n+1 проходит n периодов. В
случае, если за первый период цена актива повысилась, можно

42
воспользоваться формулой (10) для n периодов, считая S0u
текущей ценой актива. Получаем:
C1 (u ) =

1

n

n

  p n − k q k max(u n − k +1d k S 0 − X ) .
n ∑k 
(1 + r )
k = 0



Аналогично:
C1 (d ) =

n

 n  n−k k
n − k k +1

p
q
max(
u
d S0 − X ) .


k 
n
(1 + r ) k = 0 
1

После подстановки в (11) находим:
C0 =

 n  n − k +1 k
n − k +1 k

p
q
max(
u
d S0 − X ) +




(1 + r ) n +1 k = 0 k 
+

=

n

1

n

 n  n − k k +1
  p q max(u n − k d k +1S0 − X ) =
n +1 ∑  k 
(1 + r ) k = 0 
1

1
(1 + r )

n +1

p n +1 max(u n +1S0 − X ) +
n

+

 n  n − k +1 k
n − k +1 k

p
q
max(
u
d S0 − X ) +




n +1
k
(1 + r ) k =1 

+

 n  n − k +1 k
n − k +1 k

p
q
max(
u
d S0 − X ) +




(1 + r ) n +1 k =1 k − 1

+

1

n

1

1
(1 + r )

n +1

q n +1 max(d n +1S 0 − X ) .

Воспользовавшись тождеством
 n   n   n + 1
 = 
 ,
  + 
 k   k − 1  k 
приходим к следующему равенству:

43
C0 =

1
(1 + r )
+
+

n +1

p n +1 max(u n +1S0 − X ) +

 n + 1 n − k +1 k
n − k +1 k

p
q
max(
u
d S0 − X ) +


 k 
n +1
(1 + r ) k =1

n

1

1
(1 + r )

n +1
n +1
q
max(
d
S0 − X ) ,
n +1

откуда и следует, что
C0 =

n +1

 n + 1 n − k +1 k
 p
q max(u n − k +1d k S0 − X ) ,
k = 0 k 

1


n +1 ∑ 
(1 + r )

чем и завершается доказательство теоремы.
Преобразуем формулу (10). Пусть m – наибольшее целое
число, для которого un–mdm S0 > X. Тогда
C0 =

m

 n  n−k k n−k k
  p q (u d S 0 − X ) =
n ∑k 
(1 + r ) k = 0 
1

m

 n  n−k n−k k k
X
=
p
u
q
d



∑ 
(1 + r ) n k = 0 k 
(1 + r ) n
S0

В

теории

вероятностей

m

 n  n−k k
∑  k  p q .
k = 0 

устанавливается

следующий

фундаментальный факт (формула Лапласа).
Если p и q – неотрицательные числа такие, что p + q = 1, то
при

больших

равенство:

значениях

n

имеет

место

приближенное

44
m

 m − nq 
 n  n−k k

 ,
N
p
q



∑k 
 npq 
k = 0 

(12)

где
1
N ( x) =


x

−t
e


2

/2

dt –

−∞

так называемая функция нормального распределения.
Часто вместо функции N(x) используется функция
x

1
−t 2 / 2
Φ(x) = N(x) – 0,5 =
e
dt ,

2π 0
таблица значений которой приводится, как правило, в любом
учебнике по теории вероятностей. Функция Φ(x) нечетна,
монотонно возрастает и lim Φ ( x) = 0,5 . Значения, близкие к 0,5,
x→∞

функция Φ(x) принимает уже при сравнительно небольших
значениях аргумента. Например, Φ(3) ≈ 0,49865.
В соответствии с (12) имеем:
m

X

n

X

  pn−k qk ≈
n ∑k 
(1 + r )
(1 + r ) n
k = 0



 m − nq 
 .
N 
 npq 

Заметим, что pu + qd = 1 + r. В самом деле:
pu + qd =

1+ r − d
u − (1 + r )
u+
d
u−d
u−d
=

Положим

(1 + r )u − (1 + r )d
=1+ r .
u−d

45
p′ =

pu
qd
, q′ =
.
1+ r
1+ r

Так как p′ + q′ = 1, то
m

m n
 n  n−k n−k k k
  n−k k
S
p
u
q
d
=


  p′ q′ ≈


0
k 
n
(1 + r ) k = 0 
k = 0 k 

S0

 m − nq ′ 
 .
≈ S0 N 


n
p
q


Окончательно

получаем

следующее

приближенное

равенство:
 m − nq ′ 
 m − nq 
X
 –
 .

C0 ≈ S0 N 
N
n


npq
n
p
q
 (1 + r )




(13)

Модификация (13) приводит к широко применяемой
формуле Блэка–Шоулза.
Пример. Текущая цена актива составляет 100 руб. За один

день цена актива может увеличиться на 0,3% или уменьшиться
на 0,3%. Безрисковая ставка равна 10%. Требуется определить
премию за опцион «колл» на этот актив со сроком исполнения
через 360 дней и ценой исполнения 105 руб. Имеем следующие
исходные данные:
S0 = 100; X = 105;
1 + r = 1,11/360 = 1,00026;
u = 1,003; d = 0,997; n = 360.
Найдем наибольшее m, при котором
S0u360–mdm > X.

46
Логарифмируя, получаем неравенство
(360 – m)ln u + m ln d > 1,05,
откуда
m < (360 ln u – 1,05)/(ln u/d) ≈171,6,
так что m = 171. Вычисляем:
p=

1,00026 − 0,997
1,003 − 1,00026
= 0,54413 ; q =
= 0,45587 ;
1,003 − 0,997
1,003 − 0,997

p' =

0,54413 ⋅1,003
0,45587 ⋅ 0,997
= 0,54562 ; q' =
= 0,45438 ;
1,00026
1,00026
171 − 360q'
= 0,78571;
360 p ' q '

171 − 360q
= 0,72881.
360 pq

Далее,
N(0,78571) = 0,78398;

N(0,72881) = 0,766948.

Наконец,
C0 = 100⋅0,78398 – 105⋅0,766948/1,1 = 5,19 руб.

47

10. Биномиальный ряд. Производящие функции
10. 1. Степенные ряды

Хотя название «бином Ньютона» и закрепилось за формулой
( x + y)n =

n

∑ Cnk x n − k y k ,

(1)

k =0

истинная заслуга Ньютона состоит в том, что ему удалось
обобщить формулу (1) на случай произвольных показателей
степени. Изучением этого обобщения мы займемся в п. 10.2.
Ниже излагаются необходимые сведения о степенных рядах.
Формальным

степенным

рядом

(от

переменной

z)

называется выражение вида


∑ ak z k ,

(2)

k =0

где ak – члены числовой последовательности, называемые
коэффициентами степенного ряда (2). Символ суммирования
в (2), вообще говоря, формальный. Тем не менее (2) записывают
также в виде
a0 + a1z + a2z2 + a3z3 +… .
Пусть даны формальные ряды




∑ ak z и ∑ bk z k .

k =0

k

k =0

(3)

48
Их суммой по определению является ряд


∑ (ak + bk ) z k .

k =0

Произведением рядов (3) называется ряд


∑ сk z k ,

k =0

такой, что
ck = a0bk + a1bk–1 +…+ akb0
для всех k = 0, 1, 2,… . Заметим, что коэффициенты ck
получаются так, как если бы в произведении рядов были
раскрыты скобки и приведены подобные:
(a0 + a1z + a2z2 +…)(b0 + b1z + b2z2 +…) =
= a0b0 + (a0b1 + a1b0)z + (a0b2 + a1b1 + a2b0)z2 +…
Производная ряда (2) определяется как ряд
a1 + 2a2z + 3a3z2 +… .
Несложно проверить, что так определенные сложение,
умножение и дифференцирование рядов обладают привычными
свойствами.

Сложение

коммутативны,

и

сложение

умножение

ассоциативны

дистрибутивно

и

относительно

умножения. Производная суммы равна сумме производных.
Справедливо также соотношение (uv)′ = u′v + uv′.
Говорят, что ряд (2) сходится при z = t, где t – некоторое
числовое значение, если существует предел
n

k
lim ∑ ak t .

n →∞ k = 0

(4)

49
Предел (4) в случае, когда он существует, называют суммой
ряда при z = t и обозначают



∑ ak t k .

k =0

Любой степенной ряд сходится при z =0. Суммой ряда (2) в
нуле является число a0. Если ряд сходится при z = t1, то он
сходится и при любом z = t2, для которого | t2| < | t1|. Таким
образом, если степенной ряд сходится в некоторой точке,
отличной от нуля, то он сходится во всех точках некоторого
открытого

промежутка

вида

(–r, r),

где

r ∈(0; +∞].

На

промежутке, в точках которого ряд сходится, его сумма задает
функцию. Пишут
f ( z) =



∑ ak z k ,

k =0

имея в виду, что ряд в правой части сходится в некоторой
окрестности нуля, и в каждой точке t из этой окрестности
выполняется равенство f (t ) =



∑ ak t k .

k =0

Пример. Ряд

1 + z + z2 + z3 + …
сходится во всех точках промежутка (–1, 1). В каждой точке
t ∈(–1, 1) этот ряд представляет собой сумму бесконечно
убывающей геометрической прогрессии со знаменателем t. В
соответствии с известной формулой
1 + z + z 2 + z3 + … =

1
.
1− z

(5)

50
Если степенные ряды



∑ ak z

k



∑ bk z k сходятся в

и

k =0

k =0

некоторой общей точке, то в этой точке сходятся их сумма и
произведение; если степенной



∑ ak z k

ряд

сходится в

k =0

некоторой точке, отличной от нуля, то в этой точке сходится и
его производная. Пусть,
f ( z) =





k

∑ ak z ; g ( z ) = ∑ bk z k .

k =0

k =0

Тогда:
 ∞
  ∞

 ∑ ak z k  +  ∑ bk z k  = f ( z ) + g ( z ) ;
 k =0
  k =0


 ∞

k 
 ∑ ak z  ∑ bk z k  = f ( z ) g ( z ) ;
 k =0
 k = 0



∑ kak z k −1 = f ′( z ) .

k =1

10. 2. Биномиальный ряд

Начнем с того, что запишем формулу (1) в виде
(1 + z ) n =

n k

∑  k  z
k ≥0  

(6)

(когда числа Cnk трактуются как биномиальные коэффициенты,
n
обычно используется обозначение   ).
k 
Заменяя в формуле (5) z на –z, получаем:

51
1 – z + z2 – z3 + … =

1
.
1+ z

(7)

По аналогии с (7) запишем последнее соотношение в виде
(1 + z ) −1 =

 − 1 k

∑  k  z .

k ≥0 

(8)

Сравнивая (7) и (8), получаем:
 − 1
  = 1;
0

 − 1
  = −1 , … .
1

Вообще,
 − 1
  = (−1) k .
k 
Возьмем производную от обеих частей равенства (8):
− (1 + z ) − 2 =

 − 1

∑ k  k  z k −1 .

k ≥1





Полагая
 − 2
 − 1
  = −  ; …;
 0 
1

 − 2
 −1 
 ; … ,
  = −(k + 1) ⋅ 
+
k
k
1
 



получаем равенство
(1 + z ) − 2 =
Продолжая

подобным

 − 2 k
∑  k  z .

k ≥0 

образом,

мы

будем

получать

равенства вида
(1 + z ) − n =

− n

∑  k  z k .

k ≥0 

(9)

52
Чтобы получить рекуррентные соотношения, связывающие
биномиальные

коэффициенты,

продифференцируем

обе

части (9):
− n(1 + z ) − ( n +1) =

 − n  k −1
k
∑  k  z .

k ≥1 

Следовательно,
(1 + z ) − ( n +1) =

k − n

k +1 − n 

∑ − n  k  z k −1 = ∑ − n  k + 1 z k .
 


k ≥1
k ≥0

Сравнивая это равенство с равенством вида (9) для
показателя n + 1, приходим к следующему соотношению:
 − (n + 1) 
k +1 − n 
 = −
 .


+
k
1
k
n





(10)

Используя (8) и (10) и применяя метод математической
индукции, нетрудно придти к следующему заключению:
− n
n(n + 1) ⋅ K ⋅ (n + k − 1)
= (−1) k Cnk+ k −1 .
  = (−1) k
k!
 k 

(11)

Равенство (11) можно записать в следующем виде:
 − n  − n(−n − 1) ⋅ K ⋅ (−n − k + 1)
.
  =
k!
 k 

(12)

Формулу для числа сочетаний и (12) можно свести в одну
общую формулу:
 б  б (б − 1) ⋅ K ⋅ (б − k + 1)
,
  =
k
!
k
 
где α – положительное или отрицательное целое число.

(13)

53
На самом деле в качестве α можно

взять любое

действительное число. При этом справедливо соотношение
б б
б
(1 + z ) б = 1 +   z +   z 2 +   z 3 + ... .
1 2
 3
Чтобы

из

(14)

получить

(13)

(14)

достаточно

продифференцировать k раз обе части равенства (14) и
подставить z =0:
б
 б 
б (б − 1) K (б − k + 1)(1 + z ) б − k = k!  + (k + 1)!
 z + K ;
+
k
k
1
 


б
б (б − 1) K (б − k + 1) = k!  .
k 
Пример. Покажем, что

12
 2k 
 = (−1) k   (k + 1)2 2 k +1 .

 k + 1
k 

(15)

В соответствии с (13) имеем:

 1 2  1 2 (1 2 − 1) ⋅ K ⋅ (1 2 − k )
1 ⋅ 1 ⋅ 3 ⋅ K ⋅ (2k − 1)
.
= (−1) k
 =

k +1
k
1
+
k
(
+
1
)!
2 (k + 1)!


Умножив числитель и знаменатель последней дроби на
2 ⋅ 4 ⋅…⋅ 2k = 2k ⋅ k!,
получаем доказываемое соотношение:
12
1
(2k )!
(2k )!
 = (−1) k 2k +1
= (−1) k 2k +1
.

k
+
1
k
!
k
!
k!(k + 1)!
2
(k + 1)
2



54
Используя предыдущую формулу, вычислим начальные
коэффициенты разложения в ряд функции (1 + z)1/2. Получаем:
1 2 
  = 1;
 0 

1 2  1
  = ;
 1  2

1 2 
1
  = − ;
8
 2 

1 2  1
  = ;
 3  16

1 2 
5
  = −
.
4
128
 

Таким образом,
1 z3 − 5 z 4 + K .
1 + z = 1 + 12 z − 18 z 2 + 16
128

10. 3. Производящие функции и примеры их применения
при решении комбинаторных задач

Если


f ( z) =

∑ ak z k ,

(16)

k =0

то

f(z)

называют

производящей

функцией

числовой

последовательности a0, a1, …, ak, … . Если последовательность
конечна или, начиная с некоторого места, все ее члены равны
нулю, то наряду с (16) пишут также
f ( z) =

n

∑ ak z k ,

k =0

предполагая, что члены последовательности с номерами больше
чем n отсутствуют или равны нулю. Иногда производящей
функцией последовательности a0, a1, …, ak, … называют ряд в
правой части (16) и говорят, что производящая функция
представлена в замкнутом виде, если для f(z) указано конечное
аналитическое выражение.

55
Примеры. В приводимой ниже таблице даны некоторые

простые последовательности и их производящие функции. В
основе

большинства

биномиального

примеров

ряда:

лежат

производящей

последовательности

частные

функцией

биномиальных

случаи
конечной

коэффициентов

Cn0 , C1n , …, Cnn служит функция f(z) = (1 + z)n; для бесконечной
последовательности

биномиальных

коэффициентов

б
  ,
k 

k = 0, 1, …, производящей функцией служит f(z) = (1 + z)α.
Обоснование для последних двух примеров дается в курсе
анализа.
Последовательность Производящая

Замкнутый вид

функция
1,2,1,0,0,…

1 + z +z2

1,1,1,1,…

∑ zk

1
1− z

1,–1,1,–1,…

∑ (−1) k z k

1
1+ z

1,0,1,0,…

∑ z 2k

1
1− z 2

1,2,4,8,16,…

∑ 2k z k

1
1− 2 z

1,2,3,4,…

∑ (k + 1) z k

1
(1− z ) 2

1,1, 12 , 31! , 41! …



0,1, 12 , 13 , 14 …

∑ zk

zk
k!
k

1 + z +z2

ez
ln 1−1 z

56
Рассмотрим

несколько

примеров

комбинаторного

применения производящих функций.
Задача о «размене». Требуется найти число способов

разменять заданную сумму n рублей монетами достоинством 1,
2 и 5 рублей.
Обозначим искомое число способов размена через Pn,

n = 0, 1, 2,… . Для малых значений n числа Pn легко
вычисляются непосредственно:

P0 = 1; P1 = 1; P2 = 2 (1 + 1, 2); P3 = 2 (1 + 1 + 1, 1 + 2);
P4 = 3 (1 + 1 + 1 + 1, 1 + 1 + 2, 2 + 2).
Составим производящую функцию последовательности Pn:

P(z) = P0 + P1z + P2z2 +… .
Рассмотрим произведение
(1 + z + z2 +…)(1 + z2 + z4 +…)(1 + z5 + z10 +…).

(17)

После раскрытия скобок и приведения подобных коэффициент
при zn окажется равным Pn. В самом деле, коэффициент при zn
в (17) – это число способов представить zn в виде произведения
степеней zu, z2v, z5w, равное числу решений в целых
неотрицательных числах уравнения

u + 2 v + 5 w = n.
Но это как раз и есть число «разменов» числа n единицами,
двойками и пятерками, т. е. число Pn. Следовательно,

P(z) = (1 + z + z2 +…)(1 + z2 + z4 +…)(1 + z5 + z10 +…) .

57
Суммируя геометрические прогрессии в скобках, получаем:

P( z ) =

1
1
1


.
1 − z 1 − z 2 1 − z5

(18)

Используя производную, можно найти явное выражение
для Pn:

P ( n) (0)
.
Pn =
n!
Впрочем,

представление

(18)

позволяет

получить

рекуррентные соотношения для вычисления чисел Pn. Вместе с

P( z ) =

1
1
1
2


=
P
+
P
z
+
P
z
+…
0
1
2
1 − z 1 − z 2 1 − z5

пусть

Q( z ) =

1
1
2

=
Q
+
Q
z
+
Q
z
+… ,
0
1
2
1− z 1− z2

R( z ) =

1
= R0 + R1z + R2z2 +… .
1− z

Тогда:
(1 – z)R(z) = 1;
(1 – z2)Q(z) = R(z);
(1 – z5)P(z) = Q(z).
Приравнивая коэффициенты при одинаковых степенях,
получаем уравнения:

R0 = 1, Rn – Rn–1 = 0 (n ≥ 1);
Qn – Qn–2 = Rn (n ≥ 2);
Pn – Pn–5 = Qn (n ≥ 5).

58
Отсюда выводятся следующие рекуррентные соотношения:

Rn = Rn–1 (n ≥ 1);

R0 = 1,

Qn = Rn (n < 2), Qn = Qn–2 + Rn (n ≥ 2);
Pn = Qn (n < 5), Pn = Pn–5 + Qn (n ≥ 5).
Последовательные вычисления можно свести в таблицу.

n

0

1

2

3

4

5

6

7

8

9

10

R

1

1

1

1

1

1

1

1

1

1

1

Q

1

1

2

2

3

3

4

4

5

5

6

P

1

1

2

2

3

4

5

6

7

8

10

Задача о «счастливых билетах». Автобусный билет с

шестизначным номером считается «счастливым», если сумма
первых трех цифр равна сумме последних трех цифр.
Например, билет 054 342 «счастливый». Требуется найти число
счастливых

билетов.

Считается,

что

допустимы

любые

шестизначные номера.
Пусть x1x2x3 y1y2y3 – номер билета. Билет счастливый, если

x1 + x2 + x3 = y1 + y2 + y3.
Заменив последние три цифры их дополнениями до 9, т. е.
полагая x4 = 9 – y1; x5 = 9 – y2; x6 = 9 – y3, предыдущее уравнение
можно переписать так:

x1 + x2 + x3 + x4 + x5 + x6 = 27.
Задача

о

счастливых

билетах

(19)
может

быть

переформулирована теперь следующим образом: требуется

59
найти число целых решений уравнения (19), удовлетворяющих
следующим условиям:
0 ≤ xi < 10, i = 1, 2,…, 6.
Рассмотрим более общую задачу. Требуется найти число
целых решений следующей системы:

x1 + x2 +…+ xk = n; 0 ≤ xi < m, i = 1, 2,…, k.

(20)

Обозначим число решений (20) через Cn(k, m) (число
счастливых билетов в этих обозначениях равно C27(6, 10)). Если
в выражении
(1 + z +…+zm–1)k
раскрыть скобки и привести подобные, то коэффициент при zn
окажется равен числу способов представить n в виде суммы k
слагаемых, которые могут принимать значения 1, 2,…, m – 1.
Но это как раз и есть число Cn(k, m). Таким образом,
(1 + z +…+zm–1)k = Σn Cn(k, m)zn.
Суммируя геометрическую прогрессию в левой части
равенства, получаем представление производящей функции
чисел Cn(k, m) в свернутом виде:
(1 – zm)k(1 – z)–k = Σn Cn(k, m)zn.
По формулам бинома Ньютона имеем:

− k 
(1 − z ) − k = ∑ (−1) s  z s ;
 s 
s

k 
(1 − z m ) k = ∑ (−1)t  z tm .
t 
t

60
После

перемножения

этих

рядов

получится

ряд

с

коэффициентами Cn(k, m). Следовательно,

Cn(k, m) =
Используя

формулу

воспользовавшись

s + t  − k  k 
   .
(

1
)

 s  t 
s + tm = n

(21),

заменяя

s

на

(21)

n – tm

и

Ckk+−1n − tm −1 = Ckn+−ntm− tm −1 ,

соотношением

получаем

Cn(k, m) =

∑ (−1) 2 s + t Cks + s −1Ckt = ∑ (−1)t Ckk+−1n −tm −1Ckt .

s + tm = n

tm ≤ n

В частности, если m = 10, n = 27, то tm ≤ n при t = 0, 1, 2.
Следовательно,
5 0
5 1
5 2
C6 –C22
C6 + C12
C6 = 55252.
C27(6, 10) = C32

61

11. Рекуррентные последовательности
11. 1. Рекуррентные соотношения

Последовательность u0, u1, u2,… называют рекуррентной,
если указана зависимость общего члена последовательности от
предыдущих и заданы значения необходимого числа начальных
членов. Саму зависимость иногда называют рекуррентностью.
Примерами

рекуррентных

последовательностей

могут

служить арифметические и геометрические прогрессии.
Члены

геометрической

прогрессии

u0, u1, u2,…

со

знаменателем q связаны рекуррентным соотношением
un+1 = qun.
Члены

произвольной

арифметической

прогрессии

u0, u1, u2,… связаны рекуррентным соотношением
un+2 = 2un+1 – un.
Последовательность

факториалов

1, 1, 2, 6, …, n!,…

определяется рекуррентным соотношением
un+1 = (n + 1)un
(при u0 = 1).
Как рекуррентость может трактоваться формула
Cnk+1 = Cnk −1 + Cnk ,
связывающая биномиальные коэффициенты.
В качестве еще одного примера рассмотрим задачу о
разбиении плоскости прямыми.

62
Пусть Dn – число областей, на которые разбивают плоскость
n прямых общего положения (таких, что никакие три из них не
пересекаются в общей точке и никакие две прямые не
параллельны). Ясно, что D0 = 1, D2 = 2. Предположим, что на
плоскости уже проведено n прямых, и посмотрим, сколько
новых областей добавляется при проведении «новой» n + 1-й
прямой (рис. 1).

1

2
n +1

Рис. 1
Каждую область, по которой проходит эта прямая, она
рассекает на две, поскольку все области выпуклы. Таким
образом, общее число областей увеличится на число областей,
через которые проходит n + 1-я прямая. Двигаясь по n + 1-й
прямой в одном направлении, мы пересечем границы областей
n раз по числу «старых» прямых. Значит, n + 1-я прямая
пройдет через n + 1 область (в последовательности область –
граница – … – область – граница – область число областей на
единицу больше, чем число границ).
В результате получаем рекуррентное соотношение
Dn+1 = Dn + (n + 1).

63
Чтобы

найти

замкнутое

выражение

для

членов

последовательности Dn, просуммируем следующие равенства:
D1 = D0 + 1;
D2 = D1 + 2;
………………
Dn = Dn–1 + n .
После сокращений получаем
Dn = D0 + 1 + 2 +…+n .
Следовательно,
Dn = 1 +

n(n + 1)
.
2

11. 2. Линейные рекуррентные соотношения

Рекуррентная последовательность u0, u1, u2,… называется
линейной, если ее члены связаны соотношением вида
un+r = a1un+r–1 + a2un+r–2 +…+ arun ,

(1)

где ai, i = 1, 2,…, r, – постоянные, не зависящие от n.
Соотношение

(1)

называется

линейным

рекуррентным

уравнением порядка r.
Например, члены геометрической прогрессии связаны
линейным рекуррентным уравнением первого порядка:
un+1 = qun.
Члены арифметической прогрессии связаны линейным
рекуррентным уравнением второго порядка:
un+2 = 2un+1 – un.

64
Члены

последовательности

факториалов

связаны

нелинейным соотношением:
un+1 = (n + 1)un.
Еще

один

важный

пример – рекуррентность,

заданная

линейным уравнением второго порядка
un+2 = un+1 + un.
Этому уравнению удовлетворяет последовательность чисел
Фибоначчи

F0,

F1,

F2,

F3,

которая

получается,

если

положить F0 =0 и F1 =1:
0, 1, 1, 2, 3, 5, 8, 13, 21, …
Числа Фибоначчи имеют много важных приложений, в том
числе в финансовом анализе. Изучению чисел Фибоначчи
посвящена следующая глава.
Последовательность
рекуррентная

сумм.

Пусть

последовательность,

u0, u1, u2,… –

удовлетворяющая

соотношению (1). Покажем, что последовательность сумм
s0 = u0,

s1 = u0 + u1,

…,

sn = u0 + u1 +…+ un, …

также удовлетворяет некоторому линейному рекуррентному
соотношению. Заметим сначала, что
un+1 = sn+1 – sn , n = 0, 1, … .
С учетом этого рекуррентное соотношение, связывающее
члены

последовательности

u0, u1, u2,…,

перепишется

следующим образом:
sn+r+1 – sn+r =
= a1(sn+r – sn+r–1) + a2(sn+r–1 – sn+r–2) + …+ ar(sn+1 – sn).

65
Отсюда
sn+r+1 =
= (1 + a1)sn+r +(a2 – a1)sn+r–1+…+( ar –ar–1)sn+1 – arsn
Таким

образом,

последовательные

суммы

(2)
связаны

рекуррентным соотношением порядка r + 1.
Примеры. 1. Для сумм членов геометрической прогрессии

имеем:
sn+2 – sn+1 = q(sn+1 – sn),
откуда
sn+2 = (1 + q)sn+1 – qsn.
2. Для сумм членов арифметической прогрессии имеем:
sn+3 – sn+2 = 2(sn+2 – sn+1) – (sn+1 – sn),
и, значит,
sn+3 = 3sn+2 – 3sn+1 + sn.
Последовательность степеней натуральных чисел. Начнем
с последовательности квадратов:
u0 = 0, u1 = 1, u2 = 4,…, un = n2, … .
Члены этой последовательности удовлетворяют следующим
соотношениям:
un+1 = un + 2n + 1;
un+2 = un+1 + 2n + 3;
un+3 = un+2 + 2n + 5.
Вычитая из второго уравнения первое, а из третьего второе,
находим:

66
un+2 – un+1 = un+1 – un + 2;
un+3 – un+2 = un+2 – un+1 + 2.
Теперь, вычитая первое из полученных уравнений из
второго, получаем рекуррентное соотношение
un+3 = 3un+2 – 3un+1 + un .
Подобно тому как это сделано для последовательности
квадратов, несложно поверить, что последовательность кубов
u0 = 0, u1 = 1, u2 = 8,…, un = n3, …
удовлетворяет соотношению
un+4 = 4un+3 – 6un+2 + 4un+1 – un.
В общем случае последовательность
u0 = 0, u1 = 1, u2 = 2r,…, un = nr, …
удовлетворяет соотношению порядка r + 1:
r +1

un+r+1 = ∑ (−1) k −1 Crk+1u n + r +1− k .

(3)

k =1

Используя
натуральных

рекуррентные
чисел,

соотношения

можно

для

получить

степеней

рекуррентные

соотношения для сумм степеней.
Например,

последовательность

квадратов

натуральных

чисел удовлетворяет соотношению
un+3 = 3un+2 – 3un+1 + un .
Следовательно,

последовательность

сумм

удовлетворяет соотношению
sn+4 = 4sn+3 – 6sn+2 + 4sn+1 – sn.

квадратов

67
11.3. Производящие функции линейных рекуррентных
последовательностей

Наша ближайшая цель – определить, какой вид имеет
производящая функция произвольной линейной рекуррентной
последовательности.
Рассмотрим в качестве примера производящую функцию
последовательности чисел Фибоначчи:
F(z) = F0 + F1z + F2z2 + … .

(4)

Умножим F(z) на z и на z2:
zF(z)

=

z2F(z)

=

F0z + F1z2 + F2z3 + … ;
F0z2 + F1z3 + F2z2 + … .

Так как F2 = F1 + F0; F3 = F2 + F1;… , то
zF(z) + z2F(z) = F0z + F2z2 + F3z3 + … .
Учитывая, что F0 = 0 и F1 =1, получаем:
z + zF(z) + z2F(z) = F(z).
Отсюда получается компактная формула:
F(z) =

z
.
1− z − z2

(5)

Используя (5), можно найти явные выражения для чисел
Фибоначчи. Начнем с того, что представим дробь из (5) в виде
z
A
B
=
.
+
1 − z − z 2 1− бz 1− в z
Тогда
A
B
= A ∑ (б z ) n ;
= B ∑ (в z ) n ,
1 − бz
1 − вz
n≥0
n≥0

(6)

68
и, значит,
z
= A ∑ (бz ) n + B ∑ (в z ) n = ∑ ( Aб n + Bв n ) z n .
2
1− z − z
n ≥0
n ≥0
n≥0
Таким образом,
Fn = Aαn + Bβn.
Чтобы найти неизвестные коэффициенты A, B, α и β,
приведем дроби из (6) к общему знаменателю и приравняем
коэффициенты при одинаковых степенях z. Получаются
следующие уравнения:
α + β = 1;

αβ = –1; A + B = 0;

Aβ +Bα = –1.

Решая полученную систему, находим:
б=

1
1
1+ 5
1− 5
;в=
;A=
;B= −
.
2
2
5
5

Окончательно получаем:
n
n
1   1 + 5   1 − 5  
 .
 −

Fn =
5   2   2  



(7)

Пусть теперь
u0, u1, u2,… –
произвольная

рекуррентная

(8)
последовательность,

удовлетворяющая соотношению
un+r = a1un+r–1 + a2un+r–2 +…+ arun ,
и
f(z) = u0 + u1z + u2z2 +… –

(9)

69
ее производящая функция. Рассмотрим произведение f(z) на
многочлен
h(z) = 1 – a1z – a2z2 –…– arzr .
Коэффициент при zn+r равен
un+r – a1un+r–1 – a2un+r–2 –…– arun ,
и, значит, обращается в ноль в силу (9). Таким образом, в
произведении h(z)f(z) все коэффициенты при степенях z,
больших или равных r, обращаются в ноль, т. е. g(z) = h(z)f(z) –
это многочлен степени не выше чем r – 1. Производящая
функция последовательности (8) оказывается равной дробнорациональной функции f ( z ) =
Примеры.

1.

Для

g ( z)
.
h( z )

геометрической

прогрессии

со

знаменателем q имеем
f(z) = u0 + u0qz + u0qz2 +…;

h(z) = 1 – qz;

h(z)f(z) = u0 ,

откуда получается хорошо известная формула:
f ( z) =

u0
.
1 − qz

2. Пусть теперь u0, u1, u2,… – арифметическая прогрессия.
Так как un+2 = 2un+1 – un , то
h(z) = 1 – 2z + z2
и
h(z)f(z) = u0 + (u1 – 2u0)z2.
Следовательно,

70

Рассмотрим,
положительных

f ( z) =

u0 + (u1 − 2u0 ) z
.
(1 − z ) 2

в

частности,

целых

чисел

(10)
последовательность

1, 2, 3, … .

Запишем

ее

производящую функцию:
f(z) = 1 + 2z + 3z2 + … .

(11)

По формуле (10) получаем:
f ( z) =

1
.
(1 − z ) 2

(12)

К тому же результату можно придти по-другому. Ряд (11)
получается как производная ряда
z + z 2 + z 3+ … ,
сумма которого (как сумма геометрической прогрессии) равна
z
.
1− z

(13)

Дифференцируя (13), получаем (12).
Наряду с многочленом h(z) рассмотрим многочлен
k(z) = zr – a1zr–1 – a2zr–2 –…– ar,
называемый характеристическим (для последовательности,
члены

которой

удовлетворяют

рекуррентному

соотношению (1)).
Многочлены h(z) и k(z) связаны простым соотношением:
h(z) = zrk(1/z).
Пусть α1, α2, …, αs – корни характеристического многочлена
(возможно, комплексные) с кратностями p1, p2, …, ps. Тогда

71
k ( z ) = ( z − б1 ) p1 ( z − б 2 ) p2 K ( z − б s ) p s ,
и, соответственно,
h( z ) = (1 − б1z ) p1 (1 − б 2 z ) p 2 K (1 − б s z ) p s .
Рациональная функция f ( z ) =

g ( z)
может быть представлена в
h( z )

виде суммы простых дробей вида
в
(1 − бz)

p

,

(14)

где α = αi – один из корней характеристического многочлена, p
лежит в промежутке от

1 до pi, а β – некоторое число.

Разлагая (14) по формуле бинома, получаем:
в
(1 − бz ) p

=

− p
в
∑  n (−1) n б n z n .
n≥0

Относительно n выражение
− p
(−1) n = (−1) n C pn + n −1 ⋅ (−1) n = C pn + n −1 = C pp+−n1 −1

 n 
является многочленом степени не выше p – 1 и, тем более, не
выше pi – 1. Следовательно, сумма всех дробей вида (14),
относящихся к одному и тому же корню α = αi, может быть
представлена в виде

∑ Pi (n)б in z n , причем степень многочлена

n ≥0

Pi(n) не превышает pi – 1. Суммируя по всем i = 1, 2, …, s,
получаем:
s

f ( z ) = ∑  ∑ Pi (n)α in z n .

n ≥ 0 i =1

72
Сравнивая полученное выражение с
f(z) = u0 + u1z + u2z2 +… ,
приходим к заключению, что
s

un = ∑ Pi (n)б in .

(15)

i =1

Пример. Рассмотрим последовательность 6, 0, 12, … ,

удовлетворяющую рекуррентному соотношению
un+3 = 3un+1 + 2un.
Многочлен
k(z) = z3 –3z – 2
является характеристическим для этой последовательности.
Раскладывая его на множители получаем:
k(z) = (z + 1)2(z – 2).
Следовательно, члены рассматриваемой последовательности
имеют вид
un = P(n)⋅(–1)n + Q⋅2n ,
где P(n) – многочлен степени не выше первой, а Q – степени не
выше нулевой (т. е. ноль или некоторое число).
Будем искать un в виде
un = (An + B)⋅(–1)n + Q⋅2n .
Поскольку

u0 = 6,

u1 = 0,

u2 = 12,

получаем

следующие

уравнения относительно A, B и Q:
B + Q = 6; –(A + B) + 2Q = 0;
Решая систему, находим:

2A + B + 4Q = 12.

73
A = 0; B = 4; Q = 2.
Следовательно,
un = (–1)n⋅4 + 2n+1.
Пример. Используя (15), найдем формулу для суммы

квадратов первых n натуральных чисел.
Суммы квадратов связаны рекуррентным соотношением
sn+4 = 4sn+3 – 6sn+2 + 4sn+1 – sn.
Характеристический

многочлен

последовательности

сумм

квадратов
k(z) = z4 – 4z3 + 6z2 – 4z +1 = (z – 1)4
имеет

единственный

корень

1

кратности

четыре.

Следовательно, sn представимо в виде
sn = An3 + Bn2 + Cn +D.
Так как
s0 = 0, s1 = 1, s2 = 5, s3 = 14,
то
D = 0;

A + B + C = 1;

8A + 4B + 2C = 5;

27A + 9B + 3C = 14.

Вычисляем определитель системы уравнений, содержащих
неизвестные A, B, C, и определители, соответствующие
переменным:
 1 1 1
 1 1 1




∆ =  8 4 2  = −12 ; ∆ A =  5 4 2  = −4 ;
 27 9 3 
14 9 3 





74
1 1 1
 1 1 1




∆ B =  8 5 2  = −6 ; ∆ С =  8 4 5  = −2 .
 27 9 14 
 27 14 3 




Находим: A = 1/3; B = 1/2; C = 1/6. Следовательно,
sn = 13 n 3 + 12 n 2 + 16 n =

n(n + 1)(2n + 1)
.
6

11. 4. Числа Каталана. Случайное блуждание

В этом параграфе мы исследуем рекуррентное соотношение,
которое встречается во многих задачах (см., например, далее
подсчет числа бинарных деревьев), в том числе в задачах
финансового анализа.
Рассмотрим биномиальную решетку цен актива. Пусть, как
и

ранее,

u > 1 – повышающий

коэффициент,

а

d<1–

понижающий. Если стоимость актива повышалась p раз и
понижалась q раз, то она станет равной S0updq.
Сопоставим каждому пути на решетке, последовательность
вида
(a1, a2, …, am),

(16)

состоящую из –1 и 1, в которой –1 соответствует понижению
стоимости, а 1 – повышению. Пусть a = a1 + a2 +…+ am. Число a
показывает на сколько число повышений больше числа
понижений. Число «минус единиц» q в последовательности (16)
равно (n – a)/2, число «единиц» p равно (n + a)/2. Стоимость
актива с последовательностью повышений-понижений (16) к
моменту m равна

75
S0updq = S0u(n+a)/2d(n–a)/2.
Предположим, что p + q = 2n – четное число. Наибольшее
число путей C2nn ведет в узел S0undn. На этих путях число
понижений равно числу повышений. Если считать, что ud = 1,
то стоимость актива в результате развития событий по пути,
приводящему в узел S0undn, остается неизменной: S0undn = S0.
Мы займемся подсчетом числа путей, на которых стоимость
актива ни разу не опускается ниже S0. Иными словами, нас
интересует число последовательностей
(a1, a2, …, a2n),

(17)

для которых сумма всех элементов равна нулю:
a1 + a2 +…+ a2n = 0,
а все частичные суммы неотрицательны:
s1 = a1 ≥ 0,

s2 = a1 + a2 ≥ 0,

…,

s2n–1 = a1 + a2 +…+ a2n–1 ≥ 0.
Про такие последовательности будем говорить, что они
сбалансированы. Графически последовательность вида (17)
может быть представлена диаграммой частичных сумм. На
рис. 2 представлены две сбалансированные последовательности
длины 4 (при n = 2); на рис. 3 – пять сбалансированных
последовательностей длины 6 (при n = 3). Сбалансированность
означает, что диаграмма не опускается ниже нулевого уровня.

76

Рис. 2

Рис. 3
Обозначим через Cn – число различных сбалансированных
последовательностей длины 2n. Ясно, что C0 = 1 (имеется ровно
одна пустая последовательность) и С1 = 1. Мы видели также,
что С2 = 2 и С3 = 5.
При n > 0 всякая сбалансированная последовательность
начинается с единицы и заканчивается минус единицей:

77
a1 = 1, a2n = –1.
Если

все

частичные

суммы

сбалансированной

последовательности (17) положительны, то последовательность
(a2, …, a2n–1), имеющая длину 2n – 2, также оказывается
сбалансированной.

Обратно,

последовательность

длины

любую

2n – 2

сбалансированную

можно

дополнить

до

сбалансированной последовательности длины 2n, приписав к
ней слева единицу, а справа – минус единицу. Тем самым
между множеством сбалансированных последовательностей
длины

2n

с

множеством
длины

положительными
всех

2n – 2

соответствие.

частичными

сбалансированных
устанавливается

Следовательно,

суммами

и

последовательностей

взаимно
число

однозначное

сбалансированных

последовательностей длины 2n с положительными частичными
суммами

равно

Cn–1 – общему

числу

сбалансированных

произвольную

сбалансированную

последовательностей длины 2n – 2.
Рассмотрим

теперь

последовательность (17), имеющую нулевые частичные суммы.
Пусть 2k < 2n – номер последней частичной суммы, равной
нулю.

Последовательность

(17)

можно

разбить

на

две

сбалансированные последовательности
(a1, a2, …, a2k), (a2k+1, a2, …, a2n),

(18)

длины которых суть 2k и 2n, при этом частичные суммы второй
последовательности

положительны.

Обратно,

имея

две

сбалансированные последовательности (18) длин 2k и 2n,

78
можно составить из них сбалансированную последовательность
(17) длины n. Если вторая из последовательностей (18) имеет
положительные частичные суммы, то последней нулевой
частичной суммой последовательности (17) окажется частичная
сумма с номером 2k. По правилу произведения число
последовательностей (17), для которых последняя нулевая
частичная сумма имеет номер 2k, составляет Ck ⋅ Cn–k–1.
Таким образом, суммируя по всем k < n и учитывая, что
C0 = 1, приходим к равенству
Cn = C0Cn–1 + C1Cn–2 + … + Cn–1C0.

(19)

В частности,
C1 = C02 = 1; C2 = C0C1 + C1C0 = 2;
C3 = C0C2 + C1C1+ C2C0 = 5; … .
Составим производящую функцию:
C(z) = C0 + C1z + C2z2 + … .
Используя (19), получаем:
C(z)2 = C02 + (C0C1 + C1C0)z + (C0C2 + C1C1+ C2C0)z2 … =
= C1 + C2z + C3z2 + … .
Умножая обе части последнего равенства на z и добавляя 1,
приходим к соотношению
z⋅C(z)2 +1 = C(z).
Таким образом, y = C(z) удовлетворяет квадратному уравнению
z⋅y2 – y +1 = 0.
Решая его, находим:

79
y=

(

1
1 ± 1 − 4z
2z

)

Для функции y = C(z) должно выполняться соотношение
lim C ( z ) = 1 . Для

z →0

y=

(

1
1 + 1 − 4z
2z

)

предел при z→0 не

существует. Следовательно,
C( z) =

(

)

1
1 − 1 − 4z .
2z

Воспользовавшись биномом Ньютона, находим:
C ( z) =


1 / 2 
1 / 2  2k −1 k −1
1 
1 − ∑ 
(−4 z ) k  = ∑ (−1) k −1
 ⋅ 2
z ,
k
2 z  k ≥0  k 


 k ≥1

т.е.
C ( z) =

k  1 / 2  2 n +1 n
(
1
)
 ⋅ 2
z .



n
1
+


n≥0

Таким образом,
 1 / 2  2 n +1
 ⋅ 2
Cn = (−1) k 
.
1
n
+


Несложно проверить, что
 1 / 2  2 n +1
1  2n 
(−1) k 
 ⋅ 2
=
  .
1
+
n
+
n
1


n
Окончательно получаем:
Cn =

1  2n 
 .
n + 1  n 

(20)

Числа Cn называются числами Каталана. Числа Каталана
часто встречаются при решении задач перечисления (см. далее
перечисление бинарных деревьев).

80
Формула (20) позволяет установить и некоторые другие
факты о числе путей.
Для начала напомним, что при выводе (20) мы пришли к
заключению, что число сбалансированных последовательностей
длины 2n с положительными частичными суммами равно Cn–1.
Любая

последовательность

(17)

с

положительными

частичными суммами после умножения на –1 превращается в
последовательность с отрицательными частичными суммами и
обратно. Следовательно, число последовательностей (17) с
отрицательными частичными суммами и нулевой суммой s2n
столько же, сколько и сбалансированных последовательностей
с положительными частичными суммами, т. е. Cn–1. Таким
образом, число последовательностей (17), для которых s2n = 0 и
ни одна частичная сумма не обращается в ноль, равно 2Cn–1.
Если

пути

на

биномиальной

решетке

соответствует

последовательность (17) такая, что s2n = 0, а все частичные
суммы отличны от нуля, говорят , что первое возвращение в
ноль происходит в момент 2n.
Сумма
t

∑ 2Ck −1 = 2C0 + 2C1 +…+ 2Ct–1

k =1

дает число путей, на которых первое возвращение в ноль
происходит в один из моментов 2, 4, …, 2t. Соответственно
2t

2 –

t

∑ 2Ck −1

k =1



81
это число путей длины 2t, для которых возвращения в ноль до
момента 2t (включая его) не происходит. Из них половина
путей расположена выше нулевого уровня, а половина – ниже.
Следовательно,

количество

путей,

для

которых

число

повышений превосходит число понижений в любой момент
времени от 1 до 2t, равно
2

2t–1



t

∑ Ck −1 .

k =1

Анализ (как правило, довольно сложный) подобного рода
величин позволяет оценить вероятность того или иного
варианта развития событий, связанных с изменением цены
актива.

82

12. Числа Фибоначчи
12. 1. Простейшие свойства

Напомним,

что

числа

Фибоначчи

образуют

последовательность, в которой первые два члена равны 0 и 1, а
каждый следующий равен сумме двух предыдущих. В
соответствии

с

определением

последовательность

чисел

Фибоначчи
F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8,…
удовлетворяет рекуррентному соотношению
Fn+2 = Fn+1 + Fn.

(1)

Числа Фибоначчи возникают естественным образом во
многих задачах. Исторически одной из первых является задача
о кроликах, восходящая к Леонардо Пизанскому, которого
иногда называют Леонардо Фибоначчи (публикация 1202 г.). В
этой задаче требуется определить число пар зрелых кроликов,
образовавшихся от одной пары в течение года, если известно,
что каждая зрелая пара кроликов ежемесячно рождает новую
пару, причем новорожденные кролики достигают зрелости
через два месяца.
Обозначим через un, un+1, un+2 число пар зрелых кроликов
соответственно через n месяцев, через n + 1 месяц и через n + 2
месяца. Нетрудно убедиться, что un+2 = un+1 + un: к моменту n + 2
зрелости достигают un пар кроликов, родившихся в момент n,

83
которые добавляются к un+1 паре кроликов, зрелых на
момент n + 1.
Рассмотрим еще одну задачу, так называемую задачу о
прыгуне. Некоторая величина x увеличивается за единицу
времени на 1 или на 2. Требуется определить, сколькими
способами может произойти увеличение рассматриваемой
величины на n единиц. Обозначим искомое число способов
через un. Пусть x(t) – значение величины x в момент времени t.
Ясно, что x(1) = x(0) + 1 или x(1) = x(0) + 2 в зависимости от
того, на 1 или на 2 изменилась величина x за первый временной
промежуток. Имеются два пути достичь значения x(0) + n:
вырасти на n – 1 единицу со значения x(0) + 1 или на n – 2
единицы со значения x(0) + 2. Первое может произойти un–1
способами, второе – un–2 способами. Следовательно,
un = un–1 + un–2.
Многие свойства чисел Фибоначчи нетрудно получить по
индукции. Например, для любого n ≥ 0 справедливо равенство
1 1 


1
0



n +1

F
=  n + 2
 Fn +1

Fn +1 
.
Fn 

(2)

В самом деле, (2) выполняется при n = 0. Следующая
выкладка позволяет сделать индуктивный шаг:
1 1 


1
0



n+2

F
=  n + 2
 Fn +1

Fn +1 1 1 

=
Fn 1 0 

84
 F + Fn +1
=  n + 2
 Fn +1 + Fn

Fn + 2   Fn + 3
=
Fn +1   Fn + 2

Fn + 2 
.
Fn +1 

Если взять определители матриц, стоящих в правой и левой
частях (2), получится следующее соотношение:
Fn+2Fn – Fn2+1 = (–1)n+1.
Приведем одно из важных свойств чисел Фибоначчи,
доказательство которого значительно сложнее и здесь не
приводится.
Каждое целое положительное число имеет единственное
представление вида
n = Fk1 + Fk 2 + K + Fk r ,

(3)

где k1 ≥ k2 +2; k2 ≥ k3 +2; …, kr–1 ≥ kr +2; kr ≥ 2.
Чтобы получить представление (3) нужно в качестве Fk1
взять наибольшее число Фибоначчи, не превосходящее n, в
качестве

Fk 2



наибольшее

число

Фибоначчи,

не

превосходящее n − Fk1 , и т. д., пока очередной «остаток» не
станет равным нулю. Например:
1 = F1; 2 = F2; 3 = F3;4 = F3 + F1; 5 = F4; 8 = F5; 13 = F6;
20 = F6 + F4 + F2.
12.2. Формула Бине и некоторые ее применения

Напомним (см. 11.3, формула (5)), что производящая
функция для последовательности чисел Фибоначчи имеет вид

85
z
.
1− z − z2

F(z) = F0 + F1z + F2z2 + … =

Корнями характеристического многочлена
k(z) = z2 – z –1
являются числа
б=
Число

1+ 5
1− 5
ив=
.
2
2

Фибоначчи

как

функция

своего

номера

представляется в виде:
бn − вn
Fn =
,
5

(4)

или
n

Fn =

 1+ 5   1− 5 

 − 

 2   2 
5

n

,

Формула (4) называется формулой Бине.
Так как α2 = α + 1, то любую степень числа α можно
представить

в

виде

целочисленной

комбинации

aα + b.

Оказывается, коэффициентами служат числа Фибоначчи:

αk+2 = Fk+2α + Fk+1.
Формула Бине позволяет убедиться в этом прямой проверкой.
Приведем несколько оценок чисел Фибоначчи.
бn
Число Фибоначчи Fn есть ближайшее целое к числу
.
5

86
Для доказательства заметим, что |β| < 1, и, значит, |βn| < 1.
Следовательно,
n

в
бn
бn − в n бn
1
Fn −
=

=
< .
5
5
5
5 2

(5)

Из (4) вытекает также следующее свойство.

С ростом n числа Фибоначчи неограниченно сближаются с
членами геометрической прогрессии с начальным членом
знаменателем α =

1
и
5

5 +1
:
2

б n 

lim Fn −
 = 0.
n → ∞
5



Отношение соседних чисел Фибоначчи (следующего к
предыдущему) с ростом n стремится к числу

2
≈ 0,618 .
5 +1

Действительно,
Fn
бn − в n
1 − (в / б ) n
.
=
=
Fn +1 б n +1 − в n +1 б − в (в / б ) n
Так как β/α < 1, то (β/α)n с ростом n стремится к нулю.
Следовательно,
1
Fn
= ≈ 0,618 .
n → ∞ Fn +1
б
lim

87
Из предыдущего равенства следует, что
1
Fn
= 2 ≈ 0,382 .
n → ∞ Fn + 2
б
lim

Установим

справедливость

формулы,

которая

дает

представление чисел Фибоначчи в виде суммы биномиальных
коэффициентов, и как ее следствие получим одно тождество
для биномиальных коэффициентов.
При любом n справедливо следующее равенство:
Fn +1 =

∑ Cnk− k .

(6)

2k ≤ n

Заметим сначала, что при четном n равенство (6) имеет вид
Fn +1 = Cn0 + Cn1 −1 + ... + Cnn// 22 ,
а при нечетном –
Fn +1 = Cn0 + C1n −1 + ... + C((nn+−11)) // 22 .
Например:
F5 = C40 + C31 + C22 ; F6 = C50 + C41 + C32 .
Для

доказательства

(6)

воспользуемся

производящей

функцией последовательности чисел Фибоначчи:
F(z) = F0 + F1z + F2z2 +… =
Используя

формулу

для

суммы

z
1− z − z2
членов

.

(7)
бесконечно

убывающей геометрической прогрессии, преобразуем правую
часть равенства (7):

88
z
1− z − z

2

= z⋅

1
2

1− (z + z )

= z(1 + (z + z2) + (z + z2)2 +…) =

= z + z2(1 + z) + z3(1 + z)2 +… .

(8)

Коэффициент при zn+1, получающийся после раскрытия скобок
и приведения подобных в (8), должен в соответствии с (7)
равняться Fn+1. Слагаемые в (8), следующие за zn+1(1 + z)n,
содержат z в степенях более высоких, чем n + 1. Слагаемые
zk+1(1 + z)k при 2k + 1 < n + 1 содержат z в степенях более
низких, чем n + 1. Так как
zp+1(1 + z)p = z p +1

∑ C kp z k = ∑ C kp z k + p +1 ,

k≤ p

k≤ p

то коэффициент при zn+1 получается суммированием по p всех
таких

коэффициентов

C kp ,

что

k + p +1 = n + 1

и

k ≤ p.

Последние условия означают, что p = n – k и 2k ≤ n. Таким
образом, мы суммируем коэффициенты

Cnk− k , 2k ≤ n, и

получаем сумму, стоящую в правой части (6), что и доказывает
это равенство.
С учетом формулы Бине равенство (7) может быть записано
следующим образом:
1   1 + 5 
k

∑ Cn − k =  
2
5 
2k ≤ n



n +1

1 − 5 

− 
2



n +1 

.



12. 3. Золотое сечение

Разделим отрезок AB на части так, чтобы большая часть
была бы средним пропорциональным между всем отрезком и

89
меньшей его частью. Иными словами, мы ищем точку C такую,
что AC:BC = BC:AB (рис. 1).

C

A

D

B

Рис. 1
Пусть

BC = x⋅AB.

AC = x⋅BC = x2⋅AB.

Тогда

Так

как

AC + BC = AB, то
x2 + x = 1.

(9)

Уравнение (9) имеет два решения:
−1 + 5
≈ 0,618
2

и

−1− 5
≈ −1,618 .
2

Точка C соответствует положительному решению
x=

− 1+ 5
.
2

Разбиение отрезка AB на две части точкой C называют
золотым сечением этого отрезка.
Точно так же можно получить золотое сечение отрезка AB
точкой D такой, что BD:AD = AD:AB.
Оказывается, точка D дает золотое сечение отрезка BC.
Действительно:
BC = x⋅AB, AD = x⋅AB, BD = (1 – x)⋅AB,
и, значит, CD = BC – BD = (2x – 1)⋅AB. Таким образом,
CD 2 x − 1 BD 1 − x
;
=
=
.
BD 1 − x BC
x

90
Так как x служит корнем уравнения x2 + x – 1 = 0, то, как
легко проверить,

2x − 1 1 − x
. Следовательно,
=
1− x
x
CD BD
=
.
BD BC

Заметим, что x =

−1+ 5
2

– это предел, к которому стремится

отношение соседних чисел Фибоначчи Fn/Fn+1. Приближение
золотого сечения, изображенного на рис. 1, можно получить,
взяв точки C′ и D′ такие, что

F
F 
F
AC ′ = 1 − n +1  AB = n AB ; AD′ = n +1 AB .
Fn + 2
Fn + 2
 Fn + 2 
К «золотому» пределу
un/un+1

стремится

для

−1+ 5
2

= б1 , где б = 1+2 5 , отношение

любой

последовательности

с

положительными членами, удовлетворяющей рекуррентному
соотношению un+2 = un+1 + un. В самом деле, члены любой такой
последовательности имеют вид
un = aαn + bβn,
где б = 1+2 5 и в = 1−2 5 – корни характеристического уравнения
x2 – x – 1 = 0. Поскольку все члены последовательности (un)
положительны, a ≠ 0. Так как |β/α| < 1, то (β/α)n →0 при n→∝.
Следовательно,
n

n

un
aб + bв
= n +1
=
un +1 aб + bв n +1 б +

( ) → 1 при n→∝.
( )в б

в n
б
n
b в
a б

1 + ba

91
Таким образом, аппроксимировать золотое сечение можно с
помощью любой положительной последовательности (un),
члены которой удовлетворяют рекуррентному соотношению

un+2 = un+1 + un.
Золотое сечение используется в техническом анализе при
торговли ценными бумагами на инвестиционных рынках.
Центральную роль в так называемом анализе Фибоначчи
играют Фиб-узлы (или уровни Ди Наполи). На ценовой волне
берутся две крайние точки A и B и отрезок AB делится точками

C и D (рис. 2) подобно тому, как это сделано на рис. 1.
Полученные точки называются Фиб-узлами. Считается, что в
этих

точках

происходит

значительное

сопротивление

изменению цен при обратном движении.
B
D (F3)

0.618

C (F5)

0.382

A

Рис. 2
В качестве Фиб-узлов используются также близкие к ним
точки – F3 и F5 – Фиб-узлы, расположенные на уровнях 3/8
и 5/8:

F 3 = A + F4 (B − A) ; F 5 = A + F5 (B − A) .
F

6

F

6

92
Некоторое

теоретическое

обоснованному

выбору

объяснение

Фиб-узлов

дается

эмпирически
в

следующем

параграфе.
12. 4. Числа Фибоначчи и поиск экстремума

Рассмотрим следующую задачу. Имеются две величины x
и y, связанные функциональной зависимостью. Известно, что
когда x пробегает промежуток [a, b], величина y сначала
убывает, затем возрастает и в некоторой точке принимает свое
наименьшее значение. Более формально: на промежутке [a, ξ]
величина y убывает, на промежутке [ξ, b] возрастает, а в точке ξ
принимает наименьшее значение. При этом не исключается, что

a = ξ (величина y возрастает на всем промежутке) или ξ = b
(величина y убывает на всем промежутке). Требуется указать
оптимальный

алгоритм

определения

минимума,

т.

е.

приближенного нахождения точки минимума и значения
функции в этой точке при условии, что разрешается произвести

n наблюдений: можно произвольным образом выбрать n точек
x1, x2, …, xn на промежутке [a, b] и получить соответствующие
им значения y1, y2, …, yn.
Уточним понятие оптимальности. Пусть Ω – некоторый
алгоритм

определения

точки

минимума.

Параметрами,

определяющими его работу, служат величины n, a, b. Алгоритм


может

быть

применен

к

любой

функции

y = f(x),

определенной на промежутке [a, b], которая убывает на [a, ξ] и

93
возрастает на [ξ, b], где ξ – некоторая (неизвестная) точка из
[a, b]. Будем для краткости называть такие функции функциями

с одним минимумом (рис. 3).

ξ

a

b

Рис. 3
Множество

всех

функций

с

одним

минимумом

на

промежутке [a, b] обозначим через V(a, b) (или просто V, если
из контекста ясно, о каком промежутке идет речь). Результатом
применения алгоритма Ω к функции f ∈ V является некоторая
пара чисел (ω, η) такая, что ω ∈ [a, b] – приближенное значение
точки минимума, а η = f(ω). Мы будем писать ω = Ω(f; n, a, b)
или просто ω = Ω(f), когда ясно, каковы значения параметров

n, a, b. Качество алгоритма будем оценивать абсолютной
величиной погрешности определения точки минимума в
наихудшем случае:
τ(Ω) = sup {|ω – ξ| : f ∈ V}.
Будем считать алгоритм Ω оптимальным, если он дает
наименьшую ошибку, т. е. τ(Ω) ≤ τ(Ω′) для любого алгоритма
определения минимума Ω′.

94
Таким образом, если положить

ф0 = min sup щ − о ,


f

то τ0 = τ(Ω′) для оптимального алгоритма Ω.
Вообще говоря, значение τ0 зависит от числа допустимых
наблюдений n и промежутка [a, b]. Легко понять, что при
фиксированном числе наблюдений существенным является не
сам отрезок [a, b], а его длина l = b – a, так что τ0 = τ0(n, l).
Далее, относительно переменной l функция τ0 = τ0(n, l) является
однородной первой степени: τ0(n, λl) = λτ0(n, l) для λ > 0
(оптимальность алгоритма не зависит от выбора единицы
измерения длины). В оставшейся части параграфа будет
установлено, что
τ0(n, l) =

l
Fn + 2

,

где Fn+2 – число Фибоначчи. При этом в оптимальном
алгоритме в качестве первых точек наблюдения берутся
«фибоначчиевы узлы»:

c = a + F n (b − a ) ; d = a + Fn+1 (b − a ) .
F

n +2

F

n+2

Начнем с анализа алгоритмов поиска минимума при малом
числе наблюдений.
1. При n = 0 алгоритма поиска минимума не существует:
чтобы указать (пусть и произвольным образом) точку и
значение функции в ней, нужно произвести хотя бы одно

95
наблюдение – вычисление значения функции в этой точке.
При n = 1 оптимальный алгоритм состоит в том, чтобы в
ω

качестве

указать

середину

отрезка

[a, b].

В

этом

случае |ω – ξ| ≤ l/2, где бы ни располагалась точка минимума ξ.
При этом одно наблюдение не дает никакой информации о
расположении точки минимума. В частности, возможно ξ = a
или ξ = b. Какова бы ни была точка ω, имеем |ω – ξ| ≥ l/2 для
функции с минимумом в точке a, или |ω – ξ| ≥ l/2 для функции с
минимумом в точке b. Значит,
sup {|ω – ξ| : f ∈ V} ≥ l/2.
Таким образом,

τ0(1, l) = l/2.
2.

Рассмотрим

наблюдения, n = 2.

случай,
Пусть

x1

когда

допустимы

x2 – точки,

и

в

два

которых

производились наблюдения, а y1, y2 – значения функции в
точках x1 и x2 соответственно. Для определенности будем
считать, что x1 <x2. Если y1 ≤ y2, то можно утверждать, что точка
минимума расположена на отрезке [a, x2] (рис. 4).

a

x1

ξ

x2

b

a

Рис. 4

ξ

x1

x2

b

96
Так как лимит наблюдений (вычислений значения функции)
исчерпан, лучшим претендентом на роль точки минимума в
этом случае служит x1. Наибольшее отклонение τ1

от

настоящей точки минимума получится в том случае, когда
минимум достигается в концевой точке отрезка [a, x2], наиболее
удаленной от x1, то есть
τ1 = max {x1 –a, x2 – x1 }.
Аналогично при y2 ≤ y1 лучшим претендентом на роль точки
минимума

служит x2. Отклонение от настоящей

точки

минимума в «наихудшем» случае составляет
τ2 = max {b – x2, x2 – x1 }.
Положим
τ = max {τ1, τ2 } = max {x1 –a, b – x2, x2 – x1 }.
Так как
(x1 –a) + (b – x2) + (x2 – x1) = b – a,
то τ принимает наименьшее значение τ0 в случае, когда

x1 –a = b – x2 = x2 – x1 = (b – a)/3,
и при этом τ0 = (b – a)/3. Следовательно,
τ0(2, l) = l/3.
3. Случай трех наблюдений, n = 3, особенно поучителен.
Покажем, что в этом случае τ0 = l/5, а в оптимальном алгоритме
две точки наблюдения суть

x10 = 35 a + 52 b , x20 = 52 a + 53 b ,
а третья точка определяется как

97

x30 = 54 a + 15 b
при f(x10) ≤ f(x20), и

x30 = 15 a + 54 b
при f(x10) > f(x20).
Если f(x30) ≤ f(x10) ≤ f(x20) (в этом случае ξ∈[a, x10]), то
полагаем ω = x30. Если f(x10) ≤ f(x20), но f(x30) > f(x10) (в этом
случае ξ∈[x30, x20]), то полагаем ω = x10.

a

x30

x10

x20

b

a

x30

x10

x20

b

Рис. 5
Погрешность в худшем случае составит x30 – a = x20–x10 = l/5
(рис. 5).
Аналогично,

если

f(x10) > f(x20),

полагаем

ω = x20

при

f(x20) ≤ f(x30), или ω = x30 при f(x20) < f(x30). Здесь погрешность в
худшем случае также равна l/5.
Покажем теперь, что при ином выборе точек наблюдения
погрешность (в неблагоприятном случае) окажется больше
чем l/5.
Предположим, что произведены два наблюдения в точках x1
и x2, для определенности пусть x1 <x2. Если f(x1) ≤ f(x2), то

98
можно утверждать, что точка минимума расположена на
отрезке [a, x2]. Погрешность, с которой можно, произведя два
наблюдения, найти точку минимума на отрезке длины x2 – a,
оценивается величиной
τ0(2, x2 – a) =

Если

x2 − a
x − a 1 x2 − a
ф0 (2, l ) = 2
⋅ =
.
l
l
3
3l

x2 > x20 = 52 a + 35 b , то τ0(2, x2 – a) > (b – a)/5 = l/5.

Аналогично можно показать, что и при x2 < x20 погрешность
определения точки минимума в худшем случае превосходит l/5.
Таким образом, если x2 ≠ x20, погрешность в определении
минимума превосходит l/5. Точно так же доказывается, что и
при

x1 ≠ x10

погрешность

в

определении

минимума

превосходит l/5.
Тем самым описанный в начале этого пункта алгоритм
оказывается оптимальным алгоритмом определения минимума
при трех наблюдениях, и
τ0(3, l) = l/5.

Приведем

теперь

общее

рекурсивное

описание

оптимального алгоритма поиска минимума.
Обозначим

описанные

выше

оптимальные

алгоритмы

поиска минимума при одном, двух или трех допустимых
наблюдениях через Φ1, Φ2, Φ3 соответственно. Мы дадим
рекурсивное

описание

последовательности

алгоритмов

Φ1, Φ2, Φ3, …, в которой Φk – алгоритм поиска минимума при k

допустимых наблюдениях. Параметрами алгоритма Φk служат

99
концы отрезка [a, b], на котором ищется минимум, аргументом
– функция y = f(x), определенная на отрезке [a, b]. Результатом
работы алгоритма является пара чисел ω и η = f(ω).
Предположим, что уже имеются описания алгоритмов Φ1,
Φ2, …, Φn. При этом алгоритмы удовлетворяют следующим

требованиям:
1) при исполнении алгоритма Φk значения функции f
вычисляются k раз;
2) если k ≥ 2, первые два вычисления производятся в точках
Fk +1
Fk + 2

F

a + F k b,
k +2

Fk
Fk + 2

F

a + Fk +1 b ;
k +2

3) погрешность определения точки минимума в худшем
случае составляет εk(l) = l/Fk+2, где l = b – a – длина
отрезка;
4) алгоритм Φk является оптимальным алгоритмом поиска
минимума с числом наблюдений, не превосходящим k.
Дадим теперь описание алгоритма Φn+1. Положим

x1 =

Fn+ 2
Fn+3

F

a + Fn+1 b , x2 =
n+3

Fn +1
Fn +3

a+

Fn+ 2
Fn+3

b.

Вычисляем f(x1) и f(x2). Пусть сначала f(x1) ≤ f(x2).
Применим алгоритм Φn для поиска минимума на отрезке
[a, x2]. Пусть ω и η = f(ω) – результат этого применения.
Примем пару чисел ω и η = f(ω) в качестве результата
применения алгоритма Φn+1 к отрезку [a, b]. При исполнении

100
алгоритма Φn применительно к отрезку [a, x2] первые два
вычисления должны производиться в точках
Fn +1
Fn + 2

F

a + F n x2 ,
n+ 2

Fn
Fn + 2

F

a + Fn+1 x2 .
n+ 2

Используя тождество

Fn Fn + 3 + Fn2+1 = ( Fn + 2 − Fn +1 )( Fn + 2 + Fn +1 ) + Fn2+1 = Fn2+ 2 ,
получаем
Fn
Fn + 2

F

a + Fn+1 x2 =
n+ 2

Fn
Fn + 2

=

Fn Fn +3 + Fn2+1
Fn+ 2 Fn +3

=

Fn + 2
Fn +3

F

a + Fn+1

n+2

a+

(

Fn+1
Fn+3

Fn+1 Fn+ 2
Fn + 2 Fn +3

Fn+ 2
Fn+3

a+

b=

)

b =

Fn2+ 2
Fn + 2 Fn +3

F

a + Fn+1

n+2

Fn+ 2
Fn+3

b=

F

a + Fn+1 b = x1 ,
n +3

так что одно из двух вычислений уже выполнено, и для
последующего исполнения алгоритма Φn потребуется n – 1
вычисление. В общей сложности (с учетом вычислений f(x1)
и f(x2)) выполнено n + 1 вычисление значений функции f. Таким
образом,

Φn+1

алгоритм

удовлетворяет

первым

двум

требованиям, предшествующим его описанию. Оценим теперь
возникающую погрешность ε = εn(x2 – a) . Так как

x2 – a =

Fn +1
Fn +3

=

a+

Fn+ 2
Fn +3

− Fn + 2
Fn + 3

b−a=

a+

Fn + 2
Fn + 3

Fn +1 − Fn+3
Fn +3

a+

Fn+ 2
Fn +3

b=

F

b = Fn+2 (b − a ) ,
n +3

то
ε = εn(x2 – a) = (x2 – a)/Fn+2 = (b – a)/Fn+3.

Следовательно, третье условие для Φn+1 также выполняется.

101
Пусть теперь f(x1) > f(x2). Применим алгоритм Φn для поиска
минимума на отрезке [x1, b]. Пусть ω и η = f(ω) – результат
этого применения. Примем пару чисел ω и η = f(ω) в качестве
результата применения алгоритма Φn+1 к отрезку [a, b]. Так же,
как и в предыдущем случае, имеем:
Fn +1
Fn
x
+
1
Fn + 2
Fn+ 2

=

Fn +1
Fn +3

F
= Fn+1
n +3

(

Fn +1 Fn+ 2
Fn + 2 Fn +3

Fn2+1 + Fn+3 Fn
Fn+ 2 Fn+3

a+
a+

b=

Fn2+ 2
Fn + 2 Fn +3

F

)

F

a + Fn+1 b + F n b =
n +3

n+2

b=

Fn +1
Fn +3

a+

Fn2+1 + ( Fn + 2 + Fn+1 )( Fn + 2 − Fn+1 )
b
Fn+ 2 Fn+3

Fn +1
Fn +3

a+

Fn + 2
Fn +3

b = x2 ,

b=

=

так что для исполнения алгоритма Φn потребуется n – 1
вычисление. Как и в предыдущем случае, алгоритм Φn+1
удовлетворяет

обоим требованиям, предшествующим

его

описанию. Третье требование тоже выполняется. Так как

b –x1 = b –

Fn + 2
Fn +3

F

F

a − Fn+1 b = − Fn+2 a +
n+3

F

− Fn+2 a +
n +3

n +3

Fn+ 2
Fn+3

Fn+3 − Fn +1
Fn +3

b=

F

b = Fn+2 (b − a ) ,
n +3

то
ε = εn(b –x1) = (b –x1 )/Fn+2 = (b – a)/Fn+3.

Осталось доказать, что алгоритм Φn+1 является оптимальным
при условии, что используется не более n + 1 наблюдения.
Пусть t1 и t2, t1 < t2, – точки первых двух наблюдений. Если

f(t1) ≤ f(t2), точку минимума нужно искать на отрезке [a, t2], в
противном случае – на отрезке [t1, b]. Поскольку минимум

102
может оказаться в одной из концевых точек этих отрезков,
сузить область поиска нельзя. Предположим, что

t1 <

Fn+ 2
Fn+3

F

a + Fn+1 b .
n +3

При f(t1) > f(t2) требуется найти точку минимума на
отрезке [t1, b], произведя не более n – 1 наблюдения. Можно,
правда воспользоваться тем, что значение в точке t2 ∈ [t1, b] уже
вычислено. По индуктивному предположению оптимальным
алгоритмом
служит Φn.

определения
Если

точка

минимума

t2

выбрана

за

n

в

соответствии

наблюдений
с

алгоритмом Φn, то применение этого алгоритма обеспечит
погрешность
ε = εn(b – t1) = (b – t1)/Fn+2.

Применение

любого

другого

алгоритма

даст

большую

погрешность. Если

t1 <

Fn+ 2
Fn+3

F

a + Fn+1 b ,
n +3

то
F

b – t1 > Fn+2 (b − a )
n +3

и, значит,
ε > (b – a)/Fn+3.

Следовательно, в оптимальном алгоритме должно быть

t1 ≥

Fn+ 2
Fn+3

F

a + Fn+1 b .
n +3

103
Если точка минимума ξ находится на отрезке [a, t1], то на ее
поиск остается n – 1 наблюдение (знание f(t1) не дает в этом
случае никакой дополнительной информации о расположении
точки

минимума).

По

индуктивному

предположению

оптимальным алгоритмом определения минимума за n – 1
наблюдение

Φn–1.

является

Этот

алгоритм

обеспечивает

определение минимума с погрешностью
ε = εn–1(t1 – a) = (t1 – a)/Fn+1.

Если

t1 >

Fn+ 2
Fn+3

F

a + Fn+1 b ,
n +3

то

t1 – a >

Fn +1
Fn +3

(b − a ) .

Значит, и в этом случае
ε > (b – a)/Fn+3.

Следовательно, в оптимальном алгоритме

t1 =

Fn+ 2
Fn+3

F

a + Fn+1 b .
n +3

По симметрии в оптимальном алгоритме должно также
выполняться и равенство

t2 =

Fn+1
Fn +3

a+

Fn+ 2
Fn+3

b.

Но справедливость последних двух равенств и означает, что
алгоритм Φn+1 является оптимальным.

104

13. Графы. Основные понятия
13. 1. Понятие графа

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

информации

символов)

является

не



виде

естественным

последовательности
с

точки

зрения

человеческого восприятия. Использование нелинейных форм во
многих

случаях

существенно

облегчает

понимание.

В

математике главным средством нелинейного представления
информации служат чертежи. Один из видов чертежей – графы,
которые,

сохранив

присущую

чертежам

наглядность,

допускают точное теоретико-множественное описание и тем
самым становятся объектом математического исследования.
В разных задачах удобно использовать чертежи разных
типов. Соответственно определенные вариации допускает и
определение графа. Неотъемлемыми атрибутами графов (при
всем

разнообразии

определений)

являются

вершины

и

соединяющие их ребра или дуги.
Граф G = (V, E) состоит из конечного множества вершин
(или узлов) V и конечного множества ребер E. Каждое ребро
связывает (соединяет) пару вершин. Если ребро a соединяет
вершины x и y, то говорят, что ребро a и вершины x, y

инцидентны.

105
Например, на рис. 1
a

1
b

2

e

c

g

f

4

h

6

d

5

3

Рис. 1
изображен граф с шестью вершинами, обозначенными цифрами
1, 2, 3, 4, 5, 6, и восемью ребрами, обозначенными буквами a, b,

c, d, e, f, g, h. Ребро a связывает вершины 1 и 2; ребра e и f
связывают вершины 1 и 4; ребро g связывает вершину 2 саму с
собой; вершина 1 инцидентна ребрам a, b, e, f; ребро c
инцидентно вершинам 2 и 3.
Два ребра, связывающие одну и ту же пару вершин (как e
и f),

называют

параллельными

(или

кратными);

ребро,

связывающее вершину саму с собой (как g), называют петлей.
Иногда в определении графа запрещают наличие параллельных
ребер и/или петель, иногда нет. Мы не будем жестко
фиксировать определение, оговаривая специально, если это
оказывается существенным, какого типа граф рассматривается.
Пусть G = (V, E) – некоторый граф. Граф G′ = (V′, E′),
вершины и ребра которого являются вершинами и ребрами
графа G, т.е. V′⊂V, E′⊂E называется подграфом графа G.

106

Степенью вершины графа называется число ребер графа,
инцидентных этой вершине (петли считаются дважды). Степень
вершины v обозначается δ(v). Вершина степени 0 называется

изолированной, вершина степени 1 – висячей. Так, для графа на
рис. 1 имеем: δ(1) = δ(2) = δ(3) = 4, δ(4) = 3, δ(5) = 1, δ(6) = 0;
вершина 5 – висячая, вершина 6 – изолированная.
Несложно

убедиться

в

справедливости

следующего

соотношения:

∑ д(v) = 2m ,

v∈V

где m – число ребер графа G = (V, E). В самом деле, ребро,
соединяющее вершины x и y, вносит вклад по единице в
слагаемые : δ(x) и δ(y) (при x = y ребро является петлей и в
соответствии

с

определением

вносит

вклад

2

в

одно

слагаемое δ(x)).
В некоторых случаях рассматриваются направленные ребра,
которые называют дугами. Для дуги, соединяющей две
вершины, указывают, из какой вершины она выходит (начало
дуги), и в какую входит (конец дуги). На рисунке направление
дуги указывают стрелкой. Если все ребра графа направлены, его
называют ориентированным графом, или орграфом. В орграфе
параллельными считаются дуги, соединяющие одинаковые
вершины и имеющие одинаковое направление, то есть дуги,
имеющие общее начало и общий конец. Когда мы, имея в виду

107
ориентированный граф, говорим, что дуга a соединяет вершины

x и y, предполагается, что дуга a направлена от x к y.
На рис. 2 изображен орграф. Из вершины 1 выходят дуги a
и b, в нее входит дуга e.
a

1

2

b

c

e

3

4

d

Рис. 2

Полустепенью исхода вершины орграфа называется число
дуг графа, начинающихся в этой вершине; полустепенью захода
– число дуг графа, заканчивающихся в ней. Полустепени исхода
и захода вершины v обозначаются соответственно через δ+(v) и
δ–(v). Так, для графа на рис. 2 имеем δ+(1) = 2, δ–(1) = 1.

Для ориентированного графа G = (V, E), содержащего m дуг,
выполняется следующее соотношение:

∑ д+ (v ) = ∑ д− (v ) = m .

v∈V

Вершины

и

дуги

v∈V

графа

могут

быть

дополнительно

помечены. В этом случае говорят о нагруженном, или

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

108
13. 2. Маршруты, цепи и циклы

Последовательность вершин v0, v1, v2, …, vk графа G
представляет собой маршрут в этом графе от вершины v0 к
вершине vk, если для любого i = 0, 1, 2, …, k–1 вершины vi и vi+1
соединены дугой. В случае, когда допускаются параллельные
дуги, нужно дополнительно указать, по какой дуге из vi в vi+1
проходит маршрут. В этом случае маршрут от вершины v0 к
вершине vk, задается последовательностью вида

v0, a1, v1, a2, v2, …, vk–1, ak, vk,
где v0, v1, …, vk – последовательность вершин, a1, a2, …, ak –
последовательность дуг, причем дуга ai соединяет вершину vi–1
с вершиной vi. На самом деле, поскольку концы дуг определены
однозначно, маршрут можно представить последовательностью
дуг a1, a2, …, ak. Длиной маршрута считается число дуг,
которые он содержит. Все вершины маршрута, кроме начальной
и конечной, называют внутренними или промежуточными.
Вообще говоря, и начальная, и конечная вершины могут
встретиться на маршруте как промежуточные вершины. Для
любой вершины имеется маршрут из этой вершины в нее же, не
содержащий ни одной дуги (длины 0).
Маршрут называется цепью, если каждая дуга встречается в
нем не более одного раза, и простой цепью, если любая
вершина графа инцидентна не более, чем двум дугам маршрута.

Путем называют маршрут, в котором все вершины различны.

109
Впрочем, довольно часто «путь» используют как синоним
«маршрута».
Если начальная вершина маршрута совпадает с конечной,
его называют замкнутым. Замкнутый маршрут называется

циклом, если он является цепью; если эта цепь к тому же
простая, то и цикл называется простым. Таким образом, цикл –
это замкнутый маршрут, у которого все вершины различны,
кроме первой и последней. Например, в графе на рис.2 маршрут
1a2c3e1, или, короче, ace, является простым циклом. Поскольку
параллельных дуг на графе нет, этот цикл можно указать и по
вершинам: 1231. Ясно, что маршруты 2312 и 3123 представляют
тот же цикл. Граф, не содержащий циклов, называется

ациклическим.
Будем говорить, что вершина y достижима из вершины x,
если в графе G имеется путь из x в y.
Пусть G – произвольный орграф. Пополним его новыми
дугами. Новая дуга из вершины x в вершину y проводится в том
случае, если y достижима из x, а граф G не содержит дуги из x в

y. Обозначим пополненный граф через G^. Минимальный
подграф графа G, индуцирующий на множестве вершин то же
отношение достижимости и, соответственно, порождающий тот
же пополненный граф G^, что и граф G, обозначается через GB и
называется базисным графом для графа G. Для ациклического
графа его базисный граф определен однозначно. На рис. 3

110
представлен ациклический граф; «жирными» наконечниками
отмечены дуги, входящие в базисный граф.

Рис. 3
На

множестве

отношение

вершин

неориентированного

достижимости

эквивалентности.

Класс

является

эквивалентности

графа

G

отношением
составляют

все

вершины, которые могут быть связаны друг с другом
некоторым путем. Эти классы эквивалентности называются

компонентами

связности.

Неориентированный

граф

G

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

Рис. 4

111

13. 3. Эйлеровы цепи и циклы

Считается, что теория графов началась с задачи о

кенигсбергских мостах, поставленной и решенной Эйлером. На
рис. 5 приведена схема мостов в г. Кенигсберге времен Эйлера.
C

D

A

B

Рис. 5
На этой схеме B и C – берега реки Преголь, а A и D –
острова. Острова соединены с берегами и друг с другом семью
мостами. Требуется так составить маршрут, чтобы пройти
каждый мост ровно по одному разу и вернуться в исходную
точку. Можно построить граф задачи, в котором каждой части
города соответствует вершина, а каждому мосту – ребро
(рис. 6).
C

D
A

B

112
Рис. 6
Решение задачи о кенигсбергских мостах сводится теперь к
поиску цикла на построенном графе, в который все ребра графа
входят по одному разу. В общем случае цикл, обладающий
таким свойством, называется эйлеровым. Аналогично цепь
называется эйлеровой, если она проходит по одному разу через
каждое ребро.
Задача о кенигсбергских мостах решается с помощью
следующего несложного рассуждения. Предположим, что на
графе с рис. 6 существует эйлеров цикл. Рассмотрим
последовательность «выходов» – «заходов» для вершины из
этого цикла. Если вершина промежуточная, последовательность
имеет вид: «зашел» – «вышел» – «зашел» – «вышел» –… –
«зашел» – «вышел»; если вершина начальная: «вышел» –
«зашел» – «вышел» – «зашел» – … – «вышел» – «зашел». В
любом случае вершина должна быть инцидентна четному числу
ребер, по которым только и можно «зайти» и «выйти». Таким
образом, если на графе имеется эйлеров цикл, степени всех
вершин должны быть четными. Граф на рис. 6 этим свойством
не обладает, а значит, составит соответствующий маршрут
невозможно.
Используя аналогичное рассуждение нетрудно показать, что
если на графе существует эйлерова цепь, то на этом графе
ровно две вершины имеют нечетную степень. В самом деле, для
промежуточных вершин эйлеровой цепи последовательность

113
«выходов» – «заходов» имеет вид: «зашел» – «вышел» –… –
«зашел» – «вышел»; для начальной вершины: «вышел» –… –
«зашел» – «вышел»; для конечной: зашел» – «вышел» –… –
«зашел». Таким образом, все промежуточные вершины имеют
четные степени, а начальная и конечная – нечетные. Менее
тривиальным является обратное утверждение.
Теорема. Связный граф обладает эйлеровым циклом тогда

и только тогда, когда степени всех его вершин четны.
13. 4. Матрицы смежности и инцидентности

Любой ориентированный граф с вершинами v1, v2, …, vn и
дугами

a1,

a2,

…,

am

можно

задать

его

матрицей

инцидентности B=(bij), i = 1,2,…, n, j = 1,2,…, m, размера n×m, в
которой bij = 1, если дуга aj исходит из вершины vi; bij = –1, если
дуга aj заходит в вершину vi; bij = 0, если дуга aj не инцидентна
вершине vi.
Матрицу инцидентности можно использовать и для задания
неориентированного графа. В этом случае bij = 1, если дуга aj
инцидентна вершине vi, и bij = 0, если дуга aj не инцидентна
вершине vi. Например, граф на рис. 2 (с. 107) можно задать
следующей матрицей инцидентности (дуги упорядочены в
алфавитном порядке):

114
 1 1 0 0 − 1


 −1 0 1 0 0 
.
B =
0 0 −1 1 0 




0
1
0
1
0



Графы без параллельных дуг удобно представлять при
помощи матриц смежности. Для графа с n вершинами матрица
смежности – это квадратная матрица A=(aij) порядка n,
состоящая из нулей и единиц. Элемент aij равен 1, если имеется
дуга, соединяющая вершины i и j, и равен 0 в противном случае.
Впрочем, если в графе имеются параллельные дуги, то и тогда
можно использовать матрицу смежности: можно полагать aij
равным числу дуг, соединяющих вершины i и j.
Матрица
симметрична.

смежности
Например,

неориентированного
матрицей

представленного на рис. 7.

Рис. 7
служит матрица

смежности

графа
графа,

115
0

1
A =
1

1

1 1 1

1 1 0
1 0 1

0 1 0 

при том, что вершины занумерованы, начиная с левой верхней,
по часовой стрелке. Если изменить порядок нумерации вершин,
то изменится и матрица смежности. Например, нумеруя
вершины того же графа по часовой стрелке, начав с правой
верхней вершины, мы получим матрицу смежности
1

1
A′ = 
0

1

1 0 1

0 1 1
.
1 0 1

1 1 0

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

116
Матрица смежности
говоря,

несимметрична.

ориентированного
Например,

графа,

следующая

вообще
матрица

является матрицей смежности ориентированного графа на
рис. 2 (с. 107):
0

0
A =
1

0

1 0 1

0 1 0
.
0 0 1

0 0 0 

Теорема. Пусть G – ориентированный граф с вершинами 1,

2, …, n, и A = (aij) – его матрица смежности. Тогда элемент
aij(k) матрицы Ak равен числу путей длины k из вершины i в
вершину j.
Д о к а з а т е л ь с т в о . Докажем теорему индукцией по k. При

k = 1 имеем A1 = A, так что заключение теоремы верно,
поскольку элемент aij(1) = (aij) равен числу дуг из i в j, то есть
числу путей длины 1. Предположим теперь, что каждый
элемент aij(k) матрицы Ak = (aij(k)) равен числу путей длины k из
вершины i в вершину j и покажем, что каждый элемент aij(k+1)
матрицы Ak+1 = (aij(k+1))

равен числу путей длины k+1 из

вершины i в вершину j. Так как Ak+1 = Ak×A, то

aij(k+1) = ai1(k)⋅a1j + ai2(k)⋅a2j +…+ ain(k)⋅anj .

(1)

Слагаемое ai1(k)⋅a1j равно числу путей из i в j длины k+1, в
которых вершина 1 предпоследняя: пути длины k из вершины i
в вершину 1 комбинируются с дугами из вершины 1 в вершину

117

j. Аналогично слагаемое ai2(k)⋅a2j равно числу путей из i в j
длины k+1, в которых вершина 2 предпоследняя, и т. д. Каждый
путь из i в j длины k+1 получается из некоторого пути длины k,
начинающегося в вершине i, присоединением к нему некоторой
дуги, заканчивающейся в вершине j. Поэтому сумма в правой
части равенства (1) равна числу путей из i в j длины k+1.
Пример. Рассмотрим граф на рис. 8. Пути длины 1

представлены дугами. Все пути длины 2 и более выходят из
вершины 2. Путь длины k из вершины 2 в вершину 2
представляет собой петлю, повторенную k раз. Остальные пути
получаются

как

комбинации

путей

длины

соответствующим силом повторений петли.
1

2

3

Рис. 8
Матрица смежности:
 0 0 2


A = 1 1 1
0 0 0



1

и

2

с

118
дает число путей длины 1. Ее квадрат:
 0 0 0


A2 =  1 1 3 
 0 0 0



– число путей длины 2. Легко видеть, что Ak = A2 при k ≥ 2.
Замечание. Утверждение предыдущей теоремы можно

распространить и на случай k = 0. Для каждой вершины графа
имеется ровно один путь длины 0 из этой вершины в нее саму.
Других путей длины 0 на графе нет. Следовательно, элемент eij
единичной матрицы E = A0 равен числу путей длины 0 из
вершины i в вершину j (eij = 0 при i ≠ j, eij = 1 при i = j).
Пусть

G – ориентированный

граф

и

A – его

матрица

смежности. Рассмотрим последовательность матриц

A0, A1, A2, …, An–1.

(2)

Зафиксируем пару вершин i и j. Если существует какой-нибудь
путь из i в j, то существует и путь длины меньше n. В самом
деле, если длина пути превосходит n – 1, то такой путь
проходит через более чем n вершин, и, значит, на таком пути
хотя бы одна вершина, скажем, v, встретится более одного раза.
Отбросив часть пути, ведущую из вершины v в нее саму,
получаем более короткий путь из i в j. Повторив подобную
операцию несколько раз, можно получить путь из i в j, длина
которого не превосходит n – 1. Таким образом, если из i в j
имеется некоторый путь, то в одной из матриц (2) на месте (i,j)

119
встретится элемент, отличный от нуля. Если в матрице Ak на
месте (i,j) находится элемент, отличный от нуля, а во всех
предшествующих матрицах A0, A1, A2, …, Ak–1 на месте (i,j)
стоят нули, то k – это длина кратчайшего пути из i в j.
13. 5. Булевы матрицы и операции над ними

Если G – граф (ориентированный или нет) без кратных дуг,
то его матрица смежности A является булевой, то есть состоит
из нулей и единиц. Для произвольной матрицы X = (xij) с
неотрицательными элементами будем обозначать через sign(X)
булеву

матрицу,

полученную

из

X

заменой

всех

ее

положительных элементов единицами. Например,
1 2 0 1 1 0

 

sign  0 2 1  =  0 1 1  .
3 0 1 1 0 1

 


Равенство sign(X) = X означает, что матрица X булева. Легко
видеть, что
sign(X+Y) = sign(sign(X) + sign(Y)),
sign(X·Y) = sign(sign(X)·sign(Y))
в случае, когда X и Y неотрицательные матрицы, для которых
определены соответствующие матричные операции. Далее, если
матрицы X и Y имеют одинаковую размерность, то
sign(X+Y) = sign(X) ∨ sign(Y)
(дизъюнкция булевых матриц вычисляется поэлементно).

120
Пусть A и B – булевы матрицы. Матрицу sign(A·B) будем
называть их булевым произведением и обозначать через A∗B. В
соответствии с определением sign(A·B) = A∗B. Если A = (aij) и

B = (bij),

то

элементы

булева

произведения

A∗B = (cij)

определяются формулами

cij = ai1b1j ∨ = ai2b2j ∨ … ∨ ainbnj ,
где n – число столбцов матрицы A и число строк матрицы B.
Положим A[k] = sign(Ak) и будем называть матрицу A[k] булевой
степенью матрицы A.
Если A – матрица смежности графа G, то на месте (i,j)
матрицы A[k] находится 1, если на графе G существует путь
длины k из i в j, и 0 в противном случае. Пусть n – число
вершин графа G. Тогда матрица

E ∨ A ∨ A[k] ∨…∨ A[n–1]
содержит 1 на месте (i,j) в том и только том случае, когда на
графе G имеется хотя бы один путь из вершины i в вершину j.
13. 6. Бинарные отношения и графы

Бинарное отношение R на конечном множестве V может
быть представлено ориентированным графом G(R), называемым

графом отношения R. Вершинами графа служат элементы
множества V; вершины x и y соединены направленной дугой с
началом x и концом y, если (x,y)∈R. Обратно, всякий
ориентированный граф без параллельных дуг G задает бинарное
отношение R(G) на множестве своих вершин, чьим графом он и

121
является: вершины x и y связаны отношением R(G), если они
соединены направленной дугой с началом x и концом y. Если R
– бинарное отношение на конечном множестве V = {1, 2, …, n},
а G – граф c вершинами V = {1, 2, …, n}, то матрица смежности
графа G совпадает с характеристической матрицей отношения R
в том и только том случае, когда G = G(R) или, что
равносильно, R = R(G).
Рассмотрим,

как

связаны

свойства

отношения

R

и

соответствующего ему графа G = G(R).
Отношение R симметрично, если для любых x, y∈V из xRy
следует yRx. Иными словами, если на ориентированном графе G
имеется дуга из x в y, то имеется также и дуга из y в x. В этом
случае матрица смежности графа G симметрична. По существу,
граф G оказывается неориентированным. Можно считать, что
симметричным

отношениям

отвечают

неориентированные

графы. Антисимметричность отношения R означает, что xRy и

yRx влечет x = y и равносильна тому, что две различные
вершины графа G могут быть связаны дугой лишь в одном
направлении. Если отношение R асимметрично, то есть xRy
влечет ¬yRx, то, кроме того, граф G не должен иметь петель.
Если R – рефлексивное отношение, то есть xRx для любого

x∈V, то граф G имеет петлю в каждой вершине, а диагональ
матрицы смежности состоит из одних единиц. Соответственно
отношение R антирефлексивно тогда и только тогда, когда граф

G не имеет петель.

122
Отношение R транзитивно, если из xRy и yRz следует xRz.
Для графа G это означает, что если G содержит дуги из x в y и
из y в z, то он содержит и дугу из x в z. Более того, если
существует путь из вершины x в вершину y, то имеется и дуга
из x в y.
В

терминах

графа

G = G(R)

простую

интерпретацию

получает понятие транзитивного замыкания отношения R. На
множестве

вершин

графа

G

определим

отношение

достижимости R^, полагая xR^y тогда и только тогда, когда
вершина y достижима из вершины x (в графе G имеется путь из

x в y). Отношение достижимости R^ является транзитивным
замыканием отношения R, то есть R^ – это наименьшее
транзитивное отношение, содержащее R. Матрицей отношения

R^ служит матрица E ∨ A ∨ A[k] ∨…∨ A[n–1], где A – матрица
смежности графа G.
Отношение R называется ацикличным, если граф G(R) не
содержит нетривиальных циклов. Если вершины x и y на графе
ацикличного отношения R соединены некоторым путем, то в
этом графе нет дуги из y в x.
Теорема. Отношение R на конечном множестве V

ациклично

тогда

и

только

тогда,

когда

существует

отображение ϕ:V→N такое, что xRy влечет ϕ(x) < ϕ(y) для
любых x,y∈V.

123
Д о к а з а т е л ь с т в о . Достаточность. Предположим, что
отображение ϕ обладает указанным свойством. Тогда для
любого цикла v0, v1, …,vn, v0 = vn, в графе G(R) имеем:
ϕ(v0) < ϕ(v1) <…< ϕ(vn) = ϕ(v0),

что невозможно при n > 0.

Необходимость. Пусть n = |V| – число элементов множества
V.

Для

произвольного

x∈V

рассмотрим

множество

всевозможных простых цепей в графе G(R), заканчивающихся в
вершине x. Ни одна из этих цепей не содержит более чем n
вершин, так что их длины ограничены в совокупности.
Положим ϕ(x) = k, где k – максимальная из длин простых цепей,
заканчивающихся в вершине x. Если нет ни одной цепи,
ведущей в x, то есть ни одна дуга не заканчивается в x, полагаем
ϕ(x)=0. Покажем, что так определенное отображение ϕ обладает

нужным свойством. Предположим, что xRy. Пусть ϕ(x)=k. Тогда
в графе G(R) имеется простая цепь v0, v1, …,vk = x. Добавив к
этой цепи дугу из x в y, мы получим маршрут v0, v1, …,vk = x, y
(длины k+1). Этот маршрут является простой цепью. В самом
деле, так как цепь v0, v1, …, vk простая, все вершины в ней
различны. Если y совпадает с одной из вершин этой цепи,
скажем y = vi, получается цикл y = vi, v1, …,vk = x, y, что
противоречит ацикличности отношения R. Следовательно,
имеется простая цепь длины k+1, заканчивающаяся в y. Значит,
ϕ(y) ≥ k+1 и потому ϕ(y) > ϕ(x).

124
Пример. Рассмотрим бинарное отношение R, граф которого

G(R) представлен на рис 9.
1

2

3

4

Рис. 9
В соответствии с определением отображения ϕ находим:
ϕ(1) = 0; ϕ(2) = 1; ϕ(3) = 2; ϕ(4) = 3.

Из предыдущей теоремы следует, что функция выбора CR
(блокировка), построенная по ацикличному отношению R,
является

расширением

некоторой

функции

выбора

по

скалярному критерию. В самом деле, пусть Ω = {1, 2, …, n} –
множество альтернатив, а R – ацикличное бинарное отношение
на Ω. Тогда, по предыдущей теореме, на множестве Ω
существует числовая функция ϕ :{1, 2, …, n}→N такая, что iRj
влечет ϕ(i) < ϕ(j). Зададим функцию f (скалярный критерий),
полагая

f(i) = n – ϕ(i).

Ясно,

Следовательно, f(i) ≤ f(j) влечет

что

iRj

влечет

f(i) > f(j).

¬iRj. Обозначим через C

функцию выбора по скалярному критерию f. Тогда

x∈C(X) ⇔ ∀y∈X f(x) ≥ f(y).

125
С другой стороны, в соответствии с определением функции
выбора CR имеем:

x∈CR(X)⇔ ∀y∈X ¬(yRx)}.
Следовательно,

x∈C(X) ⇒ x∈CR(X),
то есть C(X) ⊂ CR(X).

126

14. Деревья
14.1. Общее понятие дерева

К числу наиболее важных нелинейных структур, связанных
с

вычислительными

алгоритмами,

относятся

графы

специального вида, называемые деревьями. Структура дерева
появляется в тех ситуациях, где в той или иной форме имеется
«ветвление».
Граф (неориентированный) называется деревом, если он
связен и не имеет циклов. Например, граф на рис.1 является
деревом.

Рис. 1
Укажем некоторые свойства деревьев.
1. Любые две вершины дерева можно соединить ровно

одной простой цепью.
В силу связности между любыми двумя вершинами дерева
имеется соединяющая их цепь. Так как дерево не содержит
циклов, эта цепь является простой и единственной.

127
2. Если дерево G содержит хотя бы одно ребро, на нем

найдется висячая вершина.
Граф G не содержит циклов, поэтому ни одно его ребро не
является петлей, т. е. концевые вершины любого ребра
различны. Предположим, что степень любой вершины графа G
превосходит 1. Пусть v1, v2 – пара вершин, соединенных
ребром a1. Так как степень вершины v2 больше 1, имеется ребро

a2, отличное от a1, соединяющее вершину v2 с некоторой
вершиной v3. Вершины v1 и v3 должны различаться, иначе путь

v1, a1, v2, a2 v3 являлся бы циклом. Пользуясь тем, что степень
вершины v3 больше 1, можно продолжить путь v1, a1, v2, a2 v3
ребром a3, отличным от a2, соединяющим вершину v3 с
некоторой вершиной v4. Вершина v4 должна отличаться от всех
предыдущих вершин построенного пути (иначе получается
цикл). Подобным образом можно построить сколь угодно
длинный путь, на котором все вершины различны. С другой
стороны, любой путь, длина которого превосходит число
вершин графа, должен содержать повторяющиеся вершины.
Таким образом, предположение об отсутствии висячих вершин
на графе G приводит к противоречию.
3. Число ребер дерева G на единицу меньше числа его

вершин.
Доказательство проведем индукцией по числу вершин.
Дерево с одной вершиной не содержит ребер, так что при n = 1
имеем m = 0 – доказываемое соотношение выполняется.

128
Предположим теперь, что доказываемое равенство справедливо
для любого дерева с n – 1 вершиной и докажем его
справедливость для любого дерева с n вершинами. Пусть n ≥ 2 –
число вершин, а m число ребер дерева G. Покажем,
что m = n – 1. В соответствии с предыдущим пунктом дерево G
содержит висячую вершину v. Удалим эту вершину вместе с
инцидентным ей ребром. Легко видеть, что оставшийся граф
является деревом, которое содержит n – 1 вершину и m – 1
ребро. По индуктивному предположению имеем m – 1 = n – 2.
Отсюда m = n – 1.
Отметим,

что

последнее

свойство

является

характеристическим.
4. Связный граф, в котором число ребер на единицу меньше

числа вершин, является деревом.
Доказательство проведем индукцией по числу вершин
графа n. При n = 1 граф состоит из одной вершины и не
содержит ребер и, значит, является деревом. Предположим
теперь, что доказываемое утверждение справедливо для всех
графов, содержащих n – 1 вершину, и рассмотрим граф G с n
вершинами и n – 1 ребром. Сначала заметим, что граф G
содержит висячую вершину. В самом деле, как показано в 13.1,
сумма степеней вершин графа равна удвоенному числу ребер:
δ(v1) + δ(v2) +…+ δ(vn) = 2(n – 1).

Хотя бы одно слагаемое в левой части этого равенства меньше
двух (в противном случае сумма превосходила бы 2n). Пусть

129
для определенности, δ(vn) < 2. Так как граф связный, то степень
любой вершины не меньше 1. Следовательно, δ(vn) = 1. Это
означает, что вершина vn висячая. Граф G′, получающийся
удалением этой вершины вместе с инцидентным ей ребром,
связен,

содержит

n–1

вершину

и

n–2

ребра.

По

индуктивному предположению G′ является деревом. Но тогда и
исходный граф также является деревом (ни один цикл не может
содержать висячую вершину vn, а циклов, не содержащих эту
вершину, нет, поскольку они должны были бы целиком
находиться в G′).
14. 2. Остовное дерево связного графа

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

деревом графа G. Иными словами, остовное дерево графа G –
это его подграф, содержащий все вершины и являющийся
деревом.
Пример. На рис. 2 представлен граф с пятью вершинами и

восемью ребрами. Четыре выделенные ребра (вместе с пятью
вершинами) составляют остовное дерево этого графа. Остовное
дерево определено неоднозначно.

130

Рис. 2
На рис. 3 выделены ребра, составляющие еще одно остовное
дерево того же графа (заметим, что на этом рисунке
невыделенные ребра также составляют остовное дерево).

Рис. 3
В прикладном плане задачу нахождения остовного дерева
можно понимать как поиск системы связей между заданными
точками без ненужного дублирования.

Построение остовного дерева. Остовное дерево T графа G
можно сформировать следующим образом. Сначала берем в
качестве

T

произвольную

вершину

графа

G.

Далее

последовательно наращиваем дерево T в соответствии со
следующим правилом: если на графе G имеется ребро,
соединяющее вершины u и v такие, что u содержится в T, а v –

131
нет, добавляем к T это ребро вместе с вершиной v. Покажем,
что при этом граф Т остается деревом. Во-первых, каждая
добавляемая вершина связана с одной из уже входящих в T, так
что добавление новых вершин и ребер оставляет граф T
связным. Далее, в начальный момент граф T содержит одну
вершину и не имеет ни одного ребра. Затем на каждом шаге
построения число его вершин и число ребер увеличивается на
единицу. Таким образом, число вершин графа T на единицу
превосходит число его ребер. Следовательно, граф T является
деревом. На некотором шаге дальнейшее расширение T
окажется невозможным. Покажем, что в этом случае T
представляет собой остовное дерево графа G, т.е. все вершины
графа G попали в T. Обозначим через T’ граф, который
содержит все вершины графа G, не попавшие в T, и все
соединяющие их ребра. На графе G нет ребер, которые имели
бы одну концевую вершину в T, а другую в T’. Так как граф G
связный, T’ не может быть непустым.
Пусть n – число вершин, а m – число ребер графа G. Любое
его остовное дерево T имеет n вершин и n – 1 ребро. Таким
образом, остовное дерево получается отбрасыванием m – n + 1
ребер

графа G.

Число

ν(G) = m – n + 1

называют

цикломатическим числом графа G.
Остовное

дерево

графа

G

может

быть

получено

последовательным удалением ν(G) «лишних» ребер: на каждом

132
шаге можно отбросить любое ребро, если это не ведет к
нарушению связности графа.
Предположим,

что

каждому

ребру

графа

приписано

некоторое положительное число, называемое его весом или
стоимостью

(это

может

быть,

например,

в

случае

информационных сетей, стоимость установления связи между
концевыми

точками).

В

этом

случае

граф

называется

нагруженным. Стоимостью нагруженного графа будем считать
суммарную

стоимость

всех

его

ребер.

Многие

задачи,

связанные с построением экономичных систем сообщения или
информационных систем, приводят к задаче поиска остовного

дерева минимальной стоимости.
Пусть G – связный нагруженный граф. Обозначим через c(T)
стоимость произвольного подграфа T графа G. Если граф T
связный, содержит все вершины графа G и имеет минимальную
стоимость среди всех подграфов графа G, обладающих этими
двумя свойствами, то T является остовным деревом. В самом
деле, если бы граф T содержал цикл, то можно было бы
отбросить, по крайней мере, одно ребро и тем самым
уменьшить стоимость T.
Опишем

минимальной

алгоритм

построения

стоимости.

видоизменением

алгоритма

Он

остовного

получается

построения

дерева

небольшим

остовного

дерева

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

133
это возможно, последовательно наращиваем дерево T: из всех
ребер графа G, соединяющих вершины u∈T и v∉T, выбираем
ребро минимальной стоимости и добавляем к T это ребро
вместе с вершиной v. Полученное в результате исполнения
этого алгоритма остовное дерево будет иметь минимальную
стоимость.
Пример. На рис. 4 выделено остовное дерево минимальной

стоимости.

Его

стоимость

равна

6.

Остовное

дерево,

представленное на рис. 2, при тех же оценках ребер имеет
стоимость 8, остовное дерево на рис. 3 – стоимость 8,
невыделенные ребра на рис. 3 составляют остовное дерево
стоимости 10.
3
1

2

3

3
2

1
3

Рис. 4
14. 3. Ориентированные и упорядоченные деревья

Пусть G –дерево с n > 1 вершинами. Зафиксируем одну из
вершин v0 и назовем ее корнем. Выделение корня определяет на
множестве

вершин

некоторое

естественное

отношение

частичного порядка (ориентацию): вершина u предшествует
вершине v (а вершина v следует за вершиной u), если u

134
встречается на пути из корневой вершины v0 в вершину v. Если
к тому же вершины u и v связаны дугой, то u называется
непосредственно

предшествующей

вершине

v



v



непосредственно следующей за u). Говорят, что вершина v,
удаленная на расстояние k от корневой вершины, расположена
на уровне k (или является вершиной уровня k). Значение уровня
согласуется

с

отношением

порядка:

если

вершина

u

предшествует вершине v, то уровень u меньше уровня v.
Обратное,

вообще

говоря,

неверно.

Представляя

дерево

графически, вершины обычно располагают так, чтобы значение
уровня увеличивалось в направлении сверху вниз.
На рис. 5 представлено дерево, в котором вершина 0
является корнем; вершины 1 и 2 находятся на первом уровне,
вершина 3 – на третьем; вершина 1 предшествует вершине 3;
вершины 1 и 3 с вершиной 2 отношением предшествования не
связаны.
0
1
2
3

Рис. 5
Вершины, за которыми не следует ни одна вершина,
называют концевыми, или, в «древесном» стиле, – листьями. На
рис. 5 вершина 3 является листом, всего же дерево на этом

135
рисунке имеет 7 листьев. У деревьев с выделенным корнем
вершины часто называют узлами. Неконцевые узлы называют

узлами ветвления. Число вершин, непосредственно следующих
за узлом ветвления, называют степенью ветвления этого узла.
На рис 5 узлы 0 и 1 имеют степень ветвления 2, узел 2 –
степень 3.
Каждую

вершину

дерева

можно

рассматривать

как

корневую вершину дерева, состоящего из всех следующих за
ней вершин. Например, взяв в качестве корневых вершины 1 и 2
(см. рис 5), получим пару деревьев, изображенных на рис. 6.
1
2
3

Рис. 6
С учетом этого можно дать следующее рекурсивное
определение дерева с корнем (или ориентированного дерева).

Дерево с корнем T – это конечное множество, состоящее из
одного или более узлов таких, что:
1) имеется один выделенный узел, называемый корнем
данного дерева;
2)

остальные

узлы

разбиты

на

m≥0

попарно

непересекающихся множеств, каждое из которых в свою
очередь является деревом.

136
Например, дерево на рис. 7 можно описать следующим
образом:

T = {1, T2}, T2 = {2, T3, T4}, T3 = {3, T5, T6, T7},
T5 = {5}, T6 = {6}, T7 = {7},
T4 = {4, T8}, T8 = {8, T9, T10}, T9 = {9}, T10 = {10}.
В явном виде это описание выглядит так:

T = {1; {2; {3; {5}, {6}, {7}}, {4; {8; {9}, {10}}}}}.
1
3

2

4
8

5

6

7
9

10

Рис. 7
Если в рекурсивном определении ориентированного дерева
считать существенным порядок, в котором перечисляются
поддеревья,

растущие

из

заданного

корня,

получается

определение упорядоченного дерева. Например, дерево с рис. 7
можно представить как упорядоченное дерево

T = (1; (2; (3; (5, 6, 7)), (4; (8; (9, 10))))).
Возможно и иное представление. Например,

T’ = (1; (2; (4; (8; (9, 10))), (3; (5, 6, 7)))).
Более формально:
1) всякий узел a является упорядоченным деревом с
корнем a;

137
2) если a – некоторый узел, а T1, T1, …, Tm, m≥0, –
упорядоченные деревья, то T = (a; (T1, T1, …, Tm)) – упорядоченное дерево с корнем a.
Упорядоченные деревья – одна из наиболее распространенных информационных и алгоритмических структур.
Например, дерево на рис. 8 задает алгоритм вычисления
значения арифметического выражения (1+2) – (3/4)2.

+



^2
/

1

2
3

4

Рис. 8
14. 4. Бинарные деревья

Бинарными называют упорядоченные деревья, в которых
каждый узел имеет не более двух, непосредственно следующих
за ним узлов (рис. 9).
a
c

b

d
g

e

f
h

Рис. 9

i

138
Бинарные
представления

деревья

наиболее

информации,

часто

используются

обрабатываемой

с

для

помощью

вычислительных машин. Рекурсивно бинарное дерево можно
определить как конечное множество узлов, которое или пусто,
или состоит из корня и двух не имеющих общих узлов
бинарных деревьев – левого и правого.
Приписывая дуге, ведущей из произвольного узла к левому
дереву, символ «0», а дуге, ведущей к правому дереву,
символ «1», можно любой путь из корневой вершины (а вместе
с ним и конечную вершину этого пути) закодировать с
помощью нулей и единиц.
Например, на рис. 9 корневая вершина a получает в качестве
кода пустую последовательность ∅, а остальные вершины
следующие коды:

b – 1;

c – 10;

e – 100;

f – 101;

d – 11;

g – 111;

h – 1110; i – 1111.

Найдем число различных бинарных деревьев с заданным

числом вершин.
Пусть bn – число различных бинарных деревьев с n
вершинами. Ясно, что b0 = 1 (имеется ровно одно пустое
бинарное дерево) и b1 = 1.
При n > 0 всякое бинарное дерево с n вершинами имеет вид
(a; (T0, T1)), где T0 – бинарное дерево с k < n вершинами, а T1 –
бинарное дерево с n – k – 1 вершиной. Число способов
расположить одно бинарное дерево с k < n вершинами слева от

139
корня, а другое бинарное дерево с n – k – 1 вершиной справа от
корня равно bkbn–k–1. Следовательно, суммируя по всем k < n,
получаем:

bn = b0bn–1 + b1bn–2 + … + bn–1b0.

(1)

В частности:

b1 = b02 = 1; b2 = b0b1 + b1b0 = 2;
b3 = b0b2 + b1b1+ b2b0 = 5; … .
Последние равенства показывают, что последовательность
чисел (bn) – это последовательность чисел Каталана (см. 11.4).
Для полноты изложения напомним коротко, как могут быть
получены явные выражения в факториалах для чисел bn.
Запишем производящую функцию:

B(z) = b0 + b1z + b2z2 + … .

(2)

Основываясь на (1), получаем:

B(z)2 = b02 + (b0b1 + b1b0)z + (b0b2 + b1b1+ b2b0)z2 … =
= b1 + b2z + b3z2 + … .
Умножая обе части последнего равенства на z и добавляя 1,
приходим к соотношению

z⋅B(z)2 +1 = B(z).
Таким образом, y = B(z) удовлетворяет квадратному уравнению

z⋅y2 – y +1 = 0.
Решая его, находим:

B( z ) =

(

)

1
1 − 1 − 4z .
2z

140
Теперь разложим правую часть полученного равенства,
воспользовавшись биномом Ньютона:

B( z ) =

k  1 / 2  2 n +1 n
(
1
)


 ⋅ 2
z .

n
1
+


n ≥0

Сравнивая (1) и (2), приходим к заключению, что для всех n
справедливо следующее равенство:
 1 / 2  2 n +1
1  2n 
  .
bn = (−1) k 
 ⋅ 2
=
+
1
n
+
1
n


n

(3)

Пример. Перечислим все бинарные деревья с 4 вершинами.

В соответствии с формулой (3) имеем:
1 8 8⋅7 ⋅6⋅5
b4 =   =
= 14 .
5  4 5⋅ 4 ⋅3⋅ 2
На рис. 10, представлены четырнадцать бинарных деревьев с
четырьмя вершинами.

141

Рис. 10
Применим к (3) формулу Стирлинга. Получаем:
1
4 рn ⋅ (2n) 2n e − 2n
22n
bn ≈
=
.
n −n 2
n +1
(
n
+
1
)
р
n
2 рn ⋅ n e

(

)

(4)

Формула (4) дает хорошее приближение даже при сравнительно
малых значениях n. Например, при n = 4 имеем:
28
b4 ≈
≈ 14,4.
5 4р

142

15. Доминирование. Внутренняя и внешняя
устойчивость в графах
15. 1. Порядковая функция графа

Пусть G = (V, E) – ориентированный граф. Наличие дуги,
идущей из вершины u в вершину v, можно интерпретировать
как доминирование u над v (в содержательных моделях –
превосходство или предпочтительность в некотором смысле).
Для вершины u обозначим через G(u) множество всех вершин,
над которыми u доминирует, т.е. множество концевых вершин
дуг, начинающихся в вершине u. Если U ⊂ V – некоторое
множество вершин, обозначим через G(U) объединение всех
множеств G(u), где u∈U. Таким образом, v∈G(U) тогда и только
тогда, когда над вершиной v доминирует хотя бы одна вершина
из U.
Теорема. В непустом ацикличном орграфе G имеется

вершина, из которой не исходит ни одна дуга.
Д о к а з а т е л ь с т в о . Предположим противное. Это означает,
что для любой вершины v множество G(v) не пусто. Тогда,
выбрав произвольно вершину v0, можно построить сколь угодно
длинную цепочку вершин v0, v1∈G(v0), v2∈G(v1), … . Поскольку
число вершин графа G конечно, в этой цепочке некоторые
вершины будут повторяться. Но цепочка вида vs, vs+1, …, vt = vs
является циклом, что противоречит ацикличности графа G.

143
Условимся обозначать через L0(G) множество всех вершин
графа G, из которых не исходит ни одна дуга. В соответствии с
предыдущей теоремой L0(G) не пусто, если G – непустой
ацикличный граф.
Обозначим через G–1 граф, полученный из графа G
изменением направлений всех дуг на противоположные. Для
любой вершины v множество G–1(v) содержит все те вершины,
из которых в вершину v ведет некоторая дуга графа G.
Множество L0(G–1) состоит из всех тех вершин, в которые не
заходит ни одна дуга графа G.
В 13.6 было доказано, что отношение R на конечном
множестве V ациклично тогда и только тогда, когда каждому
элементу v множества V можно приписать натуральное число
ϕ(v) (оценку элемента v) так, что xRy влечет ϕ(x) < ϕ(y) для

любых x,y∈V. В этом пункте мы рассмотрим один из
алгоритмов «оценивания» вершин ацикличного орграфа, при
котором оценки согласуются с отношением доминирования:
если вершина u доминирует над вершиной v, то оценка u будет
выше, чем оценка v.
Предполагая, что граф G не содержит циклов, разобьем
множество

его

вершин

на

так

называемые

уровневые

множества (или просто уровни). Уровневые множества
строятся рекурсивно:

L0 = { v∈V | G(v) = ∅ } = L0(G);
L1 = { v ∈ V \ L0 | G(v) ⊂ L0 };

144

L2 = { v ∈ V \ (L0 ∪ L1)| G(v) ⊂ L0 ∪ L1 };
L3 = { v ∈ V \ (L0 ∪ L1 ∪ L2)| G(v) ⊂ L0 ∪ L1 ∪ L2 };
………………………………………………………….
Так как граф G ацикличен, множество L0 не пусто.
Обозначим

через

G′

граф,

полученный

из

графа

G

отбрасыванием вершин из L0 и входящих в них дуг. Заметим,
что L1 = L0(G′). Если V0 ≠ V, граф G′ не пуст и не содержит
циклов. Следовательно, множество L1 = L0(G′) не пусто.
Продолжаем аналогичным образом. Если

L0 ∪ L1 ∪…∪ Lk–1 ≠ V,
обозначим

через

G(k)

граф,

полученный

из

графа

G

отбрасыванием всех вершин из L0 ∪ L1 ∪…∪ Lk–1 и водящих в
них дуг. Тогда Lk = L0(G(k)) ≠ ∅. Так как множество вершин
графа конечно, в ряду уровневых множеств L0, L1, …, найдется
такое множество Lr, что Lr ≠ ∅, а Lr+1 = ∅. Все множества

L0, L1, …, Lr не пустые, не пересекаются, а их объединение
равно V.
Каждая

вершина

графа

попадает

в

свое

уровневое

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

расположены на соответствующих уровнях.

145
L3
L2

L1

L0

Рис. 1
Заметим, что предыдущий алгоритм построения уровневых
множеств можно использовать для проверки ацикличности
графа. Если граф G содержит циклы, то на некотором шаге
возникнет ситуация, когда

L0 ∪ L1 ∪…∪ Lk–1 ≠ V, и L0(G(k)) = ∅.
15. 2. Внешняя устойчивость

Пусть G = (V, E) – ориентированный граф. Множество
вершин D ⊂ V называется доминирующим, если в каждую
вершину, не принадлежащую D, ведет некоторая дуга из
вершины, находящейся в D. Иными словами, множество D
доминирующее,

если

D∪G(D) = V.

Минимальным

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

146
1) d∉G(D);
2) имеется дуга, идущая из вершины d в некоторую вершину

d′∉D, причем никакая другая дуга с началом в одной из вершин
множества D не ведет в d′.
В самом деле, если для вершины d ∈ D выполняется одно из
этих

двух

условий,

множество

D\{d}

не

является

доминирующим.
Множество вершин U ⊂ V называется внешне устойчивым в
графе G, если U является доминирующим в графе G–1. Таким
образом, множество вершин U внешне устойчиво, если любая
вершина v, не входящая в U, служит началом хотя бы одной
дуги, конец которой находится в U.
Пример. Пусть G – граф, изображенный на рис. 2. Любое

доминирующее

множество

графа

G

должно

содержать

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

3

5

1

4

Рис. 2

147
Любое внешне устойчивое множество содержит вершину 4. Эта
вершина вместе с любой другой составляет

минимальное

внешне устойчивое множество вершин графа G.
Пусть

G – ориентированный

граф.

Перенумеровав

его

вершины, будем считать, что вершинами графа G служат числа
1, 2, …, n. Пусть A = (aij) – матрица смежности графа G. Тогда
равенство aij = 1 означает, что на графе G имеется дуга из
вершины i в вершину j. Каждому подмножеству U множества
вершин графа G сопоставим его характеристический вектор (ui)
так, что ui = 1 тогда и только тогда, когда i ∈ U.
Множество вершин U внешне устойчиво тогда и только
тогда, когда для каждого i = 1, 2, …, n выполняется условие:
если ui = 0, найдется j ∈ {1, 2,…, n} такое, что uj = 1 и aij = 1.
Иными словами, множество вершин U внешне устойчиво,
если булево выражение
¬ui → (ai1u1 ∨ ai2u2 ∨ …∨ ainun)

(1)

принимает значение 1 для всех i = 1, 2, …, n. В равносильной
форме (1) можно переписать так:

ui ∨ ( ∨ u j ) .
aij =1

Положим
n

f (U ) = ∧ (ui ∨ ( ∨ u j ))
i =1

aij =1

(2)

Множество U внешне устойчиво в том и только том случае,
когда f(U) = 1. Таким образом, булева функция (2) является

148
характеристической функцией семейства внешне устойчивых
множеств в совокупности всех подмножеств множества вершин
графа G.
Представим
дизъюнктивный

функцию
член

(2)

в

виде

соответствует

ДНФ.

внешне

Каждый

устойчивому

множеству. Если в ДНФ входит элементарная конъюнкция

uiuj…uk, то на множестве вершин U = {i, j, …, k} функция f
принимает значение 1 и, значит, множество U внешне
устойчиво. Раскрыв в (2) скобки и проведя все сокращения в
соответствии с тождествами

xx = x, x ∨ x = x, x ∨ (xy) = x, x(x ∨ y) =x,
мы

получим

ДНФ,

в

которой

дизъюнктивные

члены

соответствуют минимальным внешне устойчивым множествам.
Пример. Составим характеристическую функцию внешне

устойчивых множеств (2) для графа G, представленного на
рис.2:

f = (u1 ∨ u4)(u2 ∨ u1 ∨ u3∨ u5)(u3 ∨ u4)u4(u5 ∨ u1 ∨ u3∨ u4).
После раскрытия скобок и упрощений получаем:

f = u1u4 ∨ u2u4 ∨ u3u4 ∨ u4u5.
Следовательно,

граф

G

обладает

следующими

минимальными внешне устойчивыми множествами вершин:
{1, 4}, {2, 4}, {3, 4}, {4, 5}.

149
15. 3. Внутренняя устойчивость

Пусть G = (V, E) – ориентированный граф. Множество
вершин

U⊂V

называется

внутренне

устойчивым,

если

U∩D(U) = ∅, т. е. в графе G не существует дуги, связывающей
пару вершин из U. Внутренне устойчивое множество вершин

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

Поскольку граф не содержит петель, любое множество,
содержащее одну вершину, является внутренне устойчивым.
Максимальными внутренне устойчивыми являются множества
вершин {2, 4}, {1, 3} и {5}.
Пусть G – ориентированный граф. Так же, как и в
предыдущем пункте, перенумеровав его вершины, будем
считать, что вершинами графа G служат числа 1, 2, …, n. Пусть

A = (aij) – матрица смежности графа G. Для множества вершин
U пусть (ui) – его характеристический вектор.
Множество вершин U внутренне устойчиво тогда и только
тогда, когда для любых i, j = 1, 2, …, n выполняется условие:
если ui = 1 и aij = 1, то uj = 0.
Иными словами, множество вершин U внутренне устойчиво,
если булево выражение
(ui ∧ aij) → ¬uj

(3)

150
принимает значение 1 для всех i, j = 1, 2, …, n. В равносильной
форме предыдущее условие можно представить так:
¬ui ∨ ¬aij ∨ ¬uj =1

для всех i, j = 1, 2, …, n. Положим
n

f (U ) = ∧ (¬ui ∨ ¬aij ∨ ¬u j ) .
i , j =1

(4)

Множество U внутренне устойчиво в том и только том случае,
когда f(U) = 1. Таким образом, булева функция (4) является
характеристической функцией семейства внутренне устойчивых
множеств в совокупности всех подмножеств множества вершин
графа G. Те множители (конъюнктивные члены), в которых

ai,j = 0, обращаются в единицу, поэтому их можно опустить.
С учетом этого получаем:
n

f (U ) = ∧ (¬ui ∨ ¬u j ) .
aij =1

Представим

функцию

f(U)

в

виде

ДНФ.

Каждый

дизъюнктивный член соответствует внутренне устойчивому
множеству. Если в ДНФ входит элементарная конъюнкция

uiuj…uk, то на множестве вершин {i, j, …, k} функция f
принимает значение 0 и, значит, дополнение этого множества
внутренне устойчиво. Проведя все сокращения в соответствии с
тождествами

xx = x, x ∨ x = x, x ∨ (xy) = x, x(x ∨ y) =x,

151
мы

получим

соответствуют

ДНФ,

в

которой

максимальным

дизъюнктивные
внутренне

члены

устойчивым

множествам.
Пример. Составим характеристическую функцию внутренне

устойчивых множеств (2) для графа G, представленного на
рис. 2:

f = (¬u1 ∨ ¬u4)(¬u2 ∨ ¬u1)(¬u2 ∨ ¬u3)(¬u2 ∨ ¬u5)∧
∧(¬u3 ∨ ¬u4)(¬u5 ∨ ¬u1)(¬u5 ∨ ¬u3)(¬u5 ∨ ¬u4).

После раскрытия скобок и упрощений получаем

f = ¬u1¬u2¬u3¬u4 ∨ ¬u1¬u3¬u5 ∨ ¬u2¬u4¬u5.
Следовательно,

G

граф

обладает

следующими

максимальными внутренне устойчивыми множествами вершин:
{5}, {2, 4}, {1, 3}.
15. 4. Ядро графа

Пусть G = (V, E) – ориентированный граф. Множество
вершин N ⊂ V называется ядром, если оно одновременно
внешне и внутренне устойчиво.
Примеры.

Граф

на

рис.

2

обладает

ядром {2, 4}. Граф на рис. 3 ядер не имеет.

единственным

152
1

2

3

Рис. 3
Граф на рис. 4 имеет два ядра: {1, 3} и {2, 4}.
2

3

1

4

Рис. 4
Теорема. Множество вершин ориентированного графа

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

что

ориентированный

граф

G = (V, E)

представляет некоторое отношение предпочтения. Более точно:
множество вершин V – это множество вариантов (альтернатив);
наличие дуги из x в y означает, что y «лучше», чем x. Для
ситуаций выбора типично, когда известно, что значит «лучше»,
но не известно, что значит «хорошо». Ядро, которое называют

решением задачи выбора по Нейману – Моргенштерну, это в

153
некотором

смысле

множество

«хороших»

вариантов.

В

соответствии с определением для каждого невыбранного
варианта в ядре содержится вариант, который лучше него.
Кроме того, если некоторый вариант попал в ядро, худшие, чем
он, варианты в это ядро уже не попадут. В «простых» случаях
ядро дает естественное решение задачи выбора. Так, если граф

G не содержит циклов, а отношение предпочтения транзитивно,
то единственным ядром графа G служит множество вершин
уровня 0 (множество недоминируемых альтернатив). Ядро дает
решение задачи выбора и в более сложных случаях.
Пример. Пусть имеются шесть вариантов {1, 2, 3, 4, 5, 6},

которые оцениваются по четырем критериям. Возможные
оценки по каждому критерию: 0, 1, 2, 3, 4.

154
В следующей таблице приведены оценки вариантов.
Показатели

П1

П2

П3

П4

Варианты
1

3

3

0

2

2

3

1

1

3

3

2

1

2

1

4

4

2

1

1

5

2

3

1

3

6

2

2

0

4

Будем считать, что вариант x лучше варианта y, если x не
содержит ни одной нулевой оценки и число показателей, по
которым он лучше варианта y, больше, чем число показателей,
по

которым

y

лучше,

чем

x.

На

рис.

5

изображен

соответствующий граф предпочтений.
5

6

4
3

1

2

Рис. 5
Единственным ядром графа служит множество {2, 5}. Это и
есть множество «хороших» вариантов. Чтобы сделать выбор

155
между вторым и пятым вариантом, требуется привлечь
дополнительную информацию.
Пример. Граф на рис. 6 обладает двумя ядрами: {1, 5, 7}

и {2, 4, 6, 8}.
1

2

4
3

6

5

7

Рис. 6

8