ДМ_Конспект

Пункт 3.1. Истоку (вершине №1) присвоить метку «0»

	2			φ = 0	3
				С = 2
							С = 2
φ = 0				С = 3
							φ = 0
С = 1
				φ = 0
1	С = 2				С = 3			6
					φ = 0
М = 0	φ = 0
С = 4							С = 1
φ = 0							φ = 0
	4				5
	Рисунок 23.14
Пункт 3.2. Прямое	помечивание: Пусть w							– непомеченная, а v –
помеченная вершины. Тогда вершине w Г v ,								такой	что (v, w) c(v, w)
присвоить метку, равную номеру вершины v , а дуге								v, w	– знак «+».

	М = 1					φ = 0			М = 2
						С = 2	3
	2
φ = 0						С = 3			С = 2
									φ = 0
С = 1
						φ = 0
										М = 3
1	С = 2						С = 3			6
							φ = 0
М = 0	φ = 0
С = 4									С = 1
φ = 0									φ = 0
	4						5
	М = 1								М = 2
		Рисунок 23.15
Обратное помечивание		вершине					w Г v ,			такой	что (v, w) 0 ,
присвоить метку равную номеру вершины v , а другие v, w											– знак «-». Таких
вершин на этом шаге не найдено:
	М = 1					φ = 0		М = 2
	2					С = 2	3
φ = 0						С = 3			С = 2
									φ = 0
С = 1
						φ = 0
										М = 3
1	С = 2						С = 3			6
							φ = 0
М = 0	φ = 0
С = 4									С = 1
φ = 0									φ = 0
	4						5
	М = 1								М = 2
						241

Рисунок 23.16 Пункт 4. Вершина №6 (сток) получила метку. Значит, максимальный

поток еще не найден. Продолжаем решение.

М = 1				φ = 0		М = 2
	2			С = 2	3
φ = 0				С = 3		С = 2
						φ = 0
С = 1
				φ = 0
							М = 3
1	С = 2				С = 3		6
					φ = 0
М = 0	φ = 0
С = 4						С = 1
φ = 0						φ = 0
	4				5
	М = 1					М = 2
	Рисунок 23.17
Пункт 5. Рассмотрим	последовательность						вершин v6 ,vi ,...,vi ,v1 ,

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

: v6,v3,v2,v1 .

	М = 1			φ = 0		М = 2
	2			С = 2	3
φ = 0							С = 2
				С = 3
С = 1							φ = 0
				φ = 0
							М = 3
1	С = 2				С = 3		6
					φ = 0
М = 0	φ = 0
С = 4							С = 1
φ = 0							φ = 0
	4				5
	М = 1					М = 2

Рисунок 23.18

Зададим новый поток по правилу:

Если ;

Если ( имеет знак «+») K ;

Если ( имеет знак «-») K ;

K1 min c , , имеет знак «+»

K 2 min , , имеет знак «-»

В нашем случае K1 1, K 1, новый поток показан на рисунке. Переход к пункту 3.1:

242

Пункт 3.1 (вторая итерация). Вершине №1 (истоку) присваиваем метку

«0»:

			φ = 1
	2		С = 2			3
φ = 1						С = 2
			С = 3			φ = 1
С = 1
			φ = 0
1	С = 2			С = 3		6
				φ = 0
М = 0	φ = 0
С = 4						С = 1
φ = 0						φ = 0
	4			5

Рисунок 23.19

Пункт 3.2 (вторая итерация). Прямое помечивание:

			φ = 1	М = 4
	2		С = 2			3
φ = 1						С = 2
			С = 3			φ = 1
С = 1
			φ = 0
						+
1	С = 2			С = 3		6
				φ = 0		М = 3
М = 0	φ = 0		+
	+
С = 4						С = 1
φ = 0						φ = 0
	4			5

М = 1

Рисунок 23.20

Обратное помечивание: соответствующих вершин не найдено.

			φ = 1	М = 4
	2		С = 2	3
φ = 1						С = 2
			С = 3			φ = 1
С = 1
			φ = 0
1	С = 2			С = 3		6
				φ = 0		М = 3
М = 0	φ = 0
С = 4						С = 1
φ = 0						φ = 0

45

М= 1

Рисунок 23.21 Пункт 4 (вторая итерация). Вершина №6 (сток) получила метку. Значит,

максимальный поток еще не найден. Продолжаем решение:

243

	М = 5		φ = 1	М = 4
	2		С = 2	3
φ = 1							С = 2
			С = 3				φ = 1
С = 1
			φ = 0
1	С = 2			С = 3			6
				φ = 0			М = 3
М = 0	φ = 0
С = 4							С = 1
φ = 0							φ = 0
	4			5

М = 1	М = 6

Рисунок 23.22

Пункт 5 (вторая итерация). v6 ,v3,v2 ,v1 ; K1 1, K 1. Задаем новый поток:

	М = 5		φ = 1	М = 4
	2		С = 2	3
φ = 1							С = 2
			С = 3				φ = 2
С = 1
			φ = 0
1	С = 2			С = 3			6
				φ = 1			М = 3
