Оглавление

основы теории графов 1

Введение 3

ГЛАВА 1. СПОСОБЫ ЗАДАНИЯ ГРАФОВ. ОПЕРАЦИИ НАД ГРАФАМИ. МЕТРИЧЕСКИЕ ХАРАКТЕРИСТИКИ ГРАФОВ. УПОРЯДОЧИВАНИЕ ЭЛЕМЕНТОВ ОРГРАФОВ 4

1. Способы задания графов. Операции над графами. Метрические характеристики графов 4

1.1. Основные понятия и определения 4

1.2. Операции над графами 7

1.3. Маршруты, цепи, циклы 9

1.4 . Способы задания графов 15

ГЛАВА 2. нахождение минимальных 44

и максимальных путей на орграфах 44

1. Нахождение кратчайших путей. Алгоритм Дейкстры 44

2. Нахождение кратчайших путей. Алгоритм Беллмана-Мура 49

3. Алгоритм нахождения максимального пути 55

. 55

глава 3. Остовы графов, фундаментальные циклы. Эйлеровы и гамильтоновы графы. Доминирующие множества и клики 61

1. Деревья (основные определения) 61

2. Задача об остове экстремального веса 66

3. Обходы графов. Фундаментальные циклы 69

4. Клики, независимые множества 74

Глава 4. Планарные графы 83

1. Планарность графов 83

Глава 5. ПОТОКИ В СЕТЯХ 97

1. Потоки в сетях 97

2. Теорема Форда-Фалкерсона 99

3. Случайные графы 102

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 133

основы теории графов 137

Учебное издание

Остапенко Александр Григорьевич

Ряжских Александр Викторович

Шелковой Александр Николаевич

Ююкин Николай Алексеевич

Основы теории графов

В авторской редакции

Подписано к изданию 29.11.2013.

Объём данных 6,3 Мб

ФГБОУ ВПО «Воронежский государственный технический университет»

394026 Воронеж, Московский просп., 14

3