Заключение

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

Библиографический список

1. Емеличев В.А. Лекции по теории графов / В.А. Емеличев, О.И. Мельников. М.: Наука, 1990. – 384 с.

2. Кристофидес Н. Теория графов: алгоритмический подход / Н. Кристофидес. М.: Мир, 1978. – 432 с.

3. Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. М.: Мир, 1974. – 520 с.

4. Судоплатов С.В. Элементы дискретной математики: учебник / С.В. Судоплатов, Е.В. Овчинникова. М.: ИНФРА-М, 2002. – 280 с.

5. Леденева Т.М.Специальные главы математики. Дискретная математика: учеб. пособие / Т.М. Леденева. Воронеж: ВГТУ, 1997. – 130 с.

6. Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков. СПб.: Питер, 2004. – 364 с.

7. Тишин В.В. Дискретная математика в примерах и задачах / В.В. Тишин. СПб.: БХВ-Петербург. 2008. – 352 с.

8. Гаврилов Г.П. Задачи и упражнения по дискретной математике: учеб. пособие / Г.П. Гаврилов, А.А. Сапоженко. – 3-е изд., перераб. М.: ФИЗМАТЛИТ, 2005. – 416 с.

9. Лавров И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. М.: ФИЗМАТЛИТ, 2004. – 256 с.

10. Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов. СП.: Лань, 2005. - 400 с.

Оглавление

ВВЕДЕНИЕ				3
1.	ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ			5
	1.1.	Основные понятия и определения теории множеств		5
	1.2.	Операции над множествами и их свойства. Диаграммы Эйлера-Венна		11
	1.3.	Мощность множества		17
	1.4.	Взаимно однозначное соответствие между множествами		18
	1.5.	Счетные и несчетные множества		19
		Задачи и упражнения		23
2.	ЭЛЕМЕНТЫ ТЕОРИИ ОТНОШЕНИЙ			24
	2.1.	Бинарные отношения. Свойства отношений		24
	2.2.	Отношение эквивалентности и разбиения		29
	2.3.	Отношение порядка. Диаграмма Хассе		32
		Задачи и упражнения		37
3.	ФУНКЦИИ, ОТОБРАЖЕНИЯ И ОПЕРАЦИИ			39
4.	ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ			44
	4.1.	Основные понятия и определения теории графов		45
	4.2.	Типы графов		48
	4.3.	Матричные представления графов		53
	4.4.	Представление графов в ЭВМ		56
	4.5.	Операции над графами		59
	4.6.	Метрические характеристики графа. Расстояние в графах		63
	4.7.	Графы с заданной последовательностью степеней		65
	4.8.	Достижимость и связность		70
		4.8.1.	Основные определения	70
		4.8.2.	Матрицы достижимостей и контрдостижимостей	73
		4.8.3.	Нахождение сильных компонент	77
		4.8.4.	Базы и антибазы	82
	4.9.	Независимые и доминирующие множества		84
		4.9.1.	Нахождение всех максимальных независимых множеств	87
	4.10.	Покрытия и раскраски		94
	4.11.	Деревья, остовы и кодеревья		101
		4.11.1.	Основные определения	101
		4.11.2.	Алгортм построения остова неорграфа	105
		4.11.3.	Кратчайшие остовы	108
		4.11.4.	Обходы графа по глубине и ширине	112
		4.11.5.	Упорядоченные и бинарные деревья	115
	4.12.	Эйлеровы циклы. Гамильтонов контур		117
		4.12.1.	Метод Флери построения эйлерова цикла	120
		4.12.2.	Метод перебора Робертса и Флореса для построения гамильтоновых путей и контуров	121
		4.12.3.	Алгебраический метод выделения гамильтоновых путей и контуров	123
	4.13.	Плоские и планарные графы		128
		4.13.1.	Формула Эйлера	129
		4.13.2.	Критерии анализа планарности	131
		4.13.3.	Алгоритм укладки графа на плоскости	132
			Задачи и упражнения	137
5.	АЛГЕБРА ЛОГИКИ			140
	5.1.	Операции над высказываниями		141
	5.2.	Правила записи сложных формул		145
	5.3.	Таблицы истинности		146
	5.4.	Равносильность формул		150
	5.5.	Дизъюнктивные и конъюнктивные нормальные формы		157
		5.5.1.	Аналитический способ приведения к СДНФ	161
		5.5.2.	Табличный способ приведения к СДНФ	162
		5.5.3.	Табличный способ приведения к СКНФ	163
	5.6.	Минимизация булевых функций в классе ДНФ		166
	5.7.	Геометрическое представление булевых функций		172
		5.7.1.	Геометрический метод минимизации булевых функций	175
			Задачи и упражнения	179
6.	РАЗРЕШИМЫЕ И НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ			181
ЗАКЛЮЧЕНИЕ				192
БИБЛИОГРАФИЧЕСКИЙ СПИСОК				193

Учебное издание

Собенина Ольга Валерьевна

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

В авторской редакции

Компьютерный набор О.В. Собениной

Подписано к изданию 20.11.2012.

Уч-изд. л. 11,0.

ФГБОУ ВПО «Воронежский государственный технический университет»