М = 0	φ = 0
С = 4							С = 1
φ = 1							φ = 0
	4			5

М = 1	М = 6

Рисунок 23.23 Пункт 3.1 (третья итерация). Истоку (вершине №1) присвоить метку «0».

			φ = 1
	2		С = 2			3
φ = 1						С = 2
			С = 3			φ = 2
С = 1
			φ = 0
1	С = 2			С = 3		6
				φ = 1
М = 0	φ = 0
С = 4						С = 1
φ = 1						φ = 0
	4			5

Рисунок 23.24 Пункт 3.2 (третья итерация). Прямое и обратное помечивание:

244

М = 3

2

φ= 1

С= 1

1	С = 2
М = 0	φ = 0
	+
С = 4
φ = 1

4

М = 1

φ = 1	М = 4
С = 2	3
-
	С = 2
С = 3	φ = 2
φ = 0 +
С = 3	6
φ = 1	М = 5

+

+

С = 1 φ = 0

5

М = 2

Рисунок 23.25

Пункт 4 (третья итерация). Вершина №6 получила метку. Значит, максимальный поток еще не найден. Продолжаем решение.

	М = 3				φ = 1			М = 4
	2				С = 2	3
φ = 1								С = 2
					С = 3			φ = 2
С = 1
					φ = 0
1	С = 2					С = 3			6
						φ = 1			М = 5
М = 0	φ = 0
С = 4								С = 1
φ = 1								φ = 0
	4					5
	М = 1							М = 2
	Рисунок 23.26
Пункт 5 (третья итерация). v6 ,v5,v2 ,v3,v4 ,v1 ;										K1 1, K 2 1, K 1;
Задаем новый поток:
	М = 3				φ = 1			М = 4
	2				С = 2	3
φ = 1								С = 2
					С = 3			φ = 2
С = 1
					φ = 0
1	С = 2					С = 3			6
						φ = 1			М = 5
М = 0	φ = 0
С = 4								С = 1
φ = 1								φ = 0
	4					5
	М = 1							М = 2

Рисунок 23.27

Пункт 3.1 (четвертая итерация). Исток (вершина №1) получает метку «0».

245

			φ = 1
	2		С = 2			3
φ = 1						С = 2
			С = 3			φ = 2
С = 1
			φ = 0
1	С = 2			С = 3		6
				φ = 1
М = 0	φ = 0
С = 4						С = 1
φ = 1						φ = 0
	4			5

Рисунок 23.28

Пункт 3.2 (четвертая итерация). Прямое помечивание:

			φ = 1		М = 4
	2		С = 2	3
φ = 1						С = 2
			С = 3			φ = 2
С = 1
			φ = 0
1	С = 2			С = 3		6
				φ = 1
М = 0	φ = 0
	+		+
С = 4						С = 1
φ = 1						φ = 0

45

М= 1

Рисунок 23.29 Обратное помечивание: соответствующих вершин не найдено.

			φ = 1		М = 4
	2		С = 2	3
φ = 1						С = 2
			С = 3			φ = 2
С = 1
			φ = 0
1	С = 2			С = 3		6
				φ = 1
М = 0	φ = 0
	+		+
С = 4						С = 1
φ = 1						φ = 0

45

М= 1

Рисунок 23.30 Пункт 4 (четвертая итерация). Вершин №6 (сток) не получила метку.

Значит, задача решена. Максимальный поток найден 2 .

			φ = 1
	2		С = 2			3
φ = 1						С = 2
			С = 3			φ = 2
С = 1
			φ = 0
1	С = 2			С = 3		6
				φ = 1
	φ = 0
С = 4						С = 1
φ = 1						φ = 0
	4			5

Рисунок 23.40

246

23.5 Контрольные вопросы и задания

1.Что такое транспортная сеть.

2.Поясните понятие пропускной способности дуг.

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

4.Приведите и поясните особенности использования алгоритма ФордаФалкерсона.

247

УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ

Основная литература

1.Бондаренко, М. Ф. Комп’ютерна дискретна математика [Текст] : підручник / М. Ф. Бондаренко, Н. В. Білоус, А. Г. Руткас. – Харків: «Компанія СМІТ», 2004. – 480 с. (існує електронний варіант).

2.Капітонова, Ю. В. Основи дискретної математики [Текст] / Ю. В. Капітонова, С. Л. Кривий, О. А. Летичевський, Г. М. Луцький, М. К. Печорін – Київ: Наукова думка, 2002. – 578 с.

3.Тевяшев, А. Д. Основы дискретной математики в примерах и задачах [Текст] : учеб. пособие для вузов / А. Д. Тевяшев, И. Г. Гусарова. – Харьков:

ХНУРЭ, 2003. – 272 с.

4.Бардачев, Ю. Н. Основы дискретной математики [Текст] : учебное пособие / Ю. Н. Бардачев, Н. А. Соколова, В. Е. Ходаков; под редакцией В. Е. Ходакова. – Херсон: ХГТУ, 2000. – 356 с. (існує електронний варіант).

