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

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

Министерство образования Российской Федерации

Поморский государственный университет им. М.В. Ломоносова

Математический факультет

Кафедра алгебры и геометрии

КУРСОВАЯ РАБОТА

на тему: «Матрицы в теории графов»

Выполнила студентка

2 курса, 22 группы,

очного отделения

математического факультета

Научный руководитель

Кандидат

физико-математических наук,

доцент кафедры алгебры и геометрии

Архангельск - 2010

Оглавление

Введение

Глава 1. Теоретическая часть

1.1 Основные понятия

1.2 Способы задания графов

1.2.1 Латинская матрица

1.2.2 Матрица смежностей

1.2.3 Матрица инциденций

1.2.4 Матрицы связности и достижимости. Матрица контрдостижимости

1.3 Метрические характеристики графа

1.4 Выявление маршрутов с заданным количеством рёбер

1.5 Определение экстремальных путей на графах. Метод Шимбелла

1.6 Нахождение кратчайших путей. Алгоритм Дейкстры

1.7 Алгоритм нахождения максимального пути

Глава 2. Практическая часть

Заключение

Список литературы

Введение

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

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

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

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

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

Задачами данной работы будут:

1. изучить основные матрицы графов и их теоремы;

2. научиться строить матрицы по графическому рисунку графа и графы по данной матрице;

3. изучить метрические характеристики графов, связанные с матрицами;

4. научиться находить пути графа по матрице (минимальные и максимальные).

теорема путь граф матрица

Глава 1. Теоретическая часть

1.1 Основные понятия

Пусть S - непустое множество, V⁽²⁾ - множество всех его двухэлементных подмножеств, U ? V⁽²⁾.

Пара (S, U) называется неориентированным графом. Элементы множества S называются вершинами графа, а элементы множества U - рёбрами.

Граф G = (S, U) - это конечное множество вершин S и рёбер U.

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

Если концевые вершины совпадают, то дугу называют петлёй.

В графе G могут существовать дуги (рёбра) о одинаковыми концевыми вершинами. Такие дуги называются параллельными.

Если в графе G = (S, U) все элементы множества U изображаются дугами, то граф называется ориентированным или орграфом, если рёбрами, то неориентированным

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

Вершина x₁ и ребро u₁ называются инцидентными, если x1 является концом ребра u₁, и неинцидентными в противном случае.

Граф G называется, простым, если он не содержит петель и параллельных дуг.

Типы графов:

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

- Псевдограф, в нём допускаются петли и кратные рёбра (рис.2).



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

- Направленный граф - это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).

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

Маршрутом в графе G называется чередующаяся последовательность вершин и рёбер u₀, x₁, u₁, … u_n-1, x_n, u_n; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним.

Маршрут называется замкнутым, если u₀ = u_n, и открыт в противном случае.

Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра) различны.

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

Цикл (контур), в котором все вершины попарно различны, называется простым.

Длина маршрута равна n, то есть количеству рёбер в нём.

Расстоянием d(u, v) между двумя вершинами u и v графа G называется длина кратчайшей простой цепи, соединяющей их; если u и v не соединены, то полагаем что

d(u, v) = ?.

Графы, для которых сохраняется отношение инцидентности, называются изоморфными.

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

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

1.2 Способы задания графов

1.2.1 Латинская матрица

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

Рис. 1.1

Таблица 1.1.

	A	B	C	D	E
A		AB	AC
B	BA			BD
C	CA				CE
D		DB
E				ED	EE

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

1.2.2 Матрица смежностей

Наиболее часто граф задают с помощью матриц смежности и инциденций.

Матрицей смежностей А = ||а_ij|| помеченного графа G с p вершинами называется (p_?p)-матрица, в которой а_ij = 1, если вершина u_i смежна с u_j, и а_ij = 0 в противном случае. Строки и столбцы этой матрицы соответствуют вершинам графа, а её (ij) -элемент равен числу кратных рёбер, связывающих вершины v_i и v_j (или направленных от вершины v_i к вершине v_j для орграфа).

Таким образом, существует взаимно однозначное соответствие между помеченными графами с p вершинами и симметрическими бинарными (p_?p)-матрицами с нулями на диагонали. На рисунке 1.2 показаны помеченный граф G и его матрица смежностей А. Легко заметить, что суммы элементов матрицы А по строкам равны степеням вершин графа G.

Рис. 1. 2. Помеченный граф и его матрица смежностей

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

Элементы матрицы определяются следующим образом:

для неориентированного графа:

для ориентированного графа:

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

Доказательство: Рассмотрим два графа G₁ и G₂, которые отличаются друг от друга лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, сохраняющая их смежность: вершины x₁ и x₂ тогда и только тогда смежны в G, когда их образы y₁ = s(x₁) и y₂ = s(x₂) смежны в G₁. Тогда, если P(G) = P и P(G₁) = P⁽¹⁾, то p_s(i)s(j)=p_ij, i, j = (1, n).

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

