Тырсин А.Н. Учебное пособие по дискретной математике

Теорема 8.4. Справедливо соотношение

N (r) (r) C1 (r 1) C 2		(r 2) ( 1)n r C n r (n) .
r 1	r 2	n

Примем без доказательства.

Пример 8.2. Из 100 студентов 60 читают журнал A, 50 читают журнал

B, 50 – C, 30 – A и B, 20 – B и C, 40 – A и C, 10 – A, B и C. Сколько студентов не читает ни одного из трех журналов? Сколько студентов читает ровно два журнала?

Решение. В данной задаче в роли исходного множества из 100 студентов, подмножества A1, A2, A3 составляют студенты, читающие соответствующие журналы. Имеем: (0) = 100, (1) = 60 + 50 + 50 = 160,

(2) = 30 + 20 + 40 = 90, (3) = 10. Тогда N(0) = (0) (1) + (2) (3) = 20,

N(2) = (2) C31 (3) = 90 – 3 10 = 60,

т.е. 20 студентов не читает журналов, 60 – читает ровно два журнала.

8.4. Производящие функции

Определение 8.4. Производящей функцией для последовательности {a0, a1, , an, } называется формальный степенной ряд

A(x) ak xk .		(8.3)
k	0

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

Суммой рядов A(x) ak xk и B(x) bk xk называется ряд
k 0		k 0
A(x) B(x) (ak bk )xk .		(8.4)
k 0
Произведением ряда A(x) на число называется ряд
A(x) ak xk .		(8.5)
k 0
Произведением рядов A(x) и B(x) называется ряд
	k
A(x) B(x) ck xk , ck	aibk i .	(8.6)
k 0	i 0

Если в последовательности {ak} лишь конечное число членов отлично от нуля, то ряд A(x) можно рассматривать как многочлен. Если и в последовательности {bk} все члены, начиная с некоторого, равны нулю, то

51

ряд B(x) – также многочлен, и формула (8.6) переходит в обычную формулу умножения многочленов.

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

A(k ) (0)

ak k! , k 0, 1, 2, .

Заметим, что если A(x) и B(x) – аналитические функции в окрестности нуля, то соотношения (8.4) – (8.6) будут справедливы для них и как для числовых функций. Сохраняющее операции сложения и умножения взаимно однозначное соответствие между функциями, аналитическими в окрестности нуля, и их рядами Маклорена, позволяет отождествить формальный ряд (8.3) с определяемой им аналитической функцией. В табл. 8.1 представлены производящие функции для некоторых простых последовательностей.

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

Последовательность {ak}

Производящая функция A(x)

1, 1, , 1,

1

1 x

1,

1

,

1

, ,

1

,

ex

1!

2!

k!

1, 2, 22, , 2k,

1

1 2x

0, 1, 2, , k,

x

(1 x)2

Cn0 ,Cn1 , ,Cnk , ,Cnn ,0,

(1+x)n

1, , ( 1) , ,

( )k

,

(1+x)

2!

k!

S(n,0), S(n,1), , S(n,k),

(x)n

Покажем, например, как может быть получена производящая функция для последовательности неотрицательных целых чисел:

x

x

k

k 1

k

k

kx

x kx

x (x

) x( x

) x

.

(1 x)2

k 0

k 1

k 1

k 1

1

x

Пример 8.3. Рассмотрим применение аппарата производящих функций для комбинаторики на примере следующей задачи:

Найти ak – число всех неупорядоченных k-элементных выборок с повторениями, удовлетворяющих заданным ограничениям на число

52

вхождений в них каждого элемента генеральной совокупности {x1, x2, , xn} элемент xi может присутствовать в выборке yi раз, где yi – элемент некоторого числового множества Xi N0 (i = 1, 2, , n).

Решение. Проиллюстрируем постановку задачи на двух простых примерах.

1.Сколько разных наборов из k шаров можно получить, имея 1 синий шар, 2 одинаковых белых шара и 4 одинаковых красных шара?

Здесь генеральная совокупность состоит из синего, белого и красного шара. Возможное число вхождений каждого шара в набор определяется множествами X1 = {0, 1}, X2 = {0, 1, 2}, X3 = {0, 1, 2, 3, 4}.

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

В данном случае генеральная совокупность состоит из синего, белого

икрасного шара. Возможное число вхождений каждого шара в набор

