Материал: Diskretnaya_matematika

Составление цикломатической матрицы

где

Составление матрицы разрезов

где

Замечание.Символобозначает операцию сложения по модулю 2. Результат этой операции равен 0, если арифметическая сумма чисел есть четное число, и равен 1–в противном случае.

Цикломатическая матрица Cи матрица разрезовSявля­ются ортогональными, что математически выражается матричным уравнением:CS^T=. ЗдесьS^T– транспони­рованная матрицаS, а– нулевая матрица.

Ортогональность матриц CиSобусловлена тем, что множество хорд, порождающих базисные циклы, и множество ветвей, порождающих базисные разрезающие множества, не пересекаются (рис. 3.30). Легко проверить ортогональность полученных матриц.

3.8. Задача определения путей в графах

3.8.1. Определение путей в графе

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

Граф G(X) с двумя отмеченными вершинамиx_i,x_jназы­вается (x_i,x_j) – плоским, если графG^(X)=G(X)(x_i,x_j), полученный до­бавлением кG(X) ребра (x_i,x_j), является плоским.

Рассмотрим алгоритм определения пути, ведущего из вершины x_iвx_jплоского графа. Еслиx_iне является вершиной никакого про­стого цикла, то при определении алгоритма пути изx_iвx_jв графеG(X) всегда выбирается самый левый или правый коридор (ребро) (рис. 3.33).

–путь при выборе левого коридора;

–путь при выборе правого коридора.

Аналогичный алгоритм определения пути в прадереве предпо­лагает следующие действия. Из корня идти по какой-либо ветви насколько возможно далеко, затем возвратиться на какой-нибудь перекресток и отправиться по новому направлению (еще не прой­денному) и т.д. Искомый путь из x_iвx_jбудет состоять из всех тех ребер, которые в процессе поиска были пройдены по одному разу.

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

Рис. 3.33. Определение пути в графе

При определении пути в графе с помощью алгоритма Тарринеобходимо в данном алгоритме пользоваться правилом:

а) не проходить дважды по одному ребру в одном и том же направлении;

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

3.8.2. Алгоритм определения кратчайших путей

Эта задача имеет большое значение в практических примене­ниях. К ней сводятся многие задачи выбора наиболее экономичного (с точки зрения расстояния или стоимости) маршрута на имеющейся карте дорог, наиболее экономичного способа перевода динамиче­ской системы из одного состояния в другое и т.д. Существует много математических способов решения, но часто методы, основанные на теории графов, наименее трудоемки.

Рассмотрим задачу о кратчайшем пути. Пусть дан графG(X), ду­гам которого приписаны веса (расстояния, стоимости и т.п.), задаваемые матрицей С = ||c_ij||.

Задача о кратчайшем пути состоит в нахож­дении кратчайшего пути от заданной начальной вершины sXдо заданной конечной вершиныt Xпри условии, что такой путь су­ществует. В общем случае возможно С_ij> 0, С_ij < 0, С_ij= 0. Единст­венное ограничение состоит в том, чтобы в графеG(X)не было цикловс отрицательным суммарным весом.

Приведем очень простой и эффективный алгоритм Дейкстрырешения этой задачи для случая С_ij0i,j. Алгоритм основан на приписывании вершинам временных пометок, причем пометка вер­шины дает верхнюю границу длины пути отsк этой вершине. Вели­чины этих пометок постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это означает, что по­метка уже не является верхней границей, а дает точную длину крат­чайшего пути отsк рассматриваемой вершине. Пустьl(x_i) – пометка вершиныx_i. Опишем основные этапы алгоритма.

Алгоритм Дейкстры

Шаг 1. Присвоение начальных значений. Для исход­ной вершиныsположимl(s) = 0 и эта пометка будет по­сто­янной. Для всех других вершин имеем: 1(х_i) =x_is. Эти пометки временные. Положимp=sи составим мно­жество образов этой вершины:G(p).

Шаг 2. Обновление пометок. Для всехx_iG(p), помет­ки которых являются времен­ными, изменить пометки в соответствии с выражением:

1(х_i) = min [1(х_i), 1(р) + c(p, x_i)] (8)

Шаг 3. Превращение пометок в постоянные. Среди всех вершин с временными пометками найти та­куюx_i^*, для которойl(x_i^*) =min[l(x_i)]. Считать пометку вершиныx_i^*постоянной и положить р =x_i^*.