Пример 1. Доказать, что графы изоморфны (рис. 1.3).

Рис. 1.3

Решение: воспользуемся теоремой и проанализируем матрицы смежности данных графов.

Видно, что Р₂= Р₃. Если одновременно переставить в Р₂ вторую и пятую строки и второй и пятый столбец, то получится матрица Р₁. Следовательно, по теореме все три указанных графа изоморфны.

Из доказанной теоремы следует, что ранги матриц смежности изоморфных графов совпадают. Это позволяет ввести для графа следующее определение ранга: рангом графа называется ранг его матрицы смежности. Обозначается ранг графа - rankG,

В Примере 1 rankР₁ = 2, следовательно, rankG₁ = 2.

Аналогично можно определить и матрицу смежности дуг. Это так же квадратная матрица m_?m порядка, где m - число дуг.

Пример 2. Рассмотрим следующий граф (рис. 1.4):

Рис. 1.4

Элементы q_ij матрицы смежности дуг равны единице, если дуга u_i непосредственно предшествует дуге u_j, и равны нулю в остальных случаях. Для неориентированного графа элемент qij равен единице, если u_i и u_j смежны, и нулю в остальных случаях.

Утверждение: Для того, чтобы n-вершинный граф G с матрицей смежности A = A (G) имел хотя бы один контур, необходимо и достаточно, чтобы матрица K = A² + A³ +…+Aⁿ имела ненулевые диагональные элементы.

Доказательство:

Достаточность: Пусть K = [k_ij] и для некоторого номера i выполняется k_ij>0. в этом случае для некоторого r из {2, …, n} справедливо a^(r)_ii>0, а следовательно найдётся путь в G из x_i в x_i. Но тогда в силу того, что в графе G из всякого цикла можно выделить простой цикл, в орграфе G найдётся простой контур.

Необходимость: Пусть в графе G имеется некоторый контур. Так как из всякого контура можно выделить простой контур, нетрудно увидеть, что длина простого контура не превышает числа вершин n. Но тогда в силу того, что элемент матрицы ориентированного графа равен числу всех путей длины l, то для любой вершины x_i, принадлежащей некоторому простому контуру длины l, где 2 ? l ? n, элемент a^(l)_ii матрицы A^l отличен от нуля, а следовательно, и элемент k_ii матрицы К отличен от нуля.

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

1.2.3 Матрица инциденций

Другой матрицей, связанной с графом G, в котором помечены и вершины и рёбра, является матрица инциденций B = |b_ij|. В этой (pxq)-матрице b_ij = 1, если v_i и x_j инцидентны, и b_ij = 0 а противном случае. Как и матрица смежностей, матрица инциденций определяет граф G с точностью до изоморфизма. На самом деле уже любые p-1 строки матрицы B определяют G, поскольку каждая строка равна сумме по модулю 2 всех остальных строк.

Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-ый элемент равен 1, если вершина v_i инцидентна ребру х_j,и равен нулю, если v_i и х_j не инцидентны.

Для неориентированного графа элементы данной матрицы задаются следующим образом:

Для ориентированного графа элементы матрицы задаются так:

Строки матрицы инциденций называют векторами инциденций графа G. Матрица инциденций также однозначно определяет структуру графа. Для матрицы инциденций справедлива теорема, аналогичная для матрицы смежности.

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

Доказательство: Рассмотрим два графа G₁ и G₂, которые отличаются друг от друга лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, сохраняющая их инцидентность: вершины x₁ и x₂ тогда и только тогда инцидентны в G, когда их образы y₁ = s(x₁) и y₂ = s(x₂) инцидентны в G₁. Тогда, если P(G) = P и P(G₁) = P⁽¹⁾, то p_s(i)s(j)=p_ij, i, j = (1, n).

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

Пример 3: Рассмотрим граф (Рис. 1.5)

Рис. 1.5

Его матрица инциденций имеет вид:

1.2.4 Матрицы связности и достижимости. Матрица контрдостижимости

Определим матрицы связности и достижимости. Пусть P(G) - матрица смежности вершин графа G = (S_n, U), а B = E + P + P² + … + Pⁿ. Введём матрицу C = (cij), i,j = (1, n) по правилу:

Матрица С называется матрицей связности, если G - неориентированный граф, и матрицей достижимости, если G - ориентированный. Это значит, что в графе G тогда и только тогда существует маршрут из вершины x_i в x_j, когда c_ij = 1.

Таким образом, в матрице С содержится информация о существовании связей между различными элементами графа G посредством маршрутов.

Матрица контрдостижимости L = (l_ij), i, j = (1, n), определяется следующим образом:

Можно показать, что L = C^Т. Матрицы C и L используются для нахождения сильных компонент графа.

