Материал: Решение задач теории графов методические указания к практическим занятиям по дисциплине «Дискретная математика». Белецкая С.Ю

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

Кафедра систем автоматизированного проектирования

и информационных систем

- 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):

Вершина, имеющая минимальный эксцентриситет, называется центром графа.

Для вершины число называется передаточным числом. Вершина графа, которой соответствует минимальное передаточное число

называется медианой графа. Центров и медиан в графе может быть несколько.

1.2. Пример

Определить метрические характеристики графа

Рис. 1

Решение. Метрические характеристики определяются следующим образом:

Радиус графа равен 1, диаметр равен 2. Центр графа - вершина ; Медиана графа - вершина .

1.3. Упражнения

1. Определить метрические характеристики неориентированных графов

а б

в г

Рис. 2

2. Определить метрические характеристики ориентированных графов

Рис. 3

2. Определение сильных компонент графа

2.1. Теоретические сведения

Орграф называется сильно связным, если любые две его вершины взаимно достижимы, односторонне связным, если для любых двух вершин по крайней мере одна достижима из другой и слабо связным, если связным является лежащий в его основе неорграф.

Сильной компонентой орграфа называется его максимальный сильно связный подграф, подграф, не содержащийся ни в каком другом сильно связном подграфе этого графа.

Для определения сильных компонент графа необходимо:

Построить матрицу достижимости графа. Матрицей достижимости графа с n вершинами называется квадратная матрица R порядка n, элементы которой определяются следующим образом:

2. Построить матрицу контрдостижимости графа. Матрицей контрдостижимости графа с n вершинами называется квадратная матрица Q порядка n, элементы которой определяются следующим образом:

Матрицу контрдостижимости можно определить по матрице достижимости следующим образом:

3. Построить матрицу сильной связности графа. Матрицей сильной связности орграфа с n вершинами называется квадратная матрица S порядка n, элементы которой определяются следующим образом:

Матрицу сильной связности можно определить следующим образом:

где * - операция поэлементного умножения матриц.

4. По матрице сильной связности выделить сильные компоненты графа. Если вершины принадлежат одной сильной компоненте орграфа, то . При этом строки (столбцы), соответствующие этим вершинам в матрице S, одинаковы.

2.2. Пример

Рис. 4

Решение. Для данного графа матрицы R, Q и S имеют вид:

В соответствии с матрицей S сильные компоненты графа:

х₁, х₂, х₆,х₇ –первая сильная компонента;

х₃, х₄, х₅ - вторая сильная компонента.

2.3. Задачи для самостоятельного решения

Определить сильные компоненты графов.

а б

в г

д е

ж з

Рис. 5