Реферат: Дискретная математика: "Графы"
Данная работа является типовым расчетом N2 по курсу
«Дискретнаяматематика» по теме «Графы», предлагаемая сту-
дентам МГТУ им.Баумана. (Вариант N 17).
Эта работа была выполнена в мае 1996г. и сдана препо-
давателюКалинкину А.В. (доц. каф. ФН-1).
Сразу хочу сказать для своих коллег: Граждане! Имейте
терпение исовесть, поймите, что я это делаю для Вас с целью
помочьразобраться в этой теме, а не простосвалить очеред-
ной предмет. Мне известно, как непросто сейчас с литерату-
рой, и синформацией вообще. Поиски неизвестнокакой книги
занимаютмного времени, поэтому в конце я привел небольшой
списоклитературы, составленный мной из различных источников
в дополнение ксписку, написанному ранее в работе пографам
(о постановкелаб. работ по алгоритму Прима и Дейкстра), ко-
торая, я надеюсь,есть в сети.
Содержание работы:
──────────────────
Типовой расчет состоит из 11-ти задач:
1, 2 и 3 задачи относятся к способамзадания графов и
опредению иххарактеристик, таких как диаметр, радиус и т.д.
4 и 5 задачи соответственно наалгоритм Прима и Дейк-
стра. Здесь яснова отсылаю Вас к более ранней работе (см.
выше).
6-я задача о поиске максимального потока всети (метод
Форда-Фалкерсона).
7-я задача — Эйлерова цепь (задача опочтальоне).
8-я задача — Гамильтонова цепь.
9-я задача — метод ветвей и границприменительно к за-
даче окоммивояжере.
10-я задача — задача о назначениях;венгерский алгоритм.
11-я задача — тоже методом ветвей играниц.
Работа (tr_graf1.doc) выполнена в WinWord2.0, исполь-
зованы шрифты«Балтика» и «System». Иллюстрации выполнены в
CorelDraw 3.0.
Дополнение к списку литературы.
───────────────────────────────
1. Грешилов А.А. Как принять наилучшеерешение в реаль-
ныхусловиях:-М.: Радио и связь, 1991.-320с.: ил.
2. Беллман Р. Динамическоепрограммирование: Пер. с
англ./Под ред.Н.Н. Воробьева.-М.: ИЛ, 1960.-400 с.
3. Беллман Р., Дрейфус С. Прикладные задачи динамичес-
когопрограммирования: Пер с англ./Под ред. А.А. Первозванс-
кого.-М.: Наука,1965.-458 с.
4. Вентцель Е.С. Исследованиеопераций.-М.: Сов. радио,
1972.-551 с.
5. Вильямс Н.Н. Параметрическоепрограммирование в эко-
номике (методыоптимальных решений):-М.: Статистика, 1976.-96
с.
6. Гольштейн Е.Г., Юдин Д.Б. Новыенаправления в линей-
номпрограммировании:-М.: Сов радио, 1966.- 524 с.
7. Зангвилл У.И. Нелинейное программирование: Пер. с
англ./Под ред.Е.Г. Гольштейна.-М.: Сов радио, 1973.- 312 с.
8. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое
программирование(справочное руководство).-М.: Наука, 1964.-
348 с.
9. Исследование операций. Методологическиеосновы и ма-
тематическиеметоды: Пер. с англ./ Под ред. И.М. Макарова,
И.М.Бескровного.-М.: Мир, 1981.- Т.1.-712 с.
10. Исследование операций. Модели и применение: Пер. с
англ./ Подред. И.М. Макарова, И.М. Бескровного.-М.: Мир,
1981.- Т.1.-712с.
11. Лазарев В.Г., Лазарев Ю.В. Динамическое управление
потокамиинформации в сетях связи.-М.: Радио и связь, 1983.-
216 с.
12. Мартин Дж. Системный анализ передачиданных.: Пер с
англ./ Под ред.В.С. Лапина.-М.: Мир, 1975.- М.2.- 431 с.
13. Монаков В.М., Беляева Э.С., КраснерН.Я. Методы оп-
тимизации.Пособие для учителя.-М.: Просвещение,1978.- 175
с.
14. Муртаф Б. Современное линейное программирование:
Теория ипрактика. Пер. с англ./Под ред. И.А.Станевичуса.-
М.: Мир, 1984.-224 с.
15. Рокафеллор Р. Выпуклый анализ: Пер. с англ./Под
ред. А.Д. Иоффе,В.М. Тихомирова.-М.: Мир, 1973.- 469 с.
16. Сухарев А.Г., Тимохов А.В., ФедоровВ.В. Курс мето-
дов оптимизации.-М.:- Наука, Физматгиз, 1986.- 326 с.
17. Ху Т. Целочисленное программирование ипотоки в се-
тях: Пер. с англ./Под ред. А.А. Фридмана.- М.: Мир, 1974.-
419 с.
18. Фиакко А., Мак-Кормик Г. Нелинейное программирова-
ние. Методыпоследовательной безусловной минимизации: Пер. с
англ./Под ред.Е.Г. Гольштейна. -М.:- Мир, 1972.- 240 с.
19. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей:
Пер. с англ./ Подред. Б.Г. Сушкова.- М.: Мир, 1984.- 496 с.
20. Юдин Д.Б., Гольштейн Е.Г. Линейное программирова-
ние. Теория иконечные методы,- М.:- Физматгиз, 1963.- 775 с.
Желаю всего хорошего, буду рад, если мояскромная рабо-
та поможет Вамполюбить математику или хотя бы заинтересо-
ваться ей.
С уважением,Редникин Андрей.