Пусть F = C*L, где операция * означает поэлементное произведение матриц С и L: f_ij = c_ij l_ij. Элемент f_ij матрицы F равен единице тогда и только тогда, когда вершины x_i и x_j взаимно достижимы, т. е. x_i достижима из x_j, а x_j - из x_i. Таким образом, сильная компонента орграфа, содержащая вершину x_i, состоит из элементов x_j, для которых f_ij = 1.

Пример 4: Матрицы достижимости С и контрдостижимости L для данного графа равны

Рис. 1.6

По матрице F легко определить состав вершин трёх подграфов, образующих сильно связанные компоненты исходного графа:

1. x_i;

2. x₂, x₃, x₄;

3. x₅, x₆.

1.3 Метрические характеристики графа

Рассмотрим связный граф G = (S, U), пусть x₁ и x₂ - две его вершины. Длина кратчайшего (x₁, x₂)-маршрута называется расстоянием между вершинами x₁ и x₂, обозначается через d(x₁ , x₂). Очевидно, что расстояние между вершинами является простой цепью и d(x₁ , x₂)=0. Для любой вершины x величина e(x) = max d(x, y) называется эксцентриситетом вершины x. Максимальный из всех эксцентриситетов называется диаметром графа и обозначается d(G), т. е. d(G) = max e(x) = max max d(x, y).

Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через r(G): r(G) = min e(x) = min max d(x, y).

Вершина x называется периферийной, если её эксцентриситет равен диаметру графа, т. е. e(x) = d(G). Простая цепь, расстояние между концами которой равно d(G), называется диаметральной цепью.

Теорема: Для любого связного графа G справедливо неравенство d(G) ? rankG.

Доказательство: Пусть d(G) = d и x₁, x₂, …, x_d+1 - одна из диаметральных цепей графа G. Рассмотрим матрицу смежности вершин P(G) и выберем нумерацию вершин так, чтобы вершины x₁, x₂, …, x_d+1 имели номера 1, 2, … , d+1 соответственно. Так как цепь x₁, x₂, …, x_d+1 является подграфом G? ? G, то P(G) =( )представляет собой клеточную матрицу, в левом верхнем углу которой из-за выбранной нумерации вершин расположена матрица смежности подграфа G?. Этот подграф - простая цепь, т. е.

- симметричная матрица порядка d + 1, все элементы которой, за исключением двух ближайших к главной диагонали полос, равны нулю. Минор порядка d матрицы А, остающийся после вычёркивания первого столбца и последней строки, равен единице. Следовательно, rank G = rank P(G) ? rank A ? d = d(G), т. е. rank = G d(G).

Вершина x называется центральной, если e(x) = r(G). Множество всех центральных вершин графа называется его центром. Центром может быть единственная вершина графа или несколько вершин (рис. 1.7). Здесь e(x₁)=e(x₂)=e(x₄)=e(x₆)=3, e(x₃) = e(x₇) = 4, e(x₅) = 2. Таким образом, d(G) = 4, R(G) = 2. Периферийные вершины: x₃ и x₇, диаметральные цепи: x₃ - x₂ - x₅ - x₆ - x₇ и x₃ - x₄ - x₅ -x₆ -x₇, центральная вершина x₅.

Рис. 1.7

1.4 Выявление маршрутов с заданным количеством рёбер

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

Теорема: Для определения количества маршрутов, состоящих из k рёбер (дуг), необходимо возвести в k-ую степень матрицу смежности вершин. Тогда элемент p даст количество маршрутов длины k (состоящих из k рёбер) из вершины x_i в вершину x_j.

Доказательство: Используем индукцию по k. Для k = 1 маршрут длины 1 как раз является ребром G, следовательно, результат теоремы при k = 1 вытекает из определения матрицы смежности А. Пусть результат имеет место для k - 1.

где L_iq - число маршрутов длины (k-1) от v_i к v_q, a_qj - число маршрутов длины 1 от v_q к v_j. Следовательно, L_iq * a_qj - число маршрутов длины k из v_i в v_j, где vq - предпоследняя вершина маршрута. Отсюда следует, что n SUM L_iq * a_qj есть число маршрутов длины k от v_i к v_j. q = 1

Пример 5. Рассмотрим неориентированный граф, изображенный ниже (Рис. 1.8).

Рис. 1.8

Составим матрицу смежности вершин и возведем ее в квадрат.

Результат возведения:

Рассмотрим первую строку. Элемент p= 3. Это значит, что существуют три маршрута из А в А длиной два ребра. Действительно, это маршруты Au₁Bu₁A, Au₂Cu₂A, Au₃Du₃A. Из А в B существуют два маршрута: Au₂Cu₅B, Au₃Du₄B. Если использовать числовую матрицу смежности вершин, то для нахождения самих маршрутов необходимо работать с графом. Если же воспользоваться модифицированной матрицей смежности, в ячейки которой записаны названия ребер, то можно получить не только количество маршрутов, но и сами маршруты.

Действительно, для данного примера имеем:

Аналогично обстоит дело и с орграфом. У него матрица смежности вершин несимметрическая.

