Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образовании ДВГУПС

Кафедра «ИТиС»

Курсовая работа

Графы

Выполнил: Джемерук А.С.,

Студент группы 22к

Проверила: Рыбкина О.В.

Хабаровск 2011

Содержание

• Пояснительная записка
• Глава 1. Понятие орграфа
• 1.1 Основные определения
• 1.2 Решение заданий 1.1-1.6
• Глава 2. Понятие неориентированного графа
• 2.1 Определения
• 2.2 Решение заданий 1.7-1.13
• Глава 3. Ориентированные и неориентированные деревья
• 3.1 Определение
• 3.2 Свойства
• Глава 4. Алгоритмы нахождения кротчайших путей в графе
• 4.1 Алгоритм Дейкстры (алгоритм расстановки меток)
• 4.2 Алгоритм Беллмана-Мура (алгоритм корректировки меток)
• Заключение
• Список используемой литературы
• Приложение
• Пояснительная записка
• Первая глава содержит основные понятия и определения орграфа, встречающиеся в заданиях, методы решения и подробное пояснение к заданиям 1.1-1.6
• Вторая глава содержит основные понятия и определения неориентированного графа, встречающиеся в заданиях, методы решения и подробное пояснение к заданиям 1.7-1.13.
• Третья глава содержит основные понятия, определения и примеры неориентированных и ориентированных деревьев.
• Четвертая глава содержит подробное описание алгоритмов нахождения кротчайших путей в графе.
• Задание 1. По заданной матрице весов графа G (Вариант №3) выполнить:
• 1. Преобразовать матрицу весов в матрицу смежности орграфа. По полученной матрице:
• 2. Построить орграф.
• 3. Указать для каждой вершины ее степень входа и степень выхода.
• 4. Построить матрицу инцидентности орграфа.
• 5. Добавить в орграф дугу таким образом, чтобы одна из сильных компонент орграфа, содержала 3 вершины. Разложить полученный орграф на сильные компоненты по алгоритму.
• 6. Построить матрицу достижимостей и контрдостижимостей.
• 7. Преобразовать полученный орграф в неориентированный граф.
• 8. Построить неориентированный граф.
• 9. Перечислить смежные вершины и ребра,
• 10. Составить для него матрицу смежности.
• 11. Указать степени вершин графа.
• 12. Составить матрицу Кирхгофа и матрицу инцидентности.
• 13. Изменить граф таким образом, чтобы получить: полный граф, мультиграф, псевдограф, дерево. Построить полученные графы.
• Задание 2. По заданной матрице весов графа G (Вариант №3) найти величину минимального пути и сам путь от вершины до конечной вершины или по алгоритму Дейкстры.
• Задание 3. По заданной матрице весов графа G (Вариант №3) найти минимальный путь и сам путь по алгоритму Беллмана-Мура между начальной вершиной и конечной вершиной или .
• Глава 1. Понятие орграфа

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

Пусть V -- конечное непустое множество, V² -- его декартов квадрат. Ориентированный граф (орграф) -- это пара (V, А), где A V². Элементы множества V называются вершинами орграфа G=(V, А), а элементы множества А -- его дугами. Таким образом, дуга -- это упорядоченная пара вершин. Множества вершин и дуг орграфа G обозначаются через VG и AG соответственно. Число |VG| называется порядком орграфа G и обозначается через |G|.

Если х = (u, v) -- дуга, то вершины u и v называются ее концевыми вершинами, причем u называется началом дуги х, а. v -- концом. Говорят, что дуга инцидентна каждой из своих концевых вершин. Говорят также, что дуга исходит из своего начала и заходит в свой конец. Дуга с совпадающими началом и концом, т. е. дуга вида (v, v), называется петлей. Можно определить ориентированные графы с несколькими дугами, имеющими общее начало и общий конец (мультиграфы). Такие дуги называются параллельными.

На рисунке дуга изображается направленной линией, идущей от начала дуги к концу. Направление линии обозначается стрелкой. Например, для графа G, представленного на рис. 1, VG={v₁, v₂, v₃, v₄, v₅}, AG= {x₁, x₂, x₃, x₄, x₅, x₆, x₇}, причем x₁ и x₂ --параллельные дуги, a x₇ -- петля.

Вершины орграфа называются смежными, если они являются концевыми для некоторой дуги. Дуги называются смежными, если они имеют общую концевую вершину.

Пусть G-- некоторый орграф. Ориентированным маршрутом (или просто маршрутом) в графе G называется такая последовательность

S = (v₀, x₁, v₁, x₂, v₂, x₃, v₃, x₄,.., v_n, x_n,) (1)