Шаг 4. Переход к шагу 2, если р  t. Останов при р = t. В случае, если требуется найти лишь путь от s к одной вершине t, следует окончание счета. Длина этого крат­чайшего пути будет 1(р).

При необходимости нахождения путей от sко всем остальным вершинам графа переходим к шагу 2. Продолжаем вычисления, пока все вершины не получат по­стоянные пометки. Эти отметки и дают длины кратчайших путей отsк этим вершинам.

Проиллюстрируем работу алгоритма на примере графа, изо­браженного на рис. 3.34. Матрица весов – в табл. 3.4. Граф является смешанным, т. е. ребра у него ориентирова-нные и неори­ентированные. Требуется найти все кратчайшие пути от x₁ко всем остальным вершинам. Постоянные пометки будем обозначать знаком⁺.

Шаг 1.l(x₁) = 0⁺, 1(x_i) =x_ix₁, р =x₁.

Первая итерация

Шаг 2.G(p) =G(x₁) = {х₂, х₇, х₈, х₉}. Все эти вершины имеют временные пометки.

Рис.3.34. Пример графа к алгоритму Дейкстры

В соответствии с формулой (8) уточняем пометки:

l(х₂) = min(, 0⁺ + 10) = 10; l(х₇) = 3; l(х₈) = 6; l(x₉) = 12.

Шаг 3.min(10, 3, 6, 12,) = 3

х₂ х₇ х₈ х₉ х₃, х₄, х₅, х₆

Вершина х₇ получает постоянную пометку: 1(х₇) = З⁺ .

Далее р = x₇.

Шаг 4. Так как не все вершины имеют постоянные пометки, то переходим к шагу 2. На рис. 3.35 приведены значения пометок вершин графа. Здесь выделены вершины с постоянными пометками.

Рис. 3.35. Пометки в начале второй итерации

Вторая итерация

Шаг 2.G(p) =G(x₇) = {х₂, х₄, х_б, х₉}.Пометки всех этих вершин временные. Из (8) получим:l(х₂) = 5,l(х₄) = 7,l(х₆)=17,l(х₉) = 12.

Шаг 3.min(5, 7, 17, 6, 12,) = 5.

х₂ х₄ х₆ х₈ х₉ х₃, х₅

Вершина х₂ получает постоянную пометку 1(х₂) = 5⁺.

Далее р = x₂.

Шаг 4. Значения пометок приведены на рис. 3.36. Переходим к шагу 2.

Рис. 3.36. Пометки в начале третьей итерации

Третья итерация

Шаг 2.G(p) =G(x₂) = {х₁, х₃, х₇, х₉}. Только вершины х₃и х₉ имеют временные пометки. Из (8) получим:l(х₃) =min(,5⁺+18) = 23, аналогично 1(х₉) =12.

Шаг 3.min(23, 7, 17, 6, 12,) = 6,

х₃ х₄ х₆ х₈ х₉ х₅

Вершина х₈ получает постоянную пометку 1(х₈) = 6⁺, р=x₈.

Шаг 4. Перейти к шагу 2 (рис. 3.37).

Рис. 3.37. Пометки в начале четвертой итерации

Продолжая итерационный процесс, получим в итоге постоян­ные пометки для всех вершин графа (рис.3.38) и кратчайшие пути от вершины х₁ко всем остальным вершинам. Эти пути выделены жирными линиями.

Для нахождения кратчайшего пути между вершиной х₂и на­чальной вершинойх₁последовательно используем соотношениеl(х_i) + С(х_i, х_i) =l(х_i). Полагаяi= 2 находим вершину х₂', непосред­ственно предшествующей х₂в кратчайшем пути от х₁к х₂:

1(х₂') + С(х₂', х₂) =l(х₂) = 5. Этому соотношению удов­ле­­творяет вершина х₇. Следовательно, х₂' = х₇. Полагаяi= 7 и применяя соот­ношение еще раз, получим х₇' = х₁Поэтому кратчайший путь со­стоит из вершин х₁, х₇, х₂. Аналогичным образом находим все крат­чайшие пути от х₁к остальным вершинам.

Рис. 3.38. Пометки и кратчайшие пути в графе

3.9. Обход графа

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