Пример 6: Рассмотрим следующий орграф (Рис. 1.9) и определим все маршруты с тремя ребрами.



Рис. 1.9

Матрица смежности и результаты ее возведения в квадрат и куб находятся ниже.

Рассмотрим элемент p после возведения матрицы смежности вершин в квадрат. p = 2, то есть из вершины В в вершину В есть два маршрута длиной две дуги. Это маршруты и Bu₃Cu₄B и Bu₂Au₁B. После возведения матрицы в куб сохраняется та же картина. Например, p= 2; это значит, что есть два маршрута длиной три дуги из вершины А в вершину В. Это маршруты Au₁Bu₂Au₁В и Au₁Bu₃Сu₄В. Для получения цепей (маршрутов, в которых каждое ребро встречается один раз) нужно в модифицированной матрице P³ вычеркнуть те слагаемые, в которых какой-либо сомножитель встречается более одного раза.

1.5 Определение экстремальных путей на графах. Метод Шимбелла

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

1). Операция умножения двух величин a и b при возведении матрицы в степень соответствует их алгебраической сумме, то есть

2). Операция сложения двух величин a и b заменяется выбором из этих величин минимального (максимального) элемента, то есть

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

С помощью этих операций длины кратчайших или максимальных путей между всеми вершинами определяются возведением в степень весовой матрицы ?, содержащей веса рёбер. Например, элементы матрицы ?² вычисляют следующим образом:

щ= min (max){( щ + щ), (щ + щ), …, (щ + щ)}.

Аналогично находят элементы k-ой степени матрицы ?.

Пример 7: Составим для указанного графа (Рис 1. 10) матрицу весов. Она определяет все маршруты, состоящие из одного ребра. Найдем кратчайшие пути из двух ребер, для этого возведем эту матрицу в квадрат с учетом операций Шимбелла (min - кратчайшие пути).

Рис. 1. 10

Например: щ = min{( щ + щ), (щ + щ), (щ + щ), (щ + щ)} = min{(0 + 0), (1 + 2), (3 + 0), (2 + 0)} = min {0, 3, 0, 0} = 3.

Аналогично, кратчайшими путями из трёх рёбер будут

и так далее. Например, длина кратчайшего пути из трёх рёбер из вершины D в вершину С равна 7. это путь DBAC.

1.6 Нахождение кратчайших путей. Алгоритм Дейкстры

Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):

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

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

Теперь рассмотрим алгоритм нахождения кратчайшего пути между двумя заданными вершинами в ориентированном графе. Пусть G = {S, U, ? } - ориентированный граф со взвешенными дугами. Обозначим s-вершину - начало пути и t-вершину - конец пути.

Алгоритм Дейкстры содержит одно ограничение - веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути, на втором строится сам путь от вершины s к вершине t.

Этап 1. Нахождение кратчайшего пути.

Шаг 1. Присвоение вершинам начальных меток.

Полагаем d(s)=0* и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин x_iS, x_i ?s полагаем d(x_i) = ? и считаем эти метки верными. Пусть x” = s, x” - обозначение текущей вершины.

Шаг 2. Изменение меток.

Для каждой вершины x_i с временной меткой, непосредственно следующей за вершиной x”, меняем ее метку в соответствии со следующим правилом:

d_нов.(x_i) = min{d_стар.(x_i), d(x”)+щ(x”, x_i)}.(1. 6. 1)

Шаг 3. Превращение метки из временной в постоянную.

Из всех вершин с временными метками выбираем вершину x_j* с наименьшим значением метки

d(x_j*) = min {d(x_j) / x_jS, d(x_j) - временная}. (1. 6. 2)

Превращаем эту метку в постоянную и полагаем x” = x_j*.

Шаг 4. Проверка на завершение первого этапа.

Если x” = t, то d(x”) - длина кратчайшего пути от s до t. В противном случае происходит возвращение ко второму шагу.

Этап 2. Построение кратчайшего пути.

Шаг 5. Последовательный поиск дуг кратчайшего пути.

Среди вершин, непосредственно предшествующих вершине x” c постоянными метками, находим вершину x_i, удовлетворяющую соотношению

d(x”) = d(x_i) + щ(x_i, x”).(1. 6. 3)

Включаем дугу (x_i, x”) в искомый путь и полагаем x” = x_i.

Шаг 6. Проверка на завершение второго этапа.

Если x” = s, то кратчайший путь найден - его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.

Пример 8: Задана весовая матрица ? графа G. Найти минимальный путь из вершины x₁ в вершину x6 по алгоритму Дейкстры.

Рис. 1. 11

На рисунке 1. 11 изображён сам граф по данной матрице весов. Поскольку на данном графе есть цикл между вершинами x₂, x₃ и x₅, то вершины графа нельзя упорядочить по алгоритму Фалкерсона. На рисунке графа временные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.

Этап 1.

