Конспект_лекций_по_курсу_Дискретная_математика

Конечный индекс этой дуги j заменяется индексом j', равным сумме началь-

ного индекса и меры ребра:

j' = i + (xi, xj).

Очевидно, что j'< j, т.е. в результате выполнения этой операции значение индекса конечной вершины убывает.

Эта процедура повторяется до тех пор, пока в графе имеются ребра, удовле-

творяющие условию (2.2).

Можно доказать, что через конечное число шагов процесс уменьшения ин-

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

(2.2). При этом установившиеся значения индексов i равны длинам кратчайших путей от вершины x0 до вершины xi, в частности n определяет длину кратчайшего пути от x0 до xn.

3-й этап. Строится кратчайший путь между вершинами x0 и xn. Построение ведется в обратном направлении, т.е. от вершины xn к вершине x0. Для этого сна-

чала ищется вершина (обозначим ее xр1), которая была последней использована для уменьшения индекса вершины xn. Из описания предыдущего этапа следует,

что разность индексов этих вершин равна мере связывающего их ребра. Далее аналогично ищется вершина xр2, которая последней была использована для уменьшения индекса вершины xр1, и т.д. Через конечное число шагов приходим в начальную вершину x0. Вершины, найденные в результате этой процедуры, взятые в противоположном порядке, и образуют искомый кратчайший путь из x0 в xn.

Этот алгоритм пригоден как для ориентированных, так и для неориентиро-

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

Пример 2.12. Ниже, на рис. 2.8, приведен пример поиска кратчайшего пути в графе из вершины x0 в вершину x7. Последовательно получаемые на втором этапе индексы вершин приведены в скобках около каждой вершины. Следует иметь в виду, что эти последовательности зависят от того порядка, в котором рассматри-

-51-

ваются ребра графа, удовлетворяющие условию (2.2), но конечный результат бу-

дет одним и тем же.

		x1( , 4)		x5( , 7)
				6
	4	1	8	2	1
x0	3		2	6	x7( , 8)
(0)	3	x2( , 3)		x4( , 5)
		8		9	2

x3( , 3) 4 x6( , 7)

Рис. 2.8

Последней для уменьшения индекса вершины x7 была использована вершина x5 (как нетрудно убедиться, разность индексов этих вершин (8 – 7) как раз равна мере соединяющего их ребра (x5, x7)). Индекс вершины x5 последний раз был уменьшен из вершины x4 (7 – 5 = 2), вершины x4 – из вершины x2, вершины x2 – из вершины x0. Таким образом, кратчайший путь из вершины x0 в вершину x7 прохо-

дит через вершины x0, x2, x4, x5, x7 и имеет длину 8.

Поиск длиннейшего пути.

1-й этап. Всем вершинам присваиваются начальные индексы, равные 0.

2-й этап. Ищется дуга (xi, xj), для которой разность между конечным и началь-

ным индексом меньше меры этой дуги:

j i < (xi, xj) (2.3)

Конечный индекс этой дуги j заменяется индексом j', равным сумме началь-

ного индекса и меры ребра:

j' = i + (xi, xj).

Очевидно, что j' > j, т.е. в результате выполнения этой операции значение индекса конечной вершины возрастает.

Эта процедура повторяется до тех пор, пока в графе имеются ребра, удовле-

творяющие условию (2.3).

Можно доказать, что если в графе нет контуров, то через конечное число ша-

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

-52-

удовлетворяющих условию (2.3). При этом установившиеся значения индексов i

равны длинам длиннейших путей от вершины x0 до вершины xi, в частности n оп-

ределяет длину длиннейшего пути от x0 до xn.

3-й этап. Строится длиннейший путь между вершинами x0 и xn. Построение ведется в обратном направлении, т.е. от вершины xn к вершине x0. Для этого сна-

чала ищется вершина (обозначим ее xр1), которая была последней использована для увеличения индекса вершины xn. Из описания предыдущего этапа следует, что разность индексов этих вершин равна мере связывающего их ребра. Далее анало-

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

положном порядке, и образуют искомый длиннейший путь из x0 в xn.

Внимание! Длиннейший путь можно искать только в ориентированных гра-