его чередующихся вершин v_i и дуг х_j, что x_i = (v_i-1, v_i) (i = 1, n). Такой маршрут назовем (v₀, v_n) - маршрутом. Вершины v₀ и v_n назовем крайними, а остальные вершины маршрута (1) -- промежуточными (внутренними). Длиной маршрута называется число входящих в пего дуг. Маршрут называется цепью, если все входящие в пего дуги различны, и путем, если все входящие в него вершины, кроме, возможно, крайних, различны.

Если в орграфе G нет параллельных дуг, то маршрут (1) может быть задан последовательностью входящих в него вершин: S=( v₀, v₁, v₂, v₃,.., v_n). В любом случае маршрут можно задать последовательностью входящих в него дуг:

S = (x₁, x₂, x₃, x₄,.., x_n,)

Маршрут называется циклическим, если его первая и последняя вершины совпадают. Циклический путь называется контуром. Очевидно, что любой (u, v) - маршрут при u v содержит (u, v)-путь, а при u = v -- контур.

Последовательность (1) чередующихся вершин и дуг орграфа G, таких что x_i = (v_i-1, v_i) или x_i = (v_i, v_i-1), называется полумаршрутом. Аналогично определяются полуцепь, полупуть и полуконтур.

Если в орграфе существует (u, v) -маршрут, то говорят, что вершина v достижима из вершины u. Любая вершина считается достижимой из себя самой.

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

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

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

На рис. 2, а изображен сильный орграф, на рис. 2, б -- односторонний, а на рис. 2, в -- слабый.

Маршрут, содержащий все вершины орграфа G, называется остовным.

Утверждение 1. Орграф является сильным тогда и только тогда, когда в нем есть остовный циклический маршрут.

Необходимость. Пусть G -- сильный орграф и T = (v₀, x₁, v₁, x₂, v₂,.., x_n, v₀)--его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G -- сильный орграф, то существуют маршруты

T₁ = (v₀, y₁, .., v), T₂ = (v₀, z₁, .., v₀)

Но тогда циклический маршрут

T' = (v₀, x₁, v₁, .., x_n, v₀, y₁, .., v, .., z₁, v₀)

содержит большее, чем Т, число вершин, что противоречит выбору маршрута Т. Следовательно, Т -- остовный маршрут.

Достаточность. Пусть u и v -- две произвольные вершины орграфа G, а

T = (v₀, x, .., v, y, .., v, .., z,.., v₀)

циклический маршрут. Тогда u достижима из v с помощью маршрута (v, у, ..., u)--части маршрута Т, -- а v из u -- с помощью маршрута (u, z, ..., v₀, х, ..., v).

Аналогично доказывается

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

Подграфы и порожденные подграфы ориентированного графа определяются так же, как и для неориентированного. Так же определяются и операции над орграфами.

Введем важное понятие сильной компоненты орграфа. Сильной (или силъносвязной) компонентой ориентированного графа называется любой его максимальный относительно включения сильный подграф.

Очевидно, что отношение взаимной достижимости вершин ориентированного графа G рефлексивно, симметрично и транзитивно. Следовательно, мы получим разбиение множества VG на классы, объединив в один класс все вершины, достижимые друг из друга. Подграфы, порожденные классами этого разбиения, и только они, служат сильными компонентами орграфа G.

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

Орграф G, изображенный на рис. 3, имеет четыре сильные компоненты с множествами вершин {v₁, v₂, v₃, v₄}, {v₅, v₆, v₈}, {v₇} и {v₉}.

Пусть {S₁, S₂, ..., S_m} -- множество всех сильных компонент ориентированного графа G. Конденсацией орграфа G называется орграф G*, вершины s₁, s₂, ..., s_m которого соответствуют сильным компонентам орграфа G, и пара (s_i, s_j) является дугой в G* тогда и только тогда, когда в G есть дуга, начало которой принадлежит компоненте S_i а конец -- S_j.

На рис. 3 представлены орграф G и его конденсация G*.

Утверждение 3. Конденсация G* любого орграфа G не имеет контуров.

Проведем доказательство от противного. Пусть Т = (s₀, x₁, s₁, …, s₀) -- контур в G*. Тогда каждая вершина, входящая в компоненту S_i, достижима из любой вершины, входящей в компоненту S_j. Но это противоречит максимальности сильных компонент.

Неориентированный мультиграф, получающийся в результате снятия ориентации с дуг орграфа G, называется основанием орграфа G и обозначается через G_b.

Очевидно, что орграф является слабым тогда и только тогда, когда его основание -- связный мультиграф.

Орграф называется несвязным, если его основание -- несвязный мультиграф.

