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

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

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

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

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

5. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001. 304 с.

6. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ, 1992. 262 с.

7. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979. 272 с.

8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984. 240 с.

ОГЛАВЛЕНИЕ

Введение				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.	Плоские и планарные графы		126
		4.13.1.	Формула Эйлера	127
		4.13.2.	Критерии анализа планарности	129
		4.13.3.	Алгоритм укладки графа на плоскости	130
			Задачи и упражнения	135
5.	Разрешимые и неразрешимые проблемы			140
Библиографический список

154