Шаг 1. Полагаем d(x₁) = 0*, x” = x₁, d(x₂) = d(x₃) = d(x₄) = d(x₅) = d(x₆) = ?.

1-ая итерация.

Шаг 2. Множество вершин, непосредственно следующих за x” = x1 со временными метками S” = {x₂, x₄, x₅}. Пересчитываем временные метки вершин: d(x₂) = min{?, 0*, + 9} = 9, d(x₄) = min{?, 0* + 6} = 6, d(x₅) = min{?, 0* + 11} = 11.

Шаг 3. Одна из временных меток превращается в постоянную min{9, ?, 6, 11, ?} = 6* = d(x₄), x” = x₄.

Шаг 4. x” = x₄ ? t = x₆, происходит возвращение на второй шаг.

2-ая итерация.

Шаг 2. S” = {x₂, x₃, x₅}, d(x₂) = min{9, 6* + 5} = 9, d(x₃) = min {?, 6* + 7} = 13, d(x₅) = min{11, 6* + 6} = 11.

Шаг 3. min{d(x₂), d(x₃), d(x₅), d(x₆)} = min{9, 13, 11, ?} = 9* = d(x₂), x” = x₂.

Шаг 4. x₂ ? x₆, возвращение на второй шаг.

3-я итерация.

Шаг 2. S” ={x₃}, d(x₃) = min{13, 9* + 8} = 13.

Шаг 3. min{d(x₃), d(x₅), d(x₆)} = min{31, 11, ?} = 11* = d(x₅), x” = x₅.

Шаг 4. x₅ ? x₆, возвращение на второй шаг.

4-ая итерация.

Шаг 2. S”={x₆}, d(x₆) = min{?, 11* + 4} = 15.

Шаг 3. min {d(x₃), d(x₆)} = min{13, 15} = 13* = d(x₃), x” = x₃.

Шаг 4. x₃ ? x₆, возвращение на второй шаг.

5-ая итерация.

Шаг 2. S” = {x₆}, d(x₆) = min{15, 13* + 9} = 15.