Ориентированный граф называется турниром, если его основание является полным графом. Этот класс графов получил свое название в связи со спортивными турнирами без ничьих, проводимыми по круговой системе. Результаты встреч можно описать ориентированным графом, вершины которого соответствуют участникам соревнований, а дуга (u, v) есть в орграфе, если участник u победил участника v.

1.2 Решение заданий 1.1-1.6

Задание 1. По заданной матрице весов графа G выполнить:

1. Преобразовать матрицу весов в матрицу смежности орграфа. По полученной матрице:

2. Построить орграф.

3. Указать для каждой вершины ее степень входа и степень выхода.

4. Построить матрицу инцидентности орграфа.

5. Добавить в орграф дугу таким образом, чтобы одна из сильных компонент орграфа, содержала 3 вершины.

6. Разложить полученный орграф на сильные компоненты по алгоритму.

7. Построить матрицу достижимостей и контрдостижимостей.

- Матрица весов графа G

1) матрица смежности графа G

2) Рисунок 4

3) Степени входы и выхода вершин графа G

Deg⁺v₁=4 Deg^- v₁=0

Deg⁺v₂=1 Deg^- v₂=3

Deg⁺v₃=1 Deg^- v₃=4

Deg⁺v₄=3 Deg^- v₄=1

Deg⁺v₅=3 Deg^- v₅=2

Deg⁺v₆=0 Deg^- v₆=2

4) Матрица инцидентности -- одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки -- вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

5) Добавим дугу e₁₃ начало которой в точке V₃ и конец в точке V₅ (Рисунок 5)

Разложим полученный орграф на сильные компоненты по алгоритму

Г(V₁) : { V₂, V₃, V₄, V₅} Г^-1(V₁) :

Г(V₂) : {V₃, V₅} Г^-1(V₂) : { V₁, V₄, V₅}

Г(V₃) : { V₆, V₅} Г^-1(V₃) : { V₁, V₂, V₄, V₅}

Г(V₄) : { V₂, V₃, V₅} Г^-1(V₄) : { V₄}

Г(V₅) : { V₂, V₃, V₆} Г^-1(V₅) : { V₄, V₃ }

Г(V₆) : Г^-1(V₆) : { V₅, V₃}

R(V₅) = { V₅} { V₂, V₃, V₆} = { V₂, V₃, V₅, V₆}

Q(V₅) = { V₅} { V₄, V₃ } { V₁, V₂} = { V₁, V₂, V_3, V₄, V₅}

S1 = R(v1) Q(v1) = { V₂, V₃, V₅}

Первая Сильная компонента

V S1 = { V₁, V₄, V₆ } ?

R(V₄) = { V₄} { V₂, V₃, V₅} { V₆} = { V₂, V₃, V₄, V₅, V₆}

Q(V₄) = { V₄} { V₄} = { V₁, V₄}

S1 = R(v1) Q(v1) = { V₄}

Вторая сильная компонента

V S2 = { V₁,V₆ } ?

R(V₁) = { V₁} { V₂, V₃, V₄, V₅} { V₆} = { V₁, V₂, V₃, V₄, V₅, V₆}

Q(V₁) = { V₁} = { V₁}

S1 = R(v1) Q(v1) = { V₁}

Третья сильная компонента

V S3 = { V₆ } ?

R(V₆) = { V₆} = { V₆}

Q(V₆) = { V₆} { V₅, V₃} { V₄} = { V₃, V₄, V₅, V₆}

S1 = R(v1) Q(v1) = { V₆}

Четвертая сильная компонента

V S4 = - Алгоритм завершен

6) Матрица достижимости простого ориентированного графа G = (V,E) -- бинарная матрица замыкания по транзитивности отношения E (оно задаётся матрицей смежности графа).

Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Матрица достижимости Матрица контрдостижимости

Графа G Графа G



орграф алгоритм достижимость мультиграф

Глава 2. Понятие неориентированного графа

• Глава 2. Понятие неориентированного графа
• В математической теории графов и информатике граф -- это совокупность непустого множества вершин и множества пар вершин.
• Объекты представляются как вершины, или узлы графа, а связи -- как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
• Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины -- это статьи, а дуги (ориентированные рёбра) -- гиперссылки. Рисунок 6 - пример неориентированного графа

2.1 Определения

Теория графов не обладает устоявшейся терминологией. В различных статьях под одними и теми же терминами понимаются разные вещи. Приводимые ниже определения -- наиболее часто встречаемые.

Граф:

Граф или неориентированный граф G -- это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

V это непустое множество вершин или узлов,

E это множество пар (в случае неориентированного графа -- неупорядоченных) вершин, называемых рёбрами.

