А.В. Бирюков Дискретная математика

Министерство образования Российской Федерации Государственное учреждение

Кузбасский государственный технический университет Кафедра высшей математики

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические указания к изучению соответствующего раздела программы курса математики для

студентов всех направлений

Составитель А.В. Бирюков

Утверждены на заседании кафедры Протокол № 1 от 27.08.01

Рекомендованы к печати методической комиссией направления 550100 Протокол № 6 от 29.10.01

Электронная копия находится в библиотеке главного корпуса ГУ КузГТУ

Кемерово 2001

1. Элементы комбинаторики 1.1. Алгебра множеств

Пусть А – множество элементов произвольной природы. Принадлежность элемента Х множеству А обозначают символом Х А.

Если элемент Z не принадлежит А, то пишут Z A.

Множество без элементов называют пустым и обозначают через. Если все элементы А принадлежат множеству В, то А называют подмножеством В и употребляют символ включения А В.

Объединение множеств А и В, обозначаемое символом А В, есть множество, каждый элемент которого принадлежит А или В.

Пересечение множеств А ∩ В состоит из элементов, принадлежащих А и В.

Разность множеств обозначается через А \ В и состоит из элементов, принадлежащих множеству А, но не принадлежащих множеству В.

Если А В, то множество В \ А называют дополнением А до В. Очевидно, что в этом случае А ∩ (В \ А) = , А (В \ А) = В.

Декартовым произведением А и В называется множество, обозначаемое символом А × В и состоящее из всех упорядоченных пар

(а, в), где а А, в В.

Примеры. Пусть А = (1,2,3), В = (3,4). Тогда А В = (1,2,3,4); А ∩ В = (3); А \ В = (1,2); А × В = ( 1,3; 1,4; 2,3; 2,4; 3,3; 3,4).

1.2. Перестановки и сочетания

Число всевозможных перестановок элементов n – элементного множества равно n! = 1 2 3 n. Например, для трехэлементного

множества (1, 2, 3) число всех переустановок элементов равно 3! = 6.

Это переустановки вида: (1, 2, 3); (1, 3, 2); (2, 1, 3); (2, 3, 1); (3, 1, 2); (3, 2, 1).

Для больших значений n можно использовать приближенную формулу Стирлинга:

n! = (n / e)n (2 π n)1/2,

где е ≈ 2,71828.

1

Рассмотрим все К – элементные подмножества n – элементного множества . Их число, обозначаемое через Ckn , называется числом сочетаний из n по К и составляет

Ckn = n! / К! (n - К) !

Например, число сочетаний из трех элементов (1, 2, 3) по два равно C32 = 3! / 2! 1! = 6 / 2 = 3. Это сочетания вида: (1,2); (1,3);

(2, 3).

Сочетания используются при изучении бинома Ньютона:

n	аn-к вк ,
(а + в)n = ∑Скn
к=0

где Con = Chn = 1. Полагая здесь а= в= 1, получим:

∑n Скn = 2n,

к=0

т.е. число всех подмножеств n – элементного множества (включая и само множество) равно 2n.

2.Графы

2.1.Определения и примеры

Рассмотрим n – элементное множество V = (X1, X2, …, Xn) и множество М, состоящее из всех двухэлементных подмножеств V. Если задано произвольное подмножество Е М, то пара (V, Е) назы-

вается графом порядка n.

Элементы множества V называются вершинами графа, а элементы множества Е – ребрами графа. Если у графа n вершин и m ре-

бер, то его называют (n, m) – графом. Графы удобно изображать в виде рисунков, состоящих из точек (вершин) и линий (ребер), соединяющих некоторые из точек. На рис.1 изображен (5,6) – граф с вер-

шинами 1, 2, 3, 4, 5 и ребрами (1, 2); (1, 4); (1, 5); (4, 5); (2, 4); (2, 3).

2

5		4
1	2	3

Рис.1

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

Если вершина является общей для t ребер, то число t называется степенью этой вершины. У графа, изображенного на рис.1, вершины 1, 2, 3, 4, 5 имеют степени соответственно 3, 3, 1, 3, 2.

Граф называется полным, если любые две его вершины соединены ребром, т.е. являются смежными. В этом случае Е = М. Пол-

ный граф с n вершинами обозначается через Кn. Он имеет

C2n = n (n - 1) / 2 ребер. На рис. 2 и 3 изображены полные графы К4

и К5.

4	3
	5	3
1	2

Рис.2	Рис. 3
Чередующаяся последовательность вершин и ребер графа X1,
а1, X2, а2, …, в которой аi = (Xi, Xi + 1),	называется маршрутом, со-

единяющим вершины X1, X2, X3, … . Число ребер аi в маршруте называется его длиной. Например, на рис. 2 маршрутами, соединяющи-

ми вершины 1 и 4, являются: 1) (1, 4); 2) (1, 3); (3, 4); 3) (1, 2); (2, 4); 4) (1, 2); (2, 3); (3, 4). Длины этих маршрутов равны соответственно

1, 2, 2, 3.

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

3

лом, а циклическая простая цепь – простым циклом. Простая цепь и

простой цикл длины m обозначается соответственно через Рm и Сm. Граф Н называется подграфом графа G, если все его вершины и ребра принадлежат графу G. Очевидно, что любую цепь графа можно

рассматривать как его подграф.

2.2. Связность

Граф называется связным, если любые две его вершины соединены маршрутом. Связный граф без циклов называется деревом. Подграф, который содержит все вершины графа G и является деревом, называется остовом графа G. На рис. 4 и 5 изображены (5, 7) – граф и его остов.

			5		4
5		4
1	2	3	1	2	3

Рис.4

Рис.5