определяется	множествами X1 = {0, 1},	X2 = {0, 1, 2}, X3 = {1, 3}.
Изменилось только множество X3, определяющее допустимое число
вхождений красного шара.
Пусть A(x) – производящая функция для последовательности {ak}.
Тогда справедливо соотношение
n	x yi .
A(x)		(8.7)

i 1 yi Xi

Действительно,

n

x yi

i 1 yi Xi
где ak	1

y1 yn k

если «раскрыть скобки» в правой части (8.7), то получим:

x y1 x yn ak xk ,

y1, , yn

k 0

.

В выражении для	ak	суммирование	производится	по всем наборам
(y1, , yn) таким,	что	x yi Xi и	y1 + + yn = k,	в результате чего

получится искомое число k-элементных выборок.

Возвращаясь к первому примеру, запишем для него производящую функцию:

A(x) (1 x)(1 x x2 )(1 x x2 x3 x4 )

1 3x 5x2 6x3 6x4 5x5 x7 .

Коэффициент при xk есть число k-элементных наборов. Таким образом, можно составить 3 одноэлементных набора, 5 – двухэлементных, 6 – трехэлементных и т.д.

Во втором примере

A(x) (1 x)(1 x x2 )(x x3 ) x 2x2 3x3 3x4 2x5 x6 .

Здесь можно составить 1 одноэлементный набор, 2 – двухэлементных, 3 – трехэлементных и т.д.

53

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

Сочетания без повторений. Каждый элемент в выборке встречается не более одного раза, т.е. i Xi = {0, 1}; k-выборка при этом является сочетанием без повторений из n по k. Производящая функция имеет вид:

n

A(x) (1 x)n Cnk xk .

k 0

Сочетания с повторениями. Каждый элемент в выборке может появиться любое число раз: i Xi = N0, k-выборка представляет собой сочетание с повторениями из n по k. Производящая функция имеет вид:

A(x)	(1 x x	2	)	n			1 n
					1		x
n( n 1) ( n k 1)							( x)k
k 0	k!
Cnk k 1xk .

k 0

(1 x) n [биномиальный ряд] =

		n(n 1) (n k 1)	( 1)k
		k!
	k 0

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

повторениями: V k Ck		.
n	n k 1

54

Раздел IV. Введение в теорию графов

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

Глава 9. Основные понятия теории графов

9.1. Основные определения

Определение 9.1. Граф – это упорядоченная пара G = V, E , где V – непустое конечное множество (элементы множества V – вершины графа); E – конечное семейство неупорядоченных пар (необязательно различных) элементов V (элементы E – ребра графа).

Термин «семейство» говорит, что элементы в E могут повторяться. При этом повторяющиеся элементы в множестве E называют кратными ребрами. Если во множестве E нет повторяющихся элементов, то соответствующий граф называется простым.

Пример 9.1. На рис. 9.1 изображен простой граф с множеством вершин V = {a, b, c, d, e} и множеством ребер E = {(a,b), (a,c), (b,c), (c,d)}.

Рис. 9.1. Пример простого графа

Если в графе имеется ребро e = uv, то говорят: вершины u и v – смежные, или ребро e инцидентно вершинам u и v, или вершины u и v – инцидентны ребру e, или ребро e соединяет вершины u и v, или вершины u и v – концы ребра e.

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

Ребро, соединяющее вершину саму с собой, называется петлей. Таким образом, простой граф – это граф без петель и кратных ребер.

Линии, изображающие ребра графа, могут пересекаться, но точки пересечения не являются вершинами.

55

Пример 9.2. На рис. 9.2 изображен граф с множествами вершин

V = {a, b, c, d, e} и ребер E = {(a,b), (a,c), (a,c), (b,c), (b,b), (c,d)}.

Рис. 9.2. Пример графа с петлей и кратными ребрами

Определение	9.2.	Ориентированный граф – упорядоченная пара
G = V, A , где	V –	непустое множество вершин; A – семейство

упорядоченных пар элементов V (необязательно различных). Множество A называют семейством дуг. Направленные ребра часто называют дугами. Первая по порядку вершина, инцидентная ребру ориентированного графа, называется его началом, вторая – концом. Ориентированный граф называют также ор-графом.

Упорядоченная пара элементов V представляет собой ребро (дугу), имеющее направление от одной вершины к другой.

Пример 9.3. На рис. 9.3 изображен пример ориентированного графа с множеством вершин V = {a, b, c, d, e} и семейством дуг

A = {(a,b), (a,c), (c,a), (b,c), (b,b), (c,d)}.

Рис. 9.3. Пример ориентированного графа

