2. Разработка и отладка программы определения метрических параметров графов.

3. Проверка программы на примере заданного графа.

Краткие теоретические сведения

Обозначим через d(a,b) длину (число ребер или дуг) кратчайшего маршрута между вершинами a и b.

Для d(a,b) справедливы следующие утверждения

1) d ( a,a ) = 0,

2) d (a,b ) 0,

3) d (a,b) = 0 a = b.

Для неорграфа расстояния симметричны:

4) d (a,b) = d (b, a),

5) d (a, b) d (a, c) + d (c,b).

П
ример:

Рассмотрим вершину х₁:

d(x₁, x₂) = d(x₁, x₄) = d(x₁, x₅) = 1,

d(x₁, x₃ )= 2,

max d(x₁, x_i) = d(x₁, x₃) = 2.

x_i X

Результаты расчетов для других вершин представлены в матрице D, а максимальные кратчайшие расстояния – в столбце e(x_i):

e(x_i)

D =

Для каждой вершины x_i существует максимальный кратчайший маршрут до некоторой вершины x_j, он называется эксцентриситетом вершины и обозначается e(x_i). (См. столбец справа от матрицы D).

Максимальный из всех эксцентриситетов графа – это диаметр графа

D(G) = max e(x_i).

для графа примера D(G) = 2.

Минимальный из эксцентриситетов – это радиус графа

r(G) = min e(x_i).

для графа примера r(G) = 1.

Вершины, у которых e(x_i) = r(G) называются центральными.

Вершины периферийные – те, у которых e(x_i) = D(G).

Множество центральных вершин – центр, множество периферийных вершин – окраина.

Следовательно, вершина х₅ – центр графа, так как e(x₅) = r(G) = 1. Вершины x₁, x₂, x₃, x₄ – окраина.

Под средним диаметром графа понимают величину

D_ср= ,

где С – сумма кратчайших расстояний между всеми парами вершин графа, n – число вершин графа.

D (G)=max d(x_i, x_j) = 3, где G – данный граф с X={a, b, c, d, e, f}.

Например, d(a, e) = 3 одно из максимальных значений.

d(a, f) = d(b, e) = d(b, f) =…= 3.

Найдем кратчайшие расстояния между всеми парами вершин графа G(6, 7):

d(a, b) = d(a, c) = d(b, a) = d(b, c) = d(c, a) = d(c, b) = d(c, d) = d(d, c) =

d(d, e) = d(d, f) = d(e, d) = d(e, f) = d(f, d) = d(f, e) = 1,

d(a, d) = d(b, d) = d(c, e) = d(c, f) = d(d, a) = d(d, b) = d(e, c) = d(f, c )= 2,

d(a, e )= d(a, f) = d(b, e) = d(b, f) = d(e, a) = d(e, b) = d(f, a) = d(f, b) = 2.

Найдем сумму С всех этих расстояний: С = 1∙14 + 2∙8 + 3∙8 = 54.

n = 6 – число вершин графа G(6, 7).

Найдем средний диаметр D_ср= = =1,8.

Содержание отчёта

1. Текст программы на C₊₊ либо Delphi (допускается в среде Visual Basic);

2. Результаты выполнения программы для заданного графа.

Лабораторная работа №11

Кратчайший маршрут во взвешенном графе

Цель работы: Изучение алгоритмов построения кратчайших маршрутов в графах.

Содержание работы:

1. Разработка алгоритмов построения кратчайших маршрутов в графах.

2. Разработка и отладка программы для построения кратчайших маршрутов в графах.

3. Проверка программы на примере нахождения кратчайших маршрутов в заданном графе.

Краткие теоретические сведения

Предварительное замечание:

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

После их исключения могут оказаться изолированные, тупиковые, преходящие вершины. Их также можно исключить.

(преходящие, есть выход, нет входа).

В неорграфе никаких упрощений делать нельзя.

Волновой алгоритм

Вариант 1

Вес ребра – 1 (нет ребра – 0).

S – начало маршрута,

t – конец маршрута.

Ищем маршрут между S и T.

Прямая фаза:

Сначала все вершины не имеют меток.

