- •Белгородская государственная
- •Введение
- •1. Определение графа
- •2. Представление графов в памяти эвм
- •3. Некоторые понятия и определения теории графов
- •4. Операции над графами
- •5. Связность
- •5.1. Построение покрывающих деревьев
- •5.2. Поиск на графах
- •Поиск в глубину
- •Поиск в ширину
- •5.3. Сильная связность
- •5.4. Транзитивное замыкание орграфа
- •Алгоритм следует из выражения 5.1
- •6. Расстояние
- •6.1. Поиск кратчайших путей между отдельными вершинами графа
- •6.2. Поиск кратчайших путей между каждой парой вершин графа
- •7. Потоки
- •7.1. Условия существования потока
- •7.2. Поиск увеличивающей цепи
- •7.3. Поиск максимального потока
- •7.4. Поиск потока минимальной стоимости
- •7.5. Задача почтальона для орграфа
- •Список литературы
Список литературы
1. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 384 с.
2. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: Пер. с англ./ Предисл. В.Б.Алексеева. - М.: Мир, 1980. - 476 с.
3. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. - М. Мир, 1981. - 323 с.
4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - 2-е изд. - М.: Энергоатомиздат, 1988. - 480 с.
5. Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. - М.: Мир, 1982. -416 с.
6. Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. - М.: Мир, 1978. - 846 с.
7. П.Холл. Вычислительные структуры. Введение в нечисленное программирование: Пер. с англ. - М.: Мир, 1978. - 214 с.
8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.
9. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. - 432 с.
10. Берж К. Теория графов и её применения. – М.: ИЛ, 1962. – 319 с.
11. Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 381 с.
12. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986. – 384 с.
13. Оре О. Теория графов. – М.: Наука, 1980. – 336 с.
14. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984. – 454 с.
15. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. – 207 с.
16. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.
Св.план 2000, поз. ____
МУРОМЦЕВ ВИКТОР ВЛАДИМИРОВИЧ
АЛГОРИТМЫ НА ГРАФАХ
УЧЕБНОЕ ПОСОБИЕ
Редактор ___________________
Корректор ___________________
Подписано к печати ___/_______/_____ Формат 6084/16
Объем 3 уч.-изд.л. Тираж _________
Заказ Цена __________