Дискретная математика "Графы"

  • Просмотров 3627
  • Скачиваний 595
  • Размер файла 376
    Кб

Данная работа является типовым расчетом N2 по курсу "Дискретная математика" по теме "Графы", предлагаемая сту- дентам МГТУ им. Баумана. (Вариант N 17). Эта работа была выполнена в мае 1996 г. и сдана препо- давателю Калинкину А.В. (доц. каф. ФН-1). Сразу хочу сказать для своих коллег: Граждане! Имейте терпение и совесть, поймите, что я это делаю для Вас с целью помочь разобраться в этой теме, а не просто свалить очеред- ной предмет.

Мне известно, как непросто сейчас с литерату- рой, и с информацией вообще. Поиски неизвестно какой книги занимают много времени, поэтому в конце я привел небольшой список литературы, составленный мной из различных источников в дополнение к списку, написанному ранее в работе по графам (о постановке лаб. работ по алгоритму Прима и Дейкстра), ко- торая, я надеюсь, есть в сети. Содержание работы:

────────────────── Типовой расчет состоит из 11-ти задач: 1, 2 и 3 задачи относятся к способам задания графов и опредению их характеристик, таких как диаметр, радиус и т.д. 4 и 5 задачи соответственно на алгоритм Прима и Дейк- стра. Здесь я снова отсылаю Вас к более ранней работе (см. выше). 6-я задача о поиске максимального потока в сети (метод Форда-Фалкерсона). 7-я задача - Эйлерова цепь

(задача о почтальоне). 8-я задача - Гамильтонова цепь. 9-я задача - метод ветвей и границ применительно к за- даче о коммивояжере. 10-я задача - задача о назначениях; венгерский алгоритм. 11-я задача - тоже методом ветвей и границ. Работа (tr_graf1.doc) выполнена в WinWord 2.0, исполь- зованы шрифты "Балтика" и "System". Иллюстрации выполнены в CorelDraw 3.0. Дополнение к списку литературы.

─────────────────────────────── 1. Грешилов А.А. Как принять наилучшее решение в реаль- ных условиях:-М.:Радио и связь, 1991.-320с.:ил. 2. Беллман Р. Динамическое программирование: Пер. с англ./Под ред. Н.Н. Воробьева.-М.: ИЛ, 1960.-400 с. 3. Беллман Р., Дрейфус С. Прикладные задачи динамичес- кого программирования: Пер с англ./Под ред. А.А. Первозванс- кого.-М.: Наука,