- •Содержание
- •Введение
- •Часть 1. Элементы теории множеств и отношений § 1. Понятие множества. Операции над множествами
- •Примеры
- •Операции над множествами
- •Основные тождества алгебры множеств
- •Упражнения
- •§ 2. Декартово произведение двух или нескольких множеств. Понятие отношения. Бинарные отношения
- •Упражнения
- •§ 3. Специальные бинарные отношения. Отношения эквивалентности
- •Упражнения
- •§ 4. Отношения порядка
- •Упражнения
- •§ 5. Функциональные отношения (отображения). Виды отображений
- •Виды отображений:
- •Упражнения
- •Часть 2. Теория графов
- •§ 1. Основные понятия теории графов
- •Способы задания графов. Матричное задание графов.
- •Свойства матриц смежности и инцидентности
- •Упражнения
- •§ Б 2. Булевы матрицы
- •Дизъюнкция (конъюкция)
- •§ 3. Связность графа. Компоненты связности. Матрица связности
- •Выделение компонент связности
- •Алгоритм выделения компонент сильной связности
- •Упражнения
- •§ 4. Полные графы. Двудольные графы. Однородные и реберные графы
- •Упражнения
- •§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер)
- •Упражнения
- •§ 6. Расстояние в графах
- •Упражнения
- •§ 7. Нагруженные графы. Расстояния в нагруженном графе
- •Нахождение минимального пути в нагруженном орграфе
- •Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v1 в vi1 (i1≠1)
- •Упражнения
- •§ 8. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы
- •Упражнения
- •§ 9. Деревья. Остов графа. Цикловой базис графа
- •Алгоритм нахождения кратчайшего остова в нагруженном графе
- •Упражнения
- •§ 10. Раскраска графов. Планарные графы Раскраска вершин графа
- •Одноцветные классы образуют независимые множества вершин.
- •Существуют и приближенные алгоритмы раскрашивания:
- •Упражнения
- •Варианты контрольных работ Часть 1. Элементы теории множеств и отношений Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Часть 2. Теория графов Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Ответы Часть 1
- •Часть 2
- •Тест по теории множеств и отношений
- •Тест по теории графов
- •Библиографический список
- •Любовь Васильевна Архипова Елена Сергеевна Дернович
- •Дискретная математика
§ 7. Нагруженные графы. Расстояния в нагруженном графе
Определение: Граф G = (V, X) (орграф Д = (V, X)) называется нагруженным, если на множестве ребер (дуг) определена некоторая функция l: X → R , которую часто называют весовой функцией.
Таким образом, в нагруженном графе (нагруженном орграфе) каждому ребру (дуге) x X поставлено в соответствие некоторое действительное число l(x).
Значение l(x) называется длиной ребра (дуги) x или весом ребра (дуги) x.
Пример:
l( v1, v2)=3
l( v2, v3)=2
l( v1, v3)=7
Информацию о длинах дуг (ребер) нагруженного орграфа (графа) можно представить в виде матрицы длин дуг (ребер).
Определение: Матрицей длин дуг (ребер) орграфа Д (графа G) называется квадратная матрица порядка n С= [сij], у которой каждый элемент сij определяется следующим образом:
Определение: Пусть дан нагруженный граф G = (V, X) (орграф Д = (V, X)).
Рассмотрим некоторый маршрут (путь) из вершины vi в вершину vj. Обозначим его П, а сумму длин входящих в него ребер (дуг) обозначим l(П).
l(П) называется длиной маршрута (пути) П в нагруженном графе (орграфе) или весом маршрута (пути).
Пример: Пусть П – маршрут из v1 в v3.
П1 = v1 v2 v3 П2 = v1 v3
l(П1) = 3 + 2 = 5 l(П2) = 7
Определение: Расстоянием в нагруженном графе (орграфе) (или взвешенным расстоянием) между вершинами vi и vj называется длина минимального маршрута (пути) из vi в vj.
Матрица взвешенных расстояний, взвешенные эксцентриситеты вершин, диаметр, радиус, центр нагруженного графа определяются аналогично определению данных понятий для ненагруженного графа.
Нахождение минимального пути в нагруженном орграфе
Существует несколько алгоритмов нахождения кратчайшего маршрута в нагруженном графе:
Алгоритм Форда – Беллмана.
Алгоритм Дейкстры.
Пусть Д=(V,X) – нагруженный орграф. V={v1,…,vn}.
C(Д)nxn=[cij] – матрица длин дуг нагруженного орграфа.
Величина i(k), где i=1,…,n; k=1,2,… , равна длине минимального пути среди путей из v1 в vi, содержащих не более k дуг. Если таких путей нет, то i(k)=. 1(0) =0, i(0)=, i=2,…,n.
Утверждение:
При i=2,…,n, k≥0:
При i=1, k≥0:
Число дуг в простой цепи не превосходит n-1. Следовательно, i(k)= i(n-1) i=2,..,n,k≥n-1.
Если i(n-1)= (i {2,..,n}), то vi не достижима из v1, а если i(n-1), то vi достижима из v1 и при этом i(n-1) –длина минимального пути из v1 в vi.
Таким образом, по i(n-1) можно судить о достижимости вершин vi (i=2,…,n) из v1, а также определить длины минимальных путей из v1 в достижимые вершины.
Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v1 в vi1 (i1≠1)
Шаг 1: Пусть таблица величин i(k)(i=1,2,…,n;k=0,1,…,n-1) составлена. Если , то вершина не достижима из . В этом случае работа алгоритма заканчивается.
Шаг 2: Пусть . Тогда число выражает длину любого минимального пути из в в нагруженном орграфе Д.
Определим минимальное число k1≥1, при котором выполняется равенство . По определению чисел i(k) получаем, что k1 – минимальное число дуг в пути среди всех минимальных путей из в в нагруженном орграфе Д.
Шаг 3: Последовательно определяем номера такие, что:
(*)
Из () с учетом того, что ,имеем
(1)
Складывая равенства () и учитывая (1) получаем: , т.е. - искомый минимальный путь из в в нагруженном орграфе Д.
В этом пути ровно k1 дуг. Следовательно, мы определили путь с минимальным числом дуг среди всех минимальных путей из в в нагруженном орграфе Д.