Шаг 3. min{d(x₆₎} = min{15} = 15*, x” = x₆.

Шаг 4. x₆ = t = x₆, конец первого этапа.

Этап 2.

Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x₆ с постоянными метками S” = {x₃, x₅}. Проверим для этих двух вершин выполнение равенства d_нов.(x_i) = min{d_стар.(x_i), d(x”) + щ(x”, x_i)}:

d(x”) = 15 = 11* + 4 = d(x₅) + щ(x₅, x₆),

d(x”) = 15 ? 13* + 9 = d(x₃) + щ(x₃, x₆).

Включаем дугу (x₅, x₆) в кратчайший путь. x” = x₅.

Шаг 6. x” ? s = x₁, возвращение на пятый шаг.

2-ая итерация.

Шаг 5. S” = {x₁, x₄}.

d(x”) = 11 = 0* + 11 = d(x₁) + щ(x₁, x₅),

d(x”) = 11 ? 6* + 6 = d(x₄) + щ(x₄, x₅).

Включаем дугу (x₁, x₅) в кратчайший путь. x” = x₁.

Шаг 6. x” = s = x₁, завершение второго этапа.

Итак, кратчайший путь от вершины x₁ до вершины x₆ построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг: м = (x₁, x₅) - (x₅, x₆).

1.7 Алгоритм нахождения максимального пути

Для нахождения максимального пути граф G (сеть) должен быть ациклическим, ибо в противном случае может оказаться, что длины некоторых путей не ограничены сверху. Если G_n - ациклический граф, то для любых двух его вершин x_i ? x_j выполняется одно из двух условий:

1. x_i предшествует x_j, x_iS_предш (x_j);

2. x_i следует за x_j, x_iS_след (x_j);

3. нет пути между x_i и x_j.,

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

Перед вычислением максимального пути в орграфе необходимо упорядочить вершины графа по алгоритму Фалкерсона.

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

Пусть d_j - длина максимального пути от вершины x₁ до вершины x_j, тогда величина d_j удовлетворяет следующим рекуррентным соотношениям (1. 2. 5):

Соотношения (1. 2. 5) позволяют легко вычислить длины максимальных путей от s = x₁ до вершин, достижимых из вершины s. Сами пути могут быть построены методом последовательного возвращения (второй этап в алгоритме Дейкстры).

Пример 9: Граф (рис. 1.12) задан матрицей весов ?. Найти максимального пути из вершины x₁ в x₆ и сам этот путь.

Рис. 1. 12

Этот граф ациклический, поэтому возможно упорядочение его вершин по алгоритму Фалкерсона. Сделаем это графическим способом (рис. 1.13), переобозначив две вершины: x₄ назовём x, а x₃ - x, и применим рекуррентные формулы (1.2.5)

Рис. 1. 13

Этап 1.

d₁ = 0,

d₂ = max (d₁ + 4) = 4,

d = max (d₁ + 6, d₂ + 8) = max (0 + 6, 4 + 8) = 12,

d = max (d + 8, d₂ + 7) = max (12 + 8, 4 + 7) = 20,

d₅ = max (d + 7, d + 9, d2 + 6) = max (20 + 7, 12 + 9, 4 + 6) = 27,

d₆ = max (d₅ + 3, d + 5) = max (27 + 3, 20 + 5) = 30.

Итак, длина максимального пути их x₁ в x₆ равна 30.

Этап 2.

x₆ : d₆ = 30 = d₅ + 3 = 27 +3 - включаем дугу (x₅, x₆) в максимальный путь, d₆ = 30 ? d + 5 = 20 + 5.

x₅ : d₅ = 27 ? d + 7 = 20 + 7 - включаем дугу (x, x₅) в максимальный путь,

d₅ = 27 ? d + 9 = 12 + 9, d₅ = 27 ? d₂ + 6 = 4 +6.

x: d = 20 = d+ 8 = 12 + 8 - включаем дугу (x, x) в максимальны путь,

d = 20 ? d₂ + 7 = 4 +7.

x: d = 12 = d₂ + 8 = 4 + 8 - включаем дугу (x₂, x) в максимальный путь,

d = 12 ? d₁ +6 = 0 + 6.

x₂ : d₂ = 4 = d₁ +4 = 0 + 4 - включаем дугу (x₁, x₂) в максимальный путь.

Итак, искомый путь таков: м_max=(x₁, x₂)-(x2, x)-(x, x)-( x, x₅)-(x₅, x₆) или в первоначальных обозначениях м_max=(x₁, x₂)-(x₂, x₄)-(x₄, x₃)-(x₃, x₅)-(x₅, x₆)

Глава 2. Практическая часть

Применение способов задания графов.

Задача 1. Для графов, изображённых на рисунке 2.1, составить матрицы смежности вершин, смежности дуг и инциденций.

Рис. 2.1

Решение задачи 1.

Задача 2: По матрице смежности построить наглядное изображение графа.

Решение задачи 2:

Рис. 2.2

Задача 3: Показать, что графы изоморфны (Рис. 2. 3).

Рис. 2.3

Решение задачи 3: Воспользуемся теоремой и рассмотрим матрицы смежности графов. Заметим, что они равны, следовательно графы являются изоморфными.

= А (матрица смежности первого и второго графов)

Задача 4. Доказать, что графы на рисунке 2. 4 не изоморфны.



Решение задачи 4: Построим матрицы смежности вершин для данных графов.

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

Задача 5: Найти матрицу достижимости С для данного графа

Рис. 2.5

Решение задачи 5:

Находим матрицу смежности данного графа (рис. 2.5), Р. Затем находим Р², Р³ и Р⁴. Складываем данные матрицы и матрицу Е. Находим матрицу достижимости графа:



Задача 6. Найти матрицы сильных компонент связи для графа, изображённого на рисунке 2. 6.

Решение задачи 6: Находим матрицу смежности графа, возводим её в степени от 2 до 5. Находим матрицу В, и затем матрицу достижимости и контрдостижимости. Затем, путем перемножения последних двух матриц, получаем матрицу, по которой определяем сильные компоненты связи.

По матрице F можно сказать, что граф содержит три сильные компоненты связности. Первая сильная компонента состоит из вершины x₁, вторая сильная компонента из вершины x₂ и третья - из вершин x₃, x₄, x₅.

Задача 7: Найти матрицы сильных компонент связи для графа, изображённого на рисунке 2. 7.

Рис. 2.7

Решение задачи 7: Решение аналогично предыдущему заданию.

Задача 8. Найти ранг графа, приведённого на рисунке 2. 8.

Решение задачи 8: Ранг графа равен рангу его матрицы смежности. Следовательно, построим матрицу смежности данного графа и найдём её ранг, приводя матрицу к ступенчатому виду.

Ранг полученной матрицы смежности равен 5, тогда и rangG = 5.

Задача 9: Определить, имеют ли контуры орграфы с матрицами смежности

Решение задачи 9:

а) n = 4,

На диагонали присутствуют нулевые элементы, следовательно, граф имеет контур.

На диагонали присутствуют ненулевые элементы, следовательно, граф имеет контур.

Задача 10: По заданной матрице весов ? графа G найти величину минимального пути и сам путь от вершины s = x₁ до вершины t = x₆ по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами:

Решение задачи 10:

Построим граф по данной матрице (Рис. 2. 9).

В данном графе нет цикла, поэтому упорядочим его с помощью алгоритма Фалкерсона.