Мостом называется ребро, удаление которого делает граф несвязным. Например, удаление ребра (2, 3) у графа на рис.4 делает его несвязным, состоящим из двух компонент: полного графа К4 и вершины 3. Если удаление некоторой вершины делает граф несвязным, то она называется точкой сочленения.

В связном графе длина кратчайшего маршрута, соединяющего две вершины Xi и Xj, называется расстоянием между этими вершинами и обозначается через d (Xi , Xj). Эксцентриситетом вершины называется максимальное расстояние между ней и остальными вершинами. Вершину с минимальным эксцентриситетом называют центральной, а множество таких вершин – центром графа. Например, у графа на рис. 6 эксцентриситеты вершин 1, 2, 3, 4, 5 равны соответственно 3, 2, 2, 3, 3. Следовательно, центр графа образуют вершины 2 и 3.

4

1

4

2 5 3

Рис. 6

2.3. Обходы графов

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

Имеет место следующая теорема (Эйлер, 1736г.) : связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны. Для эйлерова графа, изображенного на рис.7, эйлеров цикл проходит через вершины 1, 2, 3, 4, 5, 6, 4, 2, 6, 1.

Рис.7

Эйлеров цикл можно построить с помощью алгоритма Флери. Начиная с произвольной вершины X0, присваиваем произвольному

ребру (X0, X1) номер 1. Удаляем это ребро и переходим в вершину

X1. Пусть уже построен маршрут X0, X1, … , Xк и пусть G′ – граф, полученный из графа G удалением всех ребер этого маршрута. Выби-

раем в G′ любое ребро (Xк , Xк+1). При этом мост выбираем лишь в том случае, когда нет других возможностей. Алгоритм заканчивается, когда удалены все ребра. Построенная последовательность ребер и есть эйлеров цикл.

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

5

же называется гамильтоновым. На рис. 8 изображен гамильтонов граф, содержащий простой цикл 1, 2, 6, 7, 3, 4, 5, 1.

23

1
					6
																																																			7																								4

5

Рис. 8

2.4.Раскраски

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

Правильная К-раскраска вершин графа состоит в окрашивании каждой его вершины в один из К цветов, при этом смежные вершины должны быть окрашены в различный цвет. Минимально возможное значение К для правильной К-цветной раскраски вершин графа G называется хроматическим числом этого графа и обозначается через

χ(G). При этом сама раскраска называется минимальной. На рис. 9

изображен (8, 12) – граф, у которого, как нетрудно убедиться, хроматическое число равно 4.

5

4	7

3	6

8

2

1

Рис. 9

6

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

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

ется через χ′(G) .

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

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

3. Дискретная оптимизация

Общая задача оптимизации состоит в поиске экстремума функции, заданной на некотором множестве X. Если X – область в евклидовом пространстве, а функция дифференцируема, то эта задача решается методами анализа. Однако многие прикладные проблемы сводятся к выбору оптимального решения из конечного числа вариантов. Так возникает задача дискретной оптимизации: для функции

f(x), заданной на конечном множестве X, найти элемент X0 X, на котором функция принимает наименьшее (или наибольшее) значение. Функцию f(x) обычно называют целевой функцией, элементы множества X – допустимыми решениями, а элемент X0 - оптимальным решением. Ниже приведены некоторые характерные задачи дискретной оптимизации.

7

1) Остов минимального веса

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

Задача: для связного взвешенного графа найти его остов минимального веса. Решение этой задачи можно найти с помощью алгоритма Прима: выберем ребро l1 с наименьшим весом; среди всех ребер, соединяющих вершины ребра l1 с остальными, выберем ребро l2 с наименьшим весом и т.д. Алгоритм заканчивается, когда будет построен остов. На рис. 10 изображен взвешенный (6, 8) – граф с отмеченными весами ребер и его остов минимального веса.

3	8	2		3	2
	5
			1	5	1
6	4	7			4

Рис. 10

2) Кратчайший путь

Пусть имеется связный взвешенный граф. Будем интерпретировать вес каждого ребра как его длину. Задача состоит в отыскании

кратчайшего пути, соединяющего две фиксированные вершины а и

в.

Алгоритм Дейкстра

Проследим действие алгоритма на конкретном примере. На рис. 11 изображен связный взвешенный (8, 13) – граф с фиксирован-

ными вершинами а = Х1 и в = Х8. Требуется найти кратчайший путь от адо в.

8

Х2	Х4	Х6
Х1		Х8
Х3	Х5	Х7
	Рис.11

Ниже приведена рабочая вспомогательная таблица.

	Х1			Х2			Х3					Х4			Х5			Х6					Х7					Х8
		0		∞			∞					∞			∞					∞					∞				∞
Х1	0			7			2					∞			∞					∞					∞				∞
	0			7								∞			∞					∞					∞				∞
								2
Х3	0			5								8			5					∞					∞				∞
								2
	0											8			5					∞					∞				∞
					5			2
Х2	0											8			5					∞					∞				∞
					5				2
	0											8								∞					∞				∞
									2
					5											5
Х5	0											8								∞			15						∞
									2
					5											5
	0																			∞			15						∞
									2
					5								8			5
Х4	0																	11					15						∞
									2
					5								8			5
	0																						15						∞
									2
					5								8			5			11
Х6	0																						15					18
					5				2				8			5				11
	0																											18
									2
					5								8			5			11					15
Х7	0																											18
									2
					5								8			5			11					15
	0								2
					5								8			5			11						15				18

Начало пути Х1 назовем активной вершиной с постоянной мет-

кой 0. Расстояние от Х1 до смежных вершин Х2 и Х3 имеют временные метки 7 и 2, а расстояния до остальных вершин помечены симво-

9