5.Шапорев, С. Д. Дискретная математика. Курс лекций и практических занятий [Текст] / С. Д. Шапорев – СПб.: БХВ-Петербург, 2006. – 400 с. (існує електронний варіант).

6.Кузнецов, О. П. Дискретная математика для инженера [Текст] / О. П. Кузнецов, Г. М. Адельсон-Вельский. – М.: Энергоатомиздат, 1988. – 480 с.

7.Сигорский, В. П. Математический аппарат инженера [Текст] / В. П. Сигорский. – Киев: Техніка, 1977. – 768 с. (існує електронний варіант).

8.Яблонский, С. В. Введение в дискретную математику [Текст] / С. В. Яблонский. – М.: Наука, 1986. – 384 с.

9.Горбатов, В.А. Основы дискретной математики [Текст] / В. А. Горбатов

–М.: Высшая школа, 1986. – 312с.

10.Харари, Ф. Теория графов [Текст] / Ф. Харари. – М.: Мир, 1973. – 304 с.

11.Глускин, Л.М. Задачи и алгоритмы комбинаторики и теории графов [Текст] / Л. М. Глускин, В. Я. Шварц, Л. А. Шор. – Донецк: Изд-во ДПИ, 1982.

–110с.

12.Білоус, Н.В. Основи комбінаторного аналізу. [Текст] : навч. посібник / Н. В. Білоус, З. В. Дудар, Н. С. Лєсна, І. Ю. Шубін. – Харків: ХТУРЕ, 1999. – 96 с.

13.Бондаренко, М. Ф. Збірник тестових завдань з дискретної математики [Текст] / М. Ф. Бондаренко, Н. В. Білоус, І. Ю. Шубін. – Харків: ХТУРЕ, 2000. – 156 с. (існує електронний варіант).

248

Дополнительная литература

14.Новиков, Ф. А. Дискретная математика для программистов [Текст] / Ф. А. Новиков. – СПб: Питер, 2001. – 304 с. (існує електронний варіант).

15.Донской, В.И. Дискретная математика [Текст] / В. И. Донской. – Симферополь: СОНАТ, 2000. – 360 с.

16.Андерсон, Дж. А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон. – М.: Издательский дом «Вильямс», 2003. – 960 с.

17.Виленкин, Н.Я. Комбинаторика [Текст] / Н. Я. Виленкин. – М.: Наука,

1969. – 328 с.

18.Белоус, Н.В. Тесты. Физика. Математическая логика [Текст] : Навч. посібник / Н. В. Белоус, Е. Е. Гетьманова, З. В. Дударь, В. Ф. Захарченко, М. А. Красноголовец, Н. С. Лесная, В. В. Семенец, В. А. Стороженко, А. А. Харьковская. – Харків: ХТУРЕ, 1998. – 152 с.

19.Капитонова, Ю. В. Лекции по дискретной математике [Текст] / Ю. В. Капитонова, С. Л. Кривой, А. А. Летичевский, Г. М. Луцкий. – СПб.: БХВПетербург, 2004. – 624 с.

Методические указания

20.Методичні вказівки до практичних робіт з дисципліни «Дискретна математика» (Частина 1) для студентів усіх форм навчання напряму 6.050101 – комп’ютерні науки / Упоряд. Н. В. Васильцова, Л.Е. Чала – Харків: ХНУРЕ,

2012. – 68 с.

21.Методичні вказівки до самостійної роботи з дисципліни «Дискретна математика» для студентів усіх форм навчання напряму 6.050101 – комп’ютерні науки / Упоряд. Н. В. Васильцова, Л.Е. Чала – Харків: ХНУРЕ, 2014. (навчальне електронне видання).

249

ГЛОССАРИЙ ТЕРМИНОВ ДИСЦИПЛИНЫ

1. Основы теории множеств Алгебра множеств.
Алгебра
Алгебра множество M (несущее множество,	носитель алгебры) вместе с
заданной на нем совокупностью операций	1 , 2 ,...,m ,...	(сигнатурой),
т.е. система A M ; 1 , ...,m , ... .

Алгебра множеств

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

Бесконечное множество

Множество, которое содержит бесконечное число элементов.

Бинарная операция

Операция, заданная на некотором множестве, называется бинарной, если она действует на два элемента этого множества и еѐ результатом является элемент этого же множества.

Булеан множества

Множество всех подмножеств множества A , обозначаемое (А) (или 2 A ). (То же, что и множество-степень).

Двойственные соотношения

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

Диаграммы Эйлера-Венна

Используются для наглядного представления отношений между подмножествами универсального множества U .

Дизъюнктивная сумма

Множество, состоящее из всех элементов множества A , не принадлежащих множеству B , и всех элементов множества B , не принадлежащих множеству A , и не содержащее никаких других элементов.

(То же, что и симметрическая разность). Дополнение (теоретико-множественная операция)

Множество U A называется дополнением множества A , т.е. это множество элементов универсума, которые не принадлежат A .

(То же, что и отрицание).

Класс

Множество, элементами которого являются множества. (То же, что и семейство).

Конечное множество

Множество, содержащее конечное число элементов. 250