Список литературы

1. Асанов, М.О., Баранский, В.А., Расин, В.В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск, 2001. – 288 с.

2. Ахо, А., Хокпкрофт, Дж., Ульман, Дж. Структуры данных и алгоритмы. – М.: «Вильямс», 2001. – 384 с.

3. Волченков, С.Г., Корнилов, П.А, Белов, Ю.А. Ярославские олимпиады по информатике. – Ярославль: Бином, 2010. – 405 с.

4. Виленкин, Н.Я. Комбинаторика. – М.: Наука, 1969. – 328 с.

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

6. Иванов, Б.Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002. – 288 с.

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

8. Майника, Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981. – 325 с.

9. Мельников, О.И. Занимательные задачи по теории графов. – Минск: Тетрасистемс, 2001. – 144 с.

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

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

12. Уилсон, Р. Введение в теорию графов. – М.: Мир, 1977. – 207 с.

13. Харари, Ф. Теория графов. – М.: Мир, 1973. – 300 с.

14. Шапорев, С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2007. – 400 с.

15. Яблонский, С.В. Введение в дискретную математику. – М.: Высш. шк., 2002. – 384 с.

Использованы задачи с сайта www.zaba.ru.

Дискретная математика 1

(для студентов специальности 050203.62 – «Информатика») 1

Введение 3

Комбинаторика 4

ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ 49

Связность в неориентированных графах 60

Связность ориентированных графов 60

Эйлеров цикл 61

Гамильтонов цикл 62

Турниры 63

ЗАДАЧИ ПО КОМБИНАТОРИКЕ 74

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

Формула включения и исключения 76

Размещения с повторениями 77

Размещения без повторений 79

Перестановки 80

Сочетания 81

Сочетания с повторениями 83

Разные задачи 83

Комбинаторика разбиений 88

Вероятность 91

Бином Ньютона. Полиномиальная формула 94

Рекуррентные соотношения 95

ЗАДАЧИ ПО ТЕОРИИ ГРАФОВ 97

Основные определения и примеры графов 97

Матрицы, ассоциированные с графом 99

Изоморфизм графов 101

Достижимость и связность 102

Циклы 104

105

Алгоритмы обхода связного графа 107

Деревья 108

Двудольные графы 112

Ориентированные графы и мультиграфы 114

Плоские графы 118

Стереографическая проекция 120

Двойственные графы 121

Раскраски графа 122

Список рекомендуемой литературы по теории графов 124

СПИСОК ЛИТЕРАТУРЫ 127

Корнилов Петр Анатольевич

Заводчикова Надежда Ивановна

Прусова Наталия Александровна

Дискретная математика

Редактор Иванова Н.А.

Подписано в печать 25.09.07 Формат бумаги 80х64 1/16

Печ. л. 5.5 Заказ 123 Тираж 100 экз.

Редакционно-издательский отдел Ярославского государственного педагогического университета имени К.Д.Ушинского (ЯГПУ)

150000, Ярославль, Республиканская, 108

ЛР №020080 от 19.12.97

Типография ЯГПУ

150000, Ярославль, Которосльная наб., 44

130