V (а значит и E, иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | -- порядком, число рёбер | E | -- размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

Степенью deg V вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

2.2 Решение заданий 1.7-1.13

Задание: По заданной матрице весов графа G (см. таблицу 1) выполнить:

1. Преобразовать полученный орграф в неориентированный граф.

2. Построить неориентированный граф.

3. Перечислить смежные вершины и ребра,

4. Составить для него матрицу смежности.

5. Указать степени вершин графа.

6. Составить матрицу Кирхгофа и матрицу инцидентности.

7. Изменить граф таким образом, чтобы получить: полный граф, мультиграф, псевдограф, дерево. Построить полученные графы.

1) неориентированный графа G^* получаем из ориентированного графа G заменяя дуги ребрами.

2)Рисунок 6

3)смежные вершины:

v₁v_{2 ;} v₁v_{3 ;} v₁v_{4 ;} v₁v_{5 ;} v₂v_{3 ;} v₃v_{6 ;} v₄v_{2 ;} v₄v_{3 ;} v₄v_{5 ;} v₅v_{2 ;} v₅v_{3 ;} v₅v₆

смежные ребра:

e₁e₂ ; e₁e₃ ; e₁e₄ ; e₁e₅ ; e₁e₉ ; e₁e₁₁ ; e₂e₉ ; e₂e₁₁ ; e₂e₃ ; e₂e₆ ; e₂e₁₂ ; e₂e₁₀ ; e₃e₄

e₃e₅ ; e₃e₆ ; e₃e₁₀ ; e₃e₁₂ ; e₄e₅ ; e₄e₉ ; e₄e₈ ; e₄e₁₀ ; e₅e₈ ; e₅e₁₁ ; e₅e₇ ; e₅e₁₂ ; e₆e₁₀

e₆e₁₂ ; e₆e₇ ; e₇e₈ ; e₇e₁₀ ; e₇e₁₂ ; e₈e₉ ; e₈e₁₀ ; e₈e₁₁ ; e₈e₁₂ ; e₉e₁₀ ; e₉e₁₁ ; e₁₀e₁₂

e₁₁e₁₂

4) Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) -- это квадратная матрица A размера n, в которой значение элемента a_ij равно числу ребёр из i-й вершины графа в j-ю вершину.

5) Степени вершин графа G

Degv₁=4

Degv₂=4

Degv₃=5

Degv₄=4

Degv₅=5

Degv₆=2

6) Дан простой граф G с вершинами V(G)=n. Тогда матрица Кирхгофа данного графа будет определяться следующим образом:

Матрица инцидентности -- одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки -- вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

7) полный граф - рисунок 7, мультиграф - рисунок 8, псевдограф - рисунок 9, дерево - рисунок 10

Глава 3. Ориентированные и неориентированные деревья

3.1 Определение

Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

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

Ориентированное (направленное) дерево -- ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.

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

Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина, т.к. в противном случае в графе будет цикл.

Для графов, которые сами по себе не являются деревьями, вводится понятие остовного дерева.

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

Пусть G - связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G)-1 ребер.

Таким образом, любое остовное дерево графа G есть результат удаления из графа G ровно m(G) - (n(G) - 1) = m(G) - n(G) + 1 ребер.

Число v(G) = m(G) - n(G) + 1 называется цикломатическим числом связного графа G.

Одной из самых распространенных задач является задача построения остовного дерева минимальной длины графа. Для решения этой задачи применяется следующий алгоритм.

1) Выберем в графе G ребро минимальной длины. Вместе с инциндентными ему вершинами оно образует подграф G2.

2) Строим граф G3, добавляя к графу G2 новое ребро минимальной длины, выбранное среди ребер графа G, каждое из которых инциндентно какой либо вершине графа G2, и одновременно инциндентно какой - либо вершине графа G, не содержащейся в графе G2.

3) Строим графы G4, G5, …, Gn, повторяя действия пункта 2 до тех пор, пока не переберем все вершины графа G.

3.2 Свойства

Дерево не имеет кратных рёбер и петель.

Любое дерево с n вершинами содержит n ? 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B ? P = 1, где B -- число вершин, P -- число рёбер графа.

Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём.

Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.

Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.

Для любых трех вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

Глава 4. Алгоритмы нахождения кротчайших путей в графе

4.1 Алгоритм Дейкстры (алгоритм расстановки меток)

Неформальное объяснение:

Каждой вершине из V сопоставим метку -- минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово -- на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин -- бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

Задание 2. По заданной матрице весов графа G найти величину минимального пути и сам путь от вершины до конечной вершины или по алгоритму Дейкстры.



1 итерация:

Присваиваем начальной вершине v₁ значение l(v₁)=0, всем остальным вершинам присваиваем .

2 итерация

Выделим все вершины

и припишем им числовые временные метки по формуле .

l(v₂)=5

l(v₃)=8

l(v₄)=7

l(v₅)=18

вершина v₂ становиться постоянной

3 итерация:

Выделим все вершины и припишем им числовые временные метки по формуле .

l(v₃)=8

l(v₄)=7

l(v₅)=18

вершина v₄ становиться постоянной

4 итерация:

Выделим все вершины и припишем им числовые временные метки по формуле .

l(v₃)=8

l(v₅)=13

вершина v₃ становиться постоянной

5 итерация:

Выделим все вершины и припишем им числовые временные метки по формуле .

l(v₅)=13

l(v₆)=24

вершина v₅ становиться постоянной

6 итерация:

Выделим все вершины и припишем им числовые временные метки по формуле .

l(v₆)=24

Алгоритм закончен. Результаты всех итераций зафиксированы в таблице 1

Кратчайший путь из v₁ в v₆: , l(v₆)=24

4.2 Алгоритм Беллмана-Мура (алгоритм корректировки меток)

Алгоритм:

1. Присвоение начальных значений.

s - начальная вершина,

- обозначение текущей вершины,

, ,

- множество вершин в очереди.

2. Корректировка меток в очереди.

Удаляем из очереди Q вершину, находящуюся в самом начале очереди. Для каждой вершины , непосредственно достижимой из , корректируем ее метку по формуле (аналогично алгоритму Дейкстры). Если при этом , то корректируем очередь вершин, иначе продолжаем перебор вершин и корректировку меток.

Корректировка очереди: если вершина не была ранее в очереди и не находится в ней в данный момент, то ставим ее в конец очереди иначе переставляем ее в начало очереди.

,

- удаляем из очереди вершину, находящуюся в начале.

3. Проверка на завершение алгоритма.

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

? Нет. Выполняем 2-ю итерацию, переходим к пункту 2.

Задание 3. По заданной матрице весов графа G найти минимальный путь и сам путь по алгоритму Беллмана-Мура между начальной вершиной и конечной вершиной или .



1 итерация

, , ,

2 итерация

, .

? Да. - вершина ранее в очереди не стояла и в данный момент Q было пусто, поэтому вершина ставится на первое место (конец очереди совпадает с началом).

? Да. - вершина ранее в очереди не стояла, поэтому вершина ставится на последнее место.

3 итерация

, .

? Да.

4 итерация

, .

? Да.

.

? Да.

.

? Да.

5 итерация

,

? Да.

6 итерация

,

? Да.

? Нет.

? Да.

7 итерация

8 итерация

,

? Нет.

.

? Нет.

.

? Нет.

9 итерация



,

? Нет.

.

? Да.

10 итерация

Алгоритм закончен. Результаты всех итераций зафиксированы в таблице 2

Кратчайший путь из v₁ в v₇: , l(v₇)=11

Заключение

В процессе выполнения курсовой работы были изучены основные понятия и определения графов, орграфов, неориентированных и ориентированных деревьев. Изучены свойства вышеперечисленных объектов.

Так же были выполнены задания по построению матриц смежности, инцидентности, достижимости, контрдостижимости, матриц Кирхгофа.

Были изучены два алгоритма нахождения кротчайших путей в графах. Алгоритм Дейкстры и алгоритм Беллмана-Мура.

Список используемой литературы

1) Белоусов А.И., Ткачев С.Б. Дискретная математика 3-е изд. 2004 год. 744с.

2) Яблонский С.В. Введение в дискретную математику. 4-е изд. 2003 год. 384 стр.

3) Н.П. Редькин. Дискретная математика. Курс лекций для судентов-механиков. Уччебник. 2003 год.96 стр.

4) Тишин В.В. Дискретная математика в примерах и задачах. 2008 год. 354 стр

Приложение

Рис. 1.

Рис. 2.

Рис. 3.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Таблица 1:

Итерации	V1	V2	V3	V4	V5	V6	P	L(P)
1	0						V1	0
2		5	8	7	18		V2	5
3			8	7	18		V4	7
4			8		13		V3	8
5					13	25	V5	13
6						24

Таблица 2:

Итерации	V1	V2	V3	V4	V5	V6	V7
1	0
2	0	2			4
3	0	2			4	12
4	0	0		12	4	12	15
5	0	0		12	4	10	15
6	0	0		7	4	10	13
7	0	0		7	4	10	13
8	0	0		7	4	10	13
9	0	0		7	4	10	11
10	0	0		7	4	10	11

Размещено на Allbest.ru