Удк 519. 17

ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ

СТРОИТЕЛЬНЫХ МАТЕРИАЛОВ

В.В.МУРОМЦЕВ

АЛГОРИТМЫ НА ГРАФАХ

УЧЕБНОЕ ПОСОБИЕ

БЕЛГОРОД - 2000

УДК 519.17

Муромцев В.В. Алгоритмы на графах: Учебное пособие.

Белгород: Изд. БИИММАП, 2000.- 64 с.

Даны основные понятия теории графов. Рассмотрены вопросы представления графов в памяти ЭВМ и ряд существующих алгоритмов на графах. Изложение иллюстрируется примерами сведения прикладных задач к графовым задачам. Затрагиваются общие вопросы построения эффективных алгоритмов. Приведено большое число упражнений, в которых требуется рассматривать вопросы программной реализации графовых алгоритмов и их модификации для решения прикладных задач.

Учебное пособие предназначено для студентов технических и экономических вузов, изучающих программирование.

Табл. 13. Ил. 37. Список лит.: 16 назв.

Рецензенты: Константинов И.С., д.т.н.

Жиляков Е.Г., д.т.н.

ВВЕДЕНИЕ..................................................................................... 4

1. ОПРЕДЕЛЕНИЕ ГРАФА........................................................ 7

2. ПРЕДСТАВЛЕНИЕ ГРАФОВ В ПАМЯТИ ЭВМ............ 10

3. НЕКОТОРЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

ТЕОРИИ ГРАФОВ...................................................................... 14

4. ОПЕРАЦИИ НАД ГРАФАМИ........................................................ 17

5. СВЯЗНОСТЬ.................................................................................... 20

5.1. Построение покрывающих деревьев......................................... 20

5.2. Поиск на графах..................................................................... 27

5.3. Сильная связность...................................................................... 31

5.4. Транзитивное замыкание орграфа......................................... 34

6. РАССТОЯНИЕ...................................................................... 35

6.1. Поиск кратчайших путей между отдельными

вершинами графа...................................................................... 36

6.2. Поиск кратчайших путей между каждой парой

вершин графа...................................................................... 43

7. ПОТОКИ.................................................................................... 44

7.1. Условия существования потока......................................... 44

7.2. Поиск увеличивающей цепи........................................................ 46

7.3. Поиск максимального потока......................................... 48

7.4. Поиск потока минимальной стоимости........................... 49

7.5. Задача почтальона для орграфа......................................... 53

СПИСОК ЛИТЕРАТУРЫ........................................................ 60