- •Решение задач теории графов методические указания
- •1. Определение метрических характеристик графов
- •1.1. Теоретические сведения
- •1.2. Пример
- •1.3. Упражнения
- •2. Определение сильных компонент графа
- •2.1. Теоретические сведения
- •2.2. Пример
- •2.3. Задачи для самостоятельного решения
- •3. Построение остовных деревьев графа
- •3.1. Теоретические сведения
- •3.2. Примеры решения задач
- •Решение Кратчайший остов для данного графа имеет следующий вид:
- •Алгоритм Прима
- •3.3. Упражнения
- •4. Построение эйлеровых и гамильтоновых циклов в графе
- •4.1. Теоретические сведения
- •4.2. Примеры решения задач
- •4.3. Упражнения
- •5. Определение кратчайшего пути между двумя вершинами графа. Алгоритм дейкстры
- •5.1. Теоретические сведения
- •5.2. Пример
- •5.3. Упражнения
- •6. Определение кратчайших путей между всеми парами вершин графа. Алгоритм флойда
- •6.1. Теоретические сведения
- •6.2. Пример
- •6.3. Упражнения
- •7. Определение максимального потока в транспортной сети
- •7.1. Теоретические сведения
- •Алгоритм Форда-Фалкерсона включает следующие шаги: а. Расстановка пометок
- •7.3 Упражнения
- •Библиографический список
- •Содержание
- •Решение задач теории графов методические указания
- •394026 Воронеж, Московский просп., 14
ФГБОУ ВПО “Воронежский государственный технический университет”
Кафедра систем автоматизированного проектирования
и информационных систем
- 2012
Решение задач теории графов методические указания
к практическим занятиям по дисциплине «Дискретная математика»
для студентов по направлениям подготовки бакалавров 230100.62
«Информатика и вычислительная техника», 230400.62 «Информационные
системы и технологии» очной формы обучения
Воронеж 2012
Составитель д-р техн. наук С.Ю. Белецкая
УДК 517.9
Решение задач теории графов: методические указания к практическим занятиям по дисциплине «Дискретная математика» для студентов по направлениям подготовки бакалавров 230100.62 «Информатика и вычислительная техника», 230400.62 «Информационные системы и технологии» очной формы обучения / ФГБОУ ВПО «Воронежский государственный технический университет»; сост. С.Ю. Белецкая. Воронеж, 2012. 33 с.
Методические указания содержат теоретические и практические сведения по изучению основных алгоритмов теории графов.
Методические указания подготовлены в электронном виде в текстовом редакторе MS Word XP и содержатся в файле Задачи теории графов.doc.
Ил. 28. Библиогр.: 4 назв.
Рецензент д-р техн. наук, проф. О.Н. Чопоров
Ответственный за выпуск зав. кафедрой д-р техн. наук, проф. Я.Е. Львович
Издается по решению редакционно-издательского совета Воронежского государственного технического университета
© ФГБОУ ВПО «Воронежский государственный
технический университет», 2012
1. Определение метрических характеристик графов
1.1. Теоретические сведения
Пусть G=(X,U) - связный граф, а - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины (пути из ) называется расстоянием между вершинами и обозначается . Положим , если вершины не соединены маршрутом (путем). Расстояние удовлетворяет следующим аксиомам метрики:
1) ;
2) ;
3) тогда и только тогда, когда ;
4) для симметрических графов;
5) (неравенство треугольника).
Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:
Матрицу расстояний можно определить
Для фиксированной вершины величина
называется эксцентриситетом (отклоненностью) вершины .
Максимальный среди эксцентриситетов вершин называется диаметром графа G и обозначается diam (G):
Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):
Вершина, имеющая минимальный эксцентриситет, называется центром графа.
Для вершины число называется передаточным числом. Вершина графа, которой соответствует минимальное передаточное число
называется медианой графа. Центров и медиан в графе может быть несколько.