4752

  • 16 мая 2011 г.
  • 4640 Слова
Ульяновский государственный университет
Механико-математический факультет
Кафедра прикладной математики

Воденин Д.Р.

Оптимизационные задачи на графах

учебно-методическое пособие для студентов экономического факультета

Ульяновск 1999

УДК 519.9

Воденин Д.Р. Оптимизационные задачи на графах : учебно-методическое пособие. Ульяновск1999, 69 с.

В основу данного пособия положен конспект первой главы лекций по курсу «Методы оптимальных решений», читаемого автором на экономическом факультете с момента основания Ульяновского филиала МГУ.
Пособие предназначено для студентов всех специальностей 2 курса экономического факультета, а также для студентов РОСАМКО.

Рецензент : д.ф.-м.н.., профессор В.К.ГорбуновОдобрено на заседании Ученого Совета механико-математического факультета
Ульяновского госуниверситета

( Ульяновский государственный университет, 1999 г.

Содержание.

0.Введение.
1.Основные определения теории графов.
1.1.Понятие графа.
1.2.Способы задания графов.
1.3.Связность.1.4.Деревья.
2.Кратчайшие пути.
2.1.Поиск контура в графе.
2.2.Дерево кратчайших путей. Алгоритм Дейкстры.
2.3.Матрица кратчайших расстояний.
2.3.1.Алгоритм Беллмана.
2.3.2.Алгоритм Флойда.
2.4.Кратчайшее дерево.
3.Критический путь.
3.1.Поиск максимального пути в графе.
3.2.Алгоритм поискакритических путей.
4.Эйлеровы и Гамильтоновы пути, циклы и контуры.
4.1.Эйлеровы пути, циклы и контуры.
4.2.Гамильтоновы пути, циклы и контуры.
4.3.Метод ветвей и границ.
5.Задача о куче камней.
Литература
0.Введение

На втором курсе экономического факультета автором читается курс «Методы оптимальных решений». Одним из основных разделовкурса является раздел «Оптимизационные задачи на графах». И хотя задачи и методы, рассматриваемые в данном разделе широко известны, остро ощущается недостаток литературы по данному вопросу. В принципе все они описаны, например, в [1]. Однако, есть ряд причин, по которым [1] не может являться наиболее подходящим пособием для студентов:
эта книга написана давно, и к настоящему моменту являетсябиблиографической редкостью,
она написана для математиков, и трудна для студентов экономического факультета,
в ней используется нестандартная система обозначений векторов и матриц,
недостаточно подробно разбираются примеры, а в ряде случаев, они просто отсутствуют,
для описания алгоритмов используются устаревшие языки программирования Алгол-60 и Алгол-68.
В других книгах, например [2]-[5], полностью неописываются все методы и алгоритмы, разбираемые в курсе. К тому же все указанные книги являются библиографической редкостью.
Вот почему автор решил издать расширенный курс лекций по разделу «Оптимизационные задачи на графах» в качестве учебного пособия для студентов экономистов второго курса.
Для описания алгоритмов используются отдельные конструкции языка Паскаль в сочетании с обычнымиматематическими обозначениями. Иногда приводятся фрагменты программ на языке Паскаль. Выбор языка не случаен. На момент написания данного методического пособия этот язык является базовым в курсе информатики для экономистов.
Многие доказательства опускаются. Это делается сознательно, поскольку автор считает, что для экономистов более важны постановки задач и методы их решений. В тоже время, как правило,даются ссылки на литературу, где можно найти доказательства тех или иных теорем.
При изложении материала автор старался придерживаться такого подхода:
постановка задачи,
математическая формализация задачи,
алгоритм решения ,
пример.
Этот же подход используется и при чтении лекций. Разбор примеров в методическом пособии проводится с...
tracking img