фах, не имеющих контуров!

Пример 2.13. Ниже, на рис. 2.9, приведен пример поиска длиннейшего пути

в графе. Последовательно получаемые на втором этапе индексы вершин приведе-

ны в скобках около каждой вершины.

		x1(0, 4)		x5(0, 10, 28)
			6
	4	1	8	2	1
x0	3	2		6	x7(0, 32)
(0)	3	x2(0, 3, 5)		x4(0, 26)
		8		9	2
			4
		x3(0, 3, 13)		x6(0, 17)

Рис. 2.9

Последней для увеличения индекса вершины x7 была использована вершина x4

(разность индексов 32 – 26 равна мере 6), для x4 вершина x6 (26 – 17 = 9), для x6 x3 (17 – 13 = 4), для x3 x2 (13 – 5 = 8), для x2 x1 (5 – 1 = 4), для x1 x0 (4 – 0 = 4).

Таким образом, длиннейший путь из x0 в x7 имеет вид: x0, x1, x2, x3, x6, x4, x7, и его длина равна 32.

-53-

3.КОМБИНАТОРИКА

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

Комбинаторика – это раздел математики, изучающий вопросы о том, сколь-

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

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

В соответствии с этим определением различают два вида комбинаторных за-

дач: пересчет и перечисление. Мы здесь будем рассматривать только задачи пе-

ресчета.

Простейшие примеры комбинаций: распределение нового набора студентов,

поступивших в университет, по учебным группам; набор гирь, с помощью которо-

го можно взвесить некоторый товар; состав профсоюзного комитета профсоюзной организации; набор ребер, с помощью которого можно построить дерево на задан-

ном множестве вершин, и т.д.

Комбинации объектов в комбинаторике принято называть расстановками.

Расстановка – это просто некоторое множество объектов. Отличие от обычного множества состоит в том, что при определенных обстоятельствах, оговариваемых или подразумеваемых в условии задачи, некоторые объекты, входящие в расста-

новку, могут быть неразличимы между собой с точки зрения рассматриваемой задачи, т.е. в расстановке объекты могут повторяться, тогда как в обычных множе-

ствах все элементы считаются различными. Пример расстановки с повторениями:

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

Расстановка, состоящая из k объектов, называется k-расстановкой.

Расстановка, для которой имеет значение порядок следования объектов, на-

зывается размещением.

-54-

Например, полосатый флаг можно рассматривать как расстановку из некото-

рого множества полос цветных материалов, а так как порядок следования этих по-

лос имеет значение, то эта расстановка является размещением.

Если для составления размещения нужно выбрать k объектов из некоторого множества, содержащего n объектов, то такое размещение называется k-размещением из n элементов или размещением из n элементов по k.

Если в размещение включаются все n имеющихся в нашем распоряжении элементов, то такое размещение называется перестановкой из n элементов или n-перестановкой.

Например, профсоюзная конференция выбрала профсоюзный комитет, кото-

рый затем распределяет должности между членами комитета. Так как в распреде-

лении участвуют все члены комитета, и имеет значение, кому какая должность на-

значена (т.е. имеет значение порядок распределения членов комитета по должно-

стям), то профсоюзный комитет с точки зрения комбинаторики можно рассматри-

вать как перестановку.

Расстановка, для которой не имеет значения порядок следования элементов,

называется сочетанием.

Например, для состава учебной группы не имеет значения, в каком порядке перечислены студенты в журнале, поэтому учебная группа с точки зрения комби-

наторики представляет собой сочетание.

Если для составления сочетания нужно выбрать k объектов из некоторого множества, содержащего n объектов, то такое сочетание называется k-сочетанием из n элементов или сочетанием из n элементов по k.

3.2. Общие правила комбинаторики

Эти правила используются для подсчета числа расстановок различного типа.

Таких правил два: правило суммы и правило произведения.

Правило суммы представляет собой формулировку того очевидного факта,

что если некоторое конечное множество (в данном случае множество всех рас-

сматриваемых расстановок) можно разбить на непересекающиеся подмножества,

-55-

то общее количество элементов множества равно сумме количеств элементов, вхо-

дящих в отдельные подмножества.