Вершина х₁ не содержит входящий дуг, отнесем ее к первой группе. Вычеркнем все дуги, исходящие из х₁, получим граф без трёх рёбер (х₁ - х₂, х₁ - х₄, х₁ - х₅). В нём опять находим одну вершину, в которую не заходит ни одна дуга. Это вершина х₄ (вторая группа). Вычеркнем дуги, исходящие из вершины х₄. получим граф только с четырьмя рёбрами (х₂ - х₃, х₃ - х₆, х₅ - х₃, х₅ - х₂). Появилась ещё одна вершина х₅ (группа 3), в которую не входят рёбра, вычеркнем исходящие из неё дуги. Получим вершину х₂, которая входит в группу 4, х₃ - в группу 5 и х₆ - в группу 6.

Получен упорядоченный граф (Рис. 2. 10):

Рис. 2.10

Этап 1.

Шаг 1. Полагаем, что d(x₁) = 0*, x” = x₁.

d(x₂) = d(x₃) = d(x₄) = d(x₅) = d(x₆) = ?.

1-ая итерация

Шаг 2. Множество вершин, непосредственно следующих за х = х₁ с временными метками S” = {x₂, x₄, x₅}. Пересчитываем временные метки этих вершин: d(x₂) = min{?, 0*+11} = 11, d(x₄) = min{?, 0*+14} = 14, d(x₅) = min{?, 0*+15} = 15.

Шаг 3. Одна из временных меток превращается в постоянную. min{11, ?, 14, 15, ?} = 11* = d(x₂), x” = x2.

Шаг 4. x” = x₂ ? x₆, происходит возвращение на второй шаг.

2-ая итерация

Шаг 2. S” = {x₃}, d(x₃) = min{11, 11*+13} = 11.

Шаг 3. min{11} = 11* = d(x₃), x” = x3.

Шаг 4. x₃ ? x₆, происходит возвращение на шаг 2.

3-я иетерация

Шаг 2. S” = {x₆}, d(x₆) = min{29, 11*+11+14} = 29.

х₆=x₆, конец первого этапа.

Этап 2.

Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x₆ с постоянными метками. S”={x₃, x₅}. Проверим для этих двух вершин выполнение равенства

d(x”) = d(x_i) + щ(x_i, x”).

d(x”) = 29 = 15*+14 = d(x₅) + щ(x₅, x₆),

d(x”) = 29 ? 23*+14 = d(x₃) + щ(x₃, x₆).

Включаем дугу (x₅, x₆) в кратчайший путь; x” = x₅.

Шаг 6. x” ? x₁, переходим на шаг 5.

2-ая итерация

Шаг 5. S” = {x₁, x₄},

d(x”) = 15 = 0*+15 = d(x₁) + щ(x₁, x₅),

d(x”) = 15 ? 14+9 = d(x₄) + щ(x₄, x₅).

Включаем дугу (x₁, x₅) в кратчайший путь. x” = x₁.

Шаг 6. x” = x₁. Завершение второго этапа.

Итак, кратчайший путь из вершины х₁ в х₆ построен. Его длина (вес) равна 29. Сам путь образует следующая последовательность дуг: м_min = (х₁, х₅)-(х₅, х₆).

Задача 11: Найти величину максимального пути и сам путь между вершинами s = x₁ и t = x₆ (матрица из задачи 10)

Решение задачи 11:

Этап 1

d₁ = 0,

d₄ = max{d₁+14} = 14

d₅ = max{d₄+9, d₁+15} = max{15, 23} = 23

d₂ = max{d₁+11, d₄+7, d₅+11} = max{11, 21, 34} = 34

d₃ = max{d₂+13, d₄+11, d₅+10} = max{47, 25, 33} = 47

d₆ = max{d₃+13, d₅+14} = max{60, 37} = 60.

Итак, длина максимального пути из х₁ в х₆ равна 60.

Этап 2

*x₆ : d₆ = 60 = x₃+13 - включаем дугу (х₃, х₆) в максимальный путь, d₆ = 60 ? d₅+14=37.

*x₃ : d₃ = 47 = d₂+13 = 34+13 - включаем дугу (x₂, x₃) в максимальный путь,

d₃ = 47 ? d₄+11 = 25,

d₃ = 47 ? d₅+10=33.

*x₂ : d₂ = 34 = d₅+11 - включаем дугу (х₅, х₂) в максимальный путь,

d₂ = 34 ? d₁+11,

d₂ = 34 ? d₄+7.

*x₅ : d₅ = 23 = d₁+15 - включаем дугу (x₁, x₅) в максимальный путь,

d₅ = 23 ? d₄+9.

*x₄ : d₄ = 14 = d₁+14 = 0+14 - включаем дугу (х₁, х₄) в максимальный путь.

итак, искомый путь таков:м_max = (x₁, x₄)-(x₄, x₅)-(x₅, x₂)-(x₂, x₃)-(x₃, x₆)

Задача 12: По заданной матрице весов ? графа G найти величину минимального пути и сам путь от вершины s = x₁ до вершины t = x₆ по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами:



