Навигация по странице:
|
Учебник по дискретной математики. Д. Ушинского Дискретная математика
|
| Название |
Д. Ушинского Дискретная математика
|
| Анкор |
Учебник по дискретной математики.doc |
| Дата |
12.04.2017 |
| Размер |
2.66 Mb. |
| Формат файла |
 |
| Имя файла |
Учебник по дискретной математики.doc |
| Тип |
Документы
#421
|
| страница |
20 из 20 |
|
№
|
Тема
|
Литература
|
|
Основные определения и примеры графов.
|
1 (гл. 1 § 1); 5 (гл. 1); 6 (гл. 6 § 1); 7 (гл. 1); 8 (гл. 1 § 2); 10 (гл. 7 § 1); 1 1(гл. 4 § 1); 12 (гл. 1 § 1, гл. 2 § 2, 3); 14(гл. 3 § 1)
|
|
Изоморфизм графов.
|
5 (гл. 1 § 1); 10 (гл. 7 § 1); 12 (гл. 1 § 1, гл. 2 § 2); 14(гл. 3 § 4)
|
|
Способы описания графов.
|
1 (гл. 1 § 4); 2 (гл. 7 § 1); 5 (гл. 1 § 6); 6 (гл. 6 § 2); 7 (гл. 1 § 8); 10 (гл. 7 § 4); 11 (гл. 4 § 1); 14(гл. 3 § 4)
|
|
Достижимость и связность.
|
1 (гл. 1 § 2); 5 (гл. 5 § 33); 6 (гл. 6 § 5, 6); 7(гл. 2);10 (гл. 8 § 1); 11 (гл. 4 § 3); 14(гл. 3 § 3)
|
|
Мосты, блоки, меры связности.
|
1 (гл. 2 § 2, гл. 8 § 2); 2 (гл. . 7 § 4); 5 (гл. 5 § 34); 6 (гл. 6 § 13); 10( гл. 7 § 2)
|
|
Кратчайшие пути
|
1 (гл. 10); 2 (гл. 6 § 3, 4); 5 (гл. 12 § 76); 6 (гл. 6 § 9); 7 (гл. 8); 8 (гл. 3); 10 (гл. 8 § 7); 11 (гл. 4 § 5); 14(гл. 3
§ 10,11,12)
|
|
Обходы графа.
|
1 (гл. 8 § 1, 4); 2 (гл. 7 § 3); 6 (гл. 6 § 3); 11 (гл. 4 § 9); 14(гл. 3 § 17)
|
|
Эйлеровы циклы в графах.
|
1 (гл. 3 § 1, гл. 8 § 5); 5 (гл. 7 § 43); 6 (гл. 6 § 7); 10 (гл. 10 § 2); 12 (гл. 3 § 6)
|
|
Гамильтонов цикл на графе.
|
1 (гл. 3 § 2); 5 (гл. 7 § 44); 7 (гл. 10 § 2);10 (гл. 10 § 3); 12 (гл. 3 § 7)
|
|
Задача коммивояжера
|
1 (гл. 13); 7 (гл. 10 § 5, 6, 7); 8 (гл. 7)
|
|
Фундаментальные циклы и разрезы
|
6 (гл. 6 § 12); 10 (гл. 10 § 1); 11 (гл. 4 § 11, 12);
|
|
Деревья. Эквивалентные определения деревьев
|
1 (гл. 2 § 1); 5 (гл. 2 § 13); 7 (гл. 7 § 1);10 (гл. 9 § 1); 12 (гл. 4 § 9); 14(гл. 3 § 15,16)
|
|
Каркас минимального веса
|
2 (гл. 7 § 2); 5 (гл. 2 § 15, гл. 12 § 75); 6 (гл. 6 § 8); 7 (гл. 7 § 3);10 (гл. 9 § 5)
|
|
Двудольные графы.
|
6 (гл. 6 § 14); 10 (гл 7 § 3.2)
|
|
Совершенное паросочетание и теорема Холла
|
5 (гл. 12 § 77); 7 (гл. 12); 10 (гл. 8 § 4); 12 (гл. 8 § 25)
|
|
Теорема.Менгера
|
5 (гл. 5 § 35); 10 (гл. 8 § 3); 12 (гл. 8 § 28)
|
|
Максимальное паросочетание
|
2 (гл. 7 § 5); 5 (гл. 12 § 77); 7 (гл. 12);8 (гл. 5)
|
|
Потоки в сетях
|
1 (гл. 11); 6 (гл. 6 § 10); 7 (гл. 11); 8 (гл. 4); 10 (гл. 8 § 5); 12 (гл. 8 § 29); 14(гл. 3 § 24, 25, 26)
|
|
Независимые и доминирующие множества
|
5 (гл. 4); 6 (гл. 6 § 11); 7 (гл. 3);10(гл. 11)
|
|
Ориентированный граф
|
1 (гл. 1 § 3); 2 (гл. 6 § 1, 2); 5 (гл. 10 § 63, 64, 65); 12 (гл. 7 § 22)
|
|
Достижимость, связность в орграфах
|
1 (гл. 8 § 3); 2 (гл. 6 § 7); 7 (гл. 2);10 (гл. 8 § 6)
|
|
Эйлеров цикл в орграфах.
|
12 (гл. 7 § 23)
|
|
Гамильтонов путь и цикл в орграфах.
|
12 (гл. 7 § 23); 14(гл. 3 § 3)
|
|
Плоские графы. Планарность.
|
1 (гл. 5 § 1); 5 (гл. 6 § 36); 10 (гл. 12 § 2); 11 (гл. 4 § 15); 12 (гл. 5 § 12); 14(гл. 3 § 20)
|
|
Укладки графов
|
1 (гл. 5 § 11); 5 (гл. 6 § 41); 12 (гл. 2 § 4, гл. 5 § 14); 14(гл. 3 § 21)
|
|
Формула Эйлера для плоских графов
|
1 (гл. 5 § 2); 5 (гл. 6 § 37); 12 (гл. 5 § 13); 14(гл. 3 § 20)
|
|
Стереографическая проекция.
|
5(гл. 6 §36); 12(гл. 2 §4)
|
|
Двойственный граф
|
1 (гл. 5 § 4), 12 (гл. 5 § 15)
|
|
Раскраски графов
|
1 (гл. 6 ); 5 (гл. 9); 10 (гл. 12 § 3); 11 (гл. 4 § 14); 12 (гл. 6); 14(гл. 3 § 22)
|
|
Раскрашивание карт. Теорема.о пяти красках.
|
10 (гл. 12 § 2.3); 12 (гл. 6); 14(гл. 3 § 22)
|
Список литературы
Асанов М. О., Баранский В. А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск, 2001.
Ахо А., Хокпкрофт Дж., Ульман Дж.Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2001.
Бадин Н.М., Волченков С.Г., Дашниц Н.Л., Корнилов П.А. Ярославские олимпиады по информатике. – Ярославль, 1995.
Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.
Иванов Б.Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002.
Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.
Майника Э. Алгоритмы оптимизации на сетях и графах. – М.:Мир,1981.
Мельников О.И. Занимательные задачи по теории графов. – Минск.: Тетрасистемс, 2001.
Новиков Ф.А. Дискретная математика для программистов. – СПб.:Питер, 2001.
Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2002.
Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
Харари Ф. Теория графов. – М.: Мир,1973.
Шапорев С.Д. Дискретная математика. –СПб:БХВ-Петербург, 2007
Яблонский С.В. Введение в дискретную математику. – М.: Высш. шк., 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
Изоморфизм графов 81
Достижимость и связность. 82
Циклы 84
Алгоритмы обхода связного графа. 86
Деревья 87
Двудольные графы 90
Ориентированные графы и мультиграфы 92
Плоские графы 95
Двойственные графы 97
Раскраски графа 98
Список рекомендуемой литературы по теории графов 100
Список литературы 102
Корнилов Петр Анатольевич
Заводчикова Надежда Ивановна
Прусова Наталия Александровна
Дискретная математика
Редактор Иванова Н.А.
Подписано в печать 25.09.07 Формат бумаги 80х64 1/16
Печ. л. 5.5 Заказ 123 Тираж 100 экз.
Редакционно-издательский отдел Ярославского государственного педагогического университета имени К.Д.Ушинского (ЯГПУ)
150000, Ярославль, Республиканская, 108
ЛР №020080 от 19.12.97
Типография ЯГПУ
150000, Ярославль, Которосльная наб., 44
|
|
|
Скачать 2.66 Mb.