Обычно этим правилом пользуются, если множество всех расстановок, кото-

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

Правило произведения применяется в тех случаях, когда выбор некоторого количества (k) объектов можно производить последовательно шаг за шагом. Если при этом на первом шаге имеется n1 вариантов выбора, на втором – n2 вариантов выбора, ..., на k-ом – nk вариантов выбора, то общее количество вариантов выбора,

а значит и общее количество таких k-расстановок равно произведению n1 n2 ... nk.

Пример 3.1. Имеется 5 кусков материала разных цветов. Нужно сшить из них полосатый флаг, состоящий из 3 разноцветных полос. Сколько различных флагов можно сшить?

Решение. Последовательность составления флага можно разбить на 3 шага, на каждом из которых выбирается материал для соответствующей полосы флага. При выборе материала для первой полосы имеется, очевидно, 5 возможностей (n1 = 5).

После того как материал для первой полосы выбран, для выбора второй полосы остается только 4 возможности (n2 = 4). После выбора первых двух полос для вы-

бора третьей полосы остается 3 возможности (n3 = 3). По правилу произведения получаем, что общее количество вариантов выбора, то есть общее количество раз-

личных флагов, которые можно сшить из имеющихся материалов, равно

5 4 3=60.

3.3.Простейшие задачи пересчета

3.3.1.Определение числа k-размещений из n элементов

Число таких размещений принято обозначать Ank . При составлении таких размещений в нашем распоряжении имеется n различных элементов, из которых

-56-

нужно выбрать k элементов. При выборе первого элемента у нас имеется, очевид-

но, n возможностей, при выборе второго (n – 1) возможность (так как из имею-

щихся n элементов один уже использован на первом шаге), при выборе третьего элемента (n – 2) возможности, ..., при выборе k-го элемента (n – k + 1) возмож-

ность. По правилу произведения получаем:

		Ak n(n 1)(n 2)...(n k 1)						(3.1)
		n
	Умножим и разделим правую часть выражения (3.1) на (n – k)!:
	Ak n(n 1)(n 2)...(n k 1)		(n k)!			n!		(3.2)
			(n k)!			(n k)!
	n

Пример 3.2. Рассмотрим задачу с флагами из примера 3.1. Флаг в этом при-

мере можно рассматривать как размещение из 5 элементов по 3. Общее количество таких размещений по формуле (3.2)

A3			5!			1 2 3		4 6	60.
5	(5		3)!			1	2

3.3.2. Определение числа k-размещений из элементов n типов с повторениями Имеются элементы n типов. Количество элементов каждого типа не ограни-

чено. Из этих элементов нужно выбрать k элементов, причем в расстановке можно использовать однотипные элементы. Подсчитаем общее количество таких расста-

новок (его принято обозначать Ank ).

При составлении таких расстановок число вариантов выбора на каждом шаге остается одним и тем же и равным n (так как число объектов каждого типа по ус-

ловию задачи не ограничено и объекты в расстановке могут повторяться, т.е. объ-

ект, выбранный на каком-то из предыдущих шагов, можно выбрать снова). Таким образом,

	k n n ... n nk
A		(3.3)

n
	k раз

-57-

Пример 3.3. Как известно, азбука Морзе состоит из комбинаций элементов двух типов: точек и тире. Причем комбинация может включать от одного до 5

элементов, которые могут повторяться. Определить, сколько различных комбина-

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

Решение. Комбинацию элементов азбуки Морзе можно рассматривать как размещение из элементов 2 типов по k, где k = 1, 2, 3, 4, 5. Все комбинации симво-

лов азбуки Морзе можно разбить на 5 непересекающихся подмножеств по количе-

ству символов в комбинации. Следовательно, здесь можно применить правило суммы, а для подсчета числа комбинаций в каждом подмножестве воспользуемся формулой (3.3):

A21 A22 A23 A24 A25 21 22 23 24 25 62.

Этого количества достаточно для представления всех букв русского алфавита,

цифр и знаков препинания. Меньшего количества символов в комбинации было бы недостаточно (например, используя только 4 символа, можно было бы полу-

чить только 30 комбинаций, что достаточно для представления латинского алфа-

вита, ноне хватило бы для цифр, не говоря уже о знаках препинания).

