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

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

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

3. Бадин Н.М., Волченков С.Г., Дашниц Н.Л., Корнилов П.А. Ярославские олимпиады по информатике. – Ярославль, 1995.

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

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

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

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

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

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

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

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

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

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

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

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

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

Оглавление

Доказательство. В случае равных корней характеристического уравнения выражение f(n)= ∙r1n+ β∙r1n нельзя считать общим решением, так как в формуле f(n)= ∙r1n+ β∙r1n= r1n∙ (+β)= δ∙r1n останется только одна постоянная и выбрать её так, чтобы удовлетворить двум начальным f(0)=a, f(1)=b условиям, невозможно. Найдем второе решение отличное от r1n . 37

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

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

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

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

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

Сочетания 47

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

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

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

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

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

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

Матрица смежности 65

Матрица инциденций 66

Перечень ребер 66

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

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

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

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

Турниры 70

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

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

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

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

Циклы 85

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

Деревья 90

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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