Определение 9.2. Степенью вершины графа называется число инцидентных ей ребер. При подсчете степени вершины петли учитываются дважды. Степень вершины v обозначим (v). Вершина v называется изолированной, если (v) = 0, и висячей, если (v) = 1.

Теорема 9.1. (Лемма о рукопожатиях). Сумма степеней всех вершин графа равна удвоенному числу ребер: (v) 2 E .

v G

56

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

Следствие 9.1. В любом графе число вершин нечетной степени четно.

Определение 9.3. Граф называется конечным, если множество его элементов (вершин и ребер) конечно, и пустым, если множество его элементов пусто.

Определение 9.4. Граф без петель и кратных ребер, в котором каждая пара вершин соединена ребром, называется полным.

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

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

Определение 9.7. Графы G1 = <V1, E1> и G2 = <V2, E2> равны, если у них V1 = V2, E1 = E2.

Определение 9.8. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Примеры изоморфных графов приведен на рис. 9.4.

Рис. 9.4. Изоморфные графы

Определение 9.9. Если у графа зафиксирована нумерация вершин и ребер, то он считается полностью заданным.

Пример 9.4. Начало теории графов было положено Л. Эйлером при решении задачи о Кенигсбергских мостах в 1736 году. Город Кенигсберг

57

имел в те времена семь мостов, соединяющих острова на реке Преголя с берегами и друг другом, таким образом, как показано на рис. 9.5.а).

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

Рис. 9.5. Граф «Кенигсбергские мосты»

9.2.Способы задания графов

Вобщем случае для задания графа необходимо:

1)Описать множества его вершин и ребер.

2)Задать на множествах вершин и ребер отношение инцидентности.

Для описания вершин и ребер достаточно их занумеровать. Обозначим: v1, , vn – вершины графа G; e1, , em – ребра графа G.

Основные способы задания графов следующие:

1.Графический способ.

2.В виде двух множеств вершин V и ребер E.

3.В виде матрицы инцидентности.

4.В виде матрицы смежности.

5.В виде списка ребер.

Первые два способа были рассмотрены выше. Поэтому рассмотрим более подробно последние три способа.

58

Зададим матрицу инцидентности { ij}m n следующим образом: по вертикали и горизонтали указываются вершины и ребра соответственно. Если ребро ei инцидентно вершине vj, то ij = 1. В противном случае, ij = 0. Матрица { ij} называется матрицей инцидентности неориентированного графа G. Для ориентированного графа элементы ij матрицы инцидентности определяются следующим образом:

1, если вершина v j начало ребра ei ,
	если вершина v j конец ребра ei ,
1,
ij	если ребро e петля, v		вершина, инцидентная v		, 0, 1,
,		j		j
	i
0,	в остальных случаях.

Пример 9.5. На рис. 9.6 приведен граф, имеющий 5 вершин и 9 ребер (в том числе одну петлю). Чтобы различить нумерацию вершин и ребер, на рисунке номера ребер указаны курсивом.

Матрица инцидентности имеет вид:

		1	1	0	0	0
		1	0	1	0	0
		0	1	1	0	0
		0	1	0	0	1
{ }		0	0	1	1	0	.
ij
		0	0	1	0	1
		0	0	0	1	1
		0	0	0	0	1
		0	1	0	0	1

Рис. 9.6. Неориентированный граф

59

Пример 9.6. На рис. 9.7 изображен ор-граф, имеющий 5 вершин и 7 ребер (в том числе одну петлю). Номера ребер указаны курсивом.

Рис. 9.7. Ор-граф

Матрица инцидентности этого графа имеет вид:

	0	1	1	0	0
	1	0	1	0	0
	1	0	0	1	0
{ ij } 0		0	2	0	0 .
	0	0	1	1	0
	0	0	1	0	1
	0	0	1	0	1

Рассмотрим далее задание графа с помощью матрицы смежности. Матрица смежности { ij}n n графа является квадратной (n – число вершин), столбцам и строкам которой соответствуют вершины графа. Для неориентированного графа элемент матрицы ij равен количеству ребер, инцидентных i-й и j-й вершинам; для ор-графа этот элемент матрицы смежности равен количеству ребер с началом в i-й вершине и концом в j-й.

Матрица смежности неориентированного графа симметрична относительно главной диагонали ij = ji, и все его ребра определяются верхним правым треугольником матрицы смежности, включая главную диагональ. Количество их NE равно сумме ij в этом треугольнике, т.е.

n n

NE ij . i 1 j i

60