3.3.3. Определение числа n-перестановок

Перестановка есть частный случай размещения, в котором используются все n

имеющихся в нашем распоряжении элементов. Число n-перестановок принято обозначать Pn. Из определения перестановки следует, что число n-перестановок равно числу размещений из n элементов по n:

P An		n!			n!	n!	(3.4)
		(n n)!
n	n			0!

Пример 3.4. Найти число способов расстановки 8 ладей на шахматной доске,

при которых они не бьют друг друга.

Решение. Зашифруем каждую из возможных расстановок восьмизначным числом, поставив в соответствие каждому разряду в этом числе вертикаль шах-

матной доски и записав в этом разряде номер горизонтали, где находится ладья,

-58-

т.е., если в i-ом разряде стоит число j, это значит, что ладья находится на пересе-

чении i-ой вертикали и j-ой горизонтали. Очевидно, что между такими шифрами и способами расстановки существует взаимно однозначное соответствие, так как не только каждую расстановку можно зашифровать таким шифром, но и по любой комбинации из восьми различных цифр от 1 до 8 можно однозначно определить соответствующую расстановку ладей. Следовательно, число расстановок равно числу перестановок из 8 элементов P8 = 8! = 40320.

3.3.4. Определение числа n-перестановок из элементов k типов с повторениями Пусть имеется набор из n объектов k типов, причем k < n. Так как k < n, то не-

которые объекты в наборе должны повторяться. Подсчитаем количество возмож-

ных перестановок из этих объектов, если число объектов 1-го типа равно n1, коли-

чество объектов 2-го типа равно n2, ... , количество объектов k-го типа равно nk.

Если бы все объекты были различны, то общее число перестановок было бы равно n!. На самом деле число перестановок будет меньше, так как, поменяв мес-

тами объекты одного типа, мы не меняем перестановку. Выберем какую-либо кон-

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

aa ...a bb ...b		xx ... x	(3.5)
n	n	n
1	2	k

и будем в ней менять местами между собой объекты одного конкретного типа. Ес-

ли меняются местами объект 1-го типа, то число вариантов обмена будет равно n1!,

если меняются местами объекты 2-го типа, то число вариантов обмена равно n2!,

..., если меняются объекты k-го типа, то число обменов равно nk!. Перестановки внутри каждого типа объектов можно делать независимо друг от друга, поэтому,

по правилу произведения, элементы перестановки (3.5) можно переставлять мес-

тами друг с другом n1!n2! … nk! способами, не меняя фактически перестановку

(3.5). Так как это справедливо и для любого другого расположения элементов, то множество всех n! перестановок распадается на подмножества, состоящие из n1!n2! … nk! одинаковых перестановок каждая. Таким образом, общее число пере-

становок с повторениями описанного типа будет равно:

-59-

P(n1, n2	,...,nk )	n!		(3.6)
		n1!n2!...nk
			!

Пример 3.5. В средние века, когда не было научных журналов, а для издания книг требовались годы, ученые сообщали друг другу результаты своих исследова-

ний в письмах. Иногда, чтобы закрепить свой приоритет на какое-нибудь откры-

тие, они сообщали об этом открытии в виде анаграммы, т.е. формулировали от-

крытие в виде некоторой фразы и переставляли в ней буквы так, чтобы ее нельзя было прочитать, а в случае спора о приоритете открытия расшифровывали эту анаграмму. С точки зрения комбинаторики анаграмма представляет собой пере-

становку с повторениями. Подсчитаем, сколько различных анаграмм можно сде-

лать из букв слова "математика". В это слово, состоящее из 10 букв, входят две бу-

квы "м", три буквы "а", две буквы "т", одна буква "е", одна буква "к" и одна буква

"и". По формуле (3.6) получаем	P(2,3,2,1,1,1)	10!		100800.
		2! 3! 2! 1! 1! 1!

3.3.5.Определение числа k-сочетаний из n элементов

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

	обозначать C k .
	n
	C k	Ak		n!
		n				(3.7)
	n	k! (n k)!k!

Сопоставляя (3.7) и (3.6), нетрудно видеть, что Cnk P(k, n k) .

-60-