Решение задачи `12:

Нарисуем граф (Рис. 2.11) по данной матрице, упорядочим его вершины по алгоритму Фалкерсона. Получим граф, изображённый на рисунке 2. 12.

Рис. 2.11

Рис. 2.12

Для нахождения минимального пути используем алгоритм Дейкстры.

Этап 1

Шаг 1. Полагаем, что d(x₁) = 0*, x” = x₁.

d(x₂) = d(x₃) = d(x₄) = d(x₅) = d(x₆) = ?.

1-ая итерация

Шаг 2. Множество вершин, непосредственно следующих за х = х₁ с временными метками S” = {x₂, х₃}. Пересчитываем временные метки этих вершин: d(x₂) = min{?, 0*+8} = 8, d(x₃) = min{?, 0*+10} = 10.

Шаг 3. Одна из временных меток превращается в постоянную. min{8, ?, 10} = 8* = d(x₂), x” = x₂.

Шаг 4. x” = x₂ ? x₆, происходит возвращение на второй шаг.

2-ая итерация

Шаг 2. S” = {x₃, х₄, х₅}, d(x₃) = min{10, 8*+10} = 10,

d(x₄) = min{?, 8*+9} = 17, d(x₅) = min{?, 8*+12} = 20.

Шаг 3. min{10, 17, 20} = 10* = d(x₃), x” = x₃.

Шаг 4. x₃ ? x₆, происходит возвращение на шаг 2.

3-я итерация

Шаг 2. S” = {x₄, х₅, x₆}, d(x₄) = min{17, 10*+10} = 17, d(x₅) = min{20, 10*+12} = 20, d(x₆) = min{?, 10*+7} = 17.

х₆ = х₆, конец первого этапа

Этап 2

Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x₆ с постоянными метками. S”={x₃, x₄, х₅}. Проверим для этих двух вершин выполнение равенства d(x”) = d(x_i) + щ(x_i, x”). В итоге включаем дугу (x₁, x₃) в кратчайший путь, затем таким же образом дугу (х₃, х₆).

Итак, кратчайший путь из вершины х₁ d х₆ построен. Его длина (вес) равна 17. Сам путь образует следующая последовательность дуг: м=(х₁, х₃)-(х₃, х₆).

Задача 13: Используя матрицу из задачи 8, построить максимальный путь из вершины х₁ в вершину х₆.

Решение задачи 13:

Этап 1

d₁ = 0,

d₂ = max{d₁+8} = 8

d₃ = max{d₁+10, d₂+10} = max{10, 18}=18

d₄ = max{d₂+9, d₃+10} = max{17, 28} = 28

d₅ = max{d₃+12, d₄+9, d₂+12} = max{30, 37, 20} = 37

d₆ = max{d₃+7, d₄+13, d₅+11} = max{25, 41, 48} = 48.

Итак, длина максимального пути из х₁ в х₆ равна 48.

Этап 2

*x₆ : d₆ = 48 = d₅ + 11 - включаем дугу (х₅, х₆) в максимальный путь.

*x₅ : d₅ = 37 = d₄+9 - включаем дугу (x₄, x₅) в максимальный путь,

*x₄ : d₄ = 28 = d₃+10 - включаем дугу (х₃, х₄) в максимальный путь,

*x₃ : d₃ = 18 = d₂+10 - включаем дугу (x₂, x₃) в максимальный путь,

*x₂ : d₂ = 8 = d₁+8 - включаем дугу (х₁, х₂) в максимальный путь.

Итак, искомый путь таков:м_max = (x₁, x₂)-(x₂, x₃)-(x₃, x₄)-(x₄, x₅)-(x₅, x₆).

Заключение

В данной курсовой работе я рассмотрела основные виды матриц из теории графов: латинская матрица, матрица смежности, инцидентности, достижимости и контрдостижимости, связности. С помощью матриц смежности и инциденций научилась определять, являются ли графы изоморфными. Рассмотрены теоремы по данному пункту.

Так же рассмотрены некоторые метрические характеристики графа, такие как ранг, расстояние, радиус и другие.

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

В практической части курсовой работы представлен ряд упражнений по данной теме.

Цель и задачи, которые ставились вначале данной работы, выполнены.

Список литературы

1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ. - М.: Издательский дом «Вильямс», 2003.

2. Баврин И. И. Дискретная математика. - М.: Высш. шк., 2007.

3. Нефёдов В. Н., Осипова В. А. Курс дискретной математики. - М.:Изд-во МАИ, 1992.

4. Новиков С.А. Дискретная математика для программистов - СПб.: Питер, 2001.

5. Оре О. Графы и их применение. - М.: Мир,1973.

6. Редькин Н. П. Дискретная математика. - СПб.: Издательство «Лань», 2003.

7. Уилсон Р. Введение в теорию графов. - М.: Мир, 1977.

8. Шапорев. С. Д. Дискретная математика. Курс лекций и практических занятий. - СПБ.: БХВ-Петербург, 2007.

9. Харари Ф. Теория графов. - М.: Мир, 1973.

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