1. Положим i = 0, присвоим вершине S вес W(S) = i (т.е. W(S) = 0) .

2. Находим все не помеченные вершины, связанные ребром с вершиной (вершинами) с меткой i.

3. Если такие вершины есть, то помечаем их метками i = i + 1. Если вершина T помечена, то к п. 4. Если – нет, то к п. 2. Если таких вершин нет, а вершина T не помечена, то T недостижима из S. СТОП.

4. Длина кратчайшего маршрута от S к T равна W(T). СТОП.

Обратная фаза (начинается с конца):

Принадлежность вершин кратчайшему маршруту определяется из условий: Конечная вершина V_k = T. Для V_k–1 должно выполняться условие W(T) – W(V_k–1) = 1. Для V_k–2 W(V_k–1) – W(V_k–2) = 1 и т.д. пока не придем в вершину S.

Пример: На рисунке показан граф с разметкой вершин.

Маршрут найдите самостоятельно.

Длина маршрута (S,T) равна 3.

Вариант 2

Каждое ребро имеет вес ℓ_ij, ℓ_ii = 0.

ℓ_ij – число, если ребро есть, или = , если ребра нет.

Ищем кратчайший маршрут между вершинами V₁ и V_k.

1) Пометить вершины с номерами 1…n метками ₁ = 0, _i = , i = , n – число вершин. Метки вершин V₂…V_n считаем временными.

2) Рассматриваем V₁. У вершин, смежных с V₁, временные метки меняем по следующему правилу:

– если _i – ₁ ℓ_1,i (ℓ_1,i – длина ребра, соединяющего вершину V₁ с вершиной V_i), то заменяем _i на _i = ₁ + ℓ_1,i

– если _i – ₁ ℓ_1,i , то _i не изменяем.

3) Среди вершин с временными метками выбираем вершину V_i с минимальным значением метки _i. Метку этой вершины делаем постоянной.

4) Рассматриваем вершины V_j, смежные с V_i, и изменяем временные метки V_j:

– если λ_j – λ_ί > ℓ_ij, то λ_j = λ_ί + ℓ_ij,

– если λ_j – λ_ί ℓ_ij, то не меняем.

1. Если метка конечной вершины V_k – постоянная, то к пункту 6, если нет, то к пункту 3.

2. Строим маршрут, начиная с V_k.

λ_k – длина маршрута.

Принадлежность вершины V_k–1 маршруту определяется равенством

λ_k – _k–1 = ℓ_{k, k–1}

Вершина V_k–2 должна удовлетворять условию

_k–1 – _k–2 = ℓ_{k–1, k–2} и т.д.

Алгоритм пригоден для орграфа и для весов (расстояний) отрицательных, но таких, чтобы не было в графе циклов с отрицательным весом.

Отрицательный цикл может сделать длину маршрута как угодно малой.

Пример: Дан граф с весами ребер, показанными на рисунке.

Найдите кратчайший маршрут (1,4) самостоятельно.

Ответ: 1,5,3,4; ℓ_1,4 = 2.

Содержание отчёта

1. Текст программы на C₊₊ либо Delphi (допускается в среде Visual Basic);

2. Результаты выполнения программы для заданного графа.

ЛИТЕРАТУРА

1. Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Изд-во НГТУ, 2002. – 280 с.

1. Новиков Ф. А. Дискретная математика для программистов. – СПб.:

Питер, 2001. – 304 с.

1. Ашинянц Р. А. Логические методы в искусственном интеллекте. –

М.: МГАПИ, 2001. – 223 с.

1. Кук Д., Бейз Г. Компьютерная математика: Пер. с англ. – М.:

Наука, 1990. – 384 с.

1. Иванов Б. Н. Дискретная математика. Алгоритмы и программы. –

М.: Лаборатория Базовых Знаний, 2003. – 288 с.

1. Редькин Н. П. Дискретная математика: Курс лекций для

студентов-механиков. – СПб.: Изд-во “Лань”, 2003. – 96 с.

1. Харари Ф. Теория графов: Пер. с англ. Под ред. Г. П. Гаврилова.

Изд. 2-е. – М.: Едиториал УРСС, 2003. – 296 с.