Алгоритмы теории графов: алгоритм Форда–Беллмана

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине “Математика”

на тему “Алгоритмы теории графов: Алгоритм Форда - Беллмана”

Содержание

Введение

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

1.1 Постановка задачи

1.2 Основные понятия теории графов

1.3 Выбор алгоритма

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

2.1 Поиск минимального пути

2.2 Построение матрицы смежности

2.3 Построение матрицы инцидентности

Заключение

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

Приложение

Введение

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

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

1.1 Постановка задачи

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

Рисунок 1

Составлена (7 ? 7) - матрица C(D) длин дуг нагруженного орграфа D. Эта матрица представлена на рисунке 2.

	х1	х2	х3	х4	х5	х6	х7
х1	?	?	9	?	?	2	12
х2	1	?	?	?	1	2	4
х3	2	1	?	?	1	?	2
х4	?	1	1	?	?	1	?
х5	1	2	?	2	?	?	?
х6	?	?	?	?	1	?	8
х7	?	2	1	?	1	2	?

2) Составить матрицу смежности A = (aij) для данного графа.

3) Составить матрицу инцидентности B = (bij) для данного графа.

1.2 Основные понятия теории графов

Пусть х - не пустое множество и Х - некоторый набор пар элементов из V вида (х, щ), х, щ Ђ V. Элементы множества V - вершины, множества X - ребра графа.

X = {( х1, х2), (х2, х3), (х1, х4), (х4, х4)}

Ребро вида (х, х) называется петлей, одинаковые пары во множестве X называются кратными ребрами.

Количество одинаковых пар (х, щ) называется кратностью ребра х, щ.

Множество V и набор Х определяют псевдограф G(V, X), т. е. граф с кратными ребрами и петлями.

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

Если во множестве X нет кратных ребер, то G(V, X) называется графом.

Если во множестве Х пары являются упорядоченными, то граф называется ориентированным графом или орграфом.

Ребра орграфа называются дугами.

Если граф не ориентированный и х = (х, щ) - ребро, то вершины х и щ называются концами ребра х.

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

Вершина х и ребро х называются инцидентными.

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

Степенью вершины х называется число д(х) ребер графа инцидентных данной вершине.

Вершина, имеющая степень 0 называется изолированной, 1 - висячей.

Последовательность хi1xi1, хi2xi2, …, хikxik, хik+1, k ? 1, хij € V, xij € X, в которой чередуются вершины и ребра (дуги) и ребро xij (хij, хij+1) называется маршрутом, соединяющим вершины хi1 и хik+1.

хi1 называется начальной вершиной. хik+1 называется конечной вершиной. Остальные - внутренние.

Одна и та же вершина может быть одновременно и начальной, и конечной, и внутренней.

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

Для орграфа маршрут называется путь.

Число ребер или дуг в маршруте (пути) называется его длинной.

Маршрут называется замкнутый, если начальная и конечная вершины совпадают.

Незамкнутый маршрут, в котором все ребра попарно различны называется цепью.

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

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

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

Матричные способы задания графов.

Пусть ?(х, x) - граф

V = {х1, х2, …, хn}

X = {x1, x2, …, xn}

Матрицей смежости называется квадратная матрица А n - ого порядка, элементы которой определяются формулой:

A = (aij) aij = 1, (хi, хj) Ђ X

0, (хi, хj) не € X

Если дан псевдограф, то aij = 0, (хi, хj) € X

k, k - кратность ребра

Матрицей инцидентности называется матрица В размера M x N, элементы которой определяются по формуле:

B = (bij) bij = 0, хi не инцидентна xj

1, хi есть конец дуги xj

-1, хi есть начало дуги xj

Пусть D - ориентированный мультиграф с непустым множеством дуг, тогда:

1) сумма строк матрицы B(D) есть нулевая строка

2) любая строка B(D) есть линейная комбинация остальных

3) ранг матрицы B(D) не превосходит числа вершин - 1 (минус 1)

4) для любого контура в D сумма столбцов матрицы B(D) соответствующих дугов входящих в этот контур равна нулевому столбцу.

A(G) - матрица смежности

Ak(G) = A * A * … * A

Элемент qkij матрицы Ak(G) ориентированного псвдографа равен числу всех путей длины k из вершины хi в хj.

Теорема: для того, чтобы n - вершинный орграф D с матрицей смежности A(D) имел хотя бы один контур необходимо и достаточно, чтобы матрица k = A2 + + A3 + … + An имела не нулевые диагональные элементы.

Объединением графов G1(V1, X1) и G2(V2, X2) называется граф

G = G1 U G2 (V1UV2, X1UX2)

Пересечением графов G1 и G2, где V1 - пересечение V2 ? Ш называется граф (V1?V2 = Ш) G1?G2 (V1?V2, X1?X2)

Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G.

Подграф называется собственным, если он отличен от самого графа.

Вершина щ орграфа D (графа G) называется достижимой из вершины V, если существует путь (маршрут) из V в щ или V = щ.

Граф называется связным, если для любых двух его вершин существует маршрут, соединяющий их.

Компонентой связности графа G называется его связный подграф не являющийся собственным подграфом никакого другого связанного подграфа.

Пусть орграф D имеет множество вершин V = {V1, V2, …, Vn}.

Матрицей достижимости орграфа D называется квадратная матрица T(D) порядка n, у которой tij = 1, хj достижимо из хi

0, хj не достижимо из хi

Матрицей связности S(D) орграфа D называется квадратная матрица порядка n, у которой Sij = 1, хj достижимо из хi, хi достижимо из хj

0, в противном случае

Матрицей связности неориентированного графа G называется квадратная матрица S(G) порядка n у которой:

Sij = 1, если i = j или если существует маршрут, соединяющий Vi и Vj

0, в противном случае

1.3 Выбор алгоритма

Для решения поставленной задачи будем использовать алгоритм Форда - Бэллмана.

Назовем орграф D = (V, X) нагруженным, если на множестве дуг X определена некоторая функция l: X > R, которую часто называют весовой функцией. Тем самым в нагруженном орграфе D в каждой дуге x € X поставлено в соответствие некоторое действительное число l(x). Значение l(x) будем называть длинной дуги x. Для этого пути р нагруженного орграфа D обозначим через l(р) сумму длин входящих в р дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину l(р) будем называть длинной пути р в нагруженном орграфе D. Ранее так называлось количество дуг в пути р. В связи с этим заметим, что если длины дуг выбраны равными l, то l(р) выражает введенную ранее длину пути р в ненагруженном орграфе. Следовательно, любой ненагруженный орграф можно считать нагруженным с длинами дуг, равными l. Аналогично определяется и нагруженный граф, а также длина маршрута в нем.

Пусть в нагруженном орграфе D из вершины х в вершину щ, где х ? щ, называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из х в щ. Аналогично определяется и минимальный маршрут в нагруженном графе G.

Если в нагруженном орграфе D имеются замкнутые пути отрицательной длины, то для заданных вершин х1, щ орграфа D, где х ? щ, минимального пути из х в щ может и не быть. Действительно, если в D имеется замкнутый путь у отрицательной длины и существует путь из х в щ, проходящий хотя бы через одну вершину, содержащуюся в у, то очевидно, что в D найдется путь р из х в щ вида р = р1П у П р2, где р1, р2 - пути в D (возможно также, что либо р1, либо р2 является пустой последовательностью; при этом предполагаем, что Ш П у = у П Ш = у). Но тогда р1 П у П у П р2, р1 П у П у П у П р2 … также пути в D из х в щ, и длина каждого следующего пути в этой последовательности отличается от длины предыдущего на l(у) < 0, а значит, длины путей из х в щ могут принимать сколь угодно малые отрицательные значения. Аналогичная ситуация имеет место в случае, когда в нагруженном графе G вершины х, щ находятся в одной компоненте связности, содержащей хотя бы одно ребро отрицательной длины. В таких случаях имеют смысл лишь задачи поиска минимальных путей (маршрутов) среди путей (маршрутов), число дуг (ребер) в которых ограничено сверху.

Приведем некоторые свойства минимальных путей (маршрутов) в нагруженном орграфе D = (V, X) (графе G = (V, X)):

1) если существует x € X l(x) > 0, то любой минимальный путь (маршрут) является простой цепью;

2) если х1 х2 … хk - минимальный путь (маршрут), то для любых номеров i, j таких, что 1 ? i < j ? k, путь (маршрут) хi хi+1 также является минимальным;

3) если х … и щ - минимальный путь (маршрут) среди путей из х в щ (среди маршрутов, соединяющих х, щ), содержащих не более k+1 дуг (ребер), то х … u - минимальный путь (маршрут) среди путей из х в u (среди маршрутов, соединяющих х, u), содержащих не более k дуг (ребер).

Рассмотрим теперь задачу поиска минимальных путей (маршрутов) в нагруженном орграфе (графе). При этом для определенности рассуждения будем проводить для орграфа (для графа они аналогичны).

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

Пусть D = (V, X) - нагруженный орграф, V = { х1, …, хn}, n > 2. Введем величины лi(k) , где i = 1, …, n, k = 1, 2, … . Для каждых фиксированных i и k величина лi(k) равна длине минимального пути среди путей из х1 в хi, содержащих не более k дуг; если же таких путей нет, то лi(k) = ?. Кроме того, если произвольную вершину х Ђ V считать путем из х в х нулевой длины, то величины лi(k) можно ввести также и для k = 0, при этом

л1(0) = 0, лi(0) = ?, i = 2, …, n. (1)

Введем также в рассмотрение квадратную матрицу C(D) = [сij] порядка n с элементами

cij = l(хi, хj), если (хi, хj) € X;

?, если (хi, хj) € Х, которую будем называть матрицей длин дуг нагруженного орграфа D.

Следующее утверждение дает простые формулы дл вычисления величин лi(k).

Утверждение 1. При i - 2, …, n, k ? 0 выполняется равенство

лi(k+1) = min {лj(k)+cij}

1 ? j ? n

а при i - 1, k ? 0 справедливо равенство

лi(k+1) = min{0; min {лj(k)=cj1}}

1 ? j ? n

Используя утверждение 1, нетрудно описать алгоритм нахождения таблицы значении величин лi(k) (будем записывать в виде матрицы, где i - номер строки, k+1 - номер столбца). Действительно, используя рекуррентные соотношения (2), (3) и исходя из (1), последовательно определяем набор величин л1(k), …, лn(k) ((k+1) столбец матрицы), начиная с k = 0, а затем шаг за шагом увеличивая значение k до любой необходимой величины.

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

Утверждение 2. Из всякого замкнутого пути отрицательной длины можно выделить простой контур отрицательной длины.

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

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

Замечание 2. При определении нагруженного графа мы предполагали, что величины l(x), x € X, конечны. Между тем величины лi(k) (i = 1, 2, …, n, k = 0, 1, …, n - 1) можно аналогичным образом определить и для случая, когда для некоторых x € X выполняется l(x) = ?. При этом сохраняет силу утверждение 1, а следовательно, и алгоритм построения таблицы величин лi(k). Отметим, однако, что теперь могут существовать вершины, достижимые из х1 с длинами минимальных путей из х1 в эти вершины, равными ?, т. е. мы уже не можем судить по лi(n-1) о достижимости вершин хi из х1.

Замечание 3. Если при некотором k0, где 0 ? k0 ? n - 2, выполняются равенства лi(k0) = лi(k0 + 1), i = 1, 2, …, n, и, в частности , лi(n - 1) = лi(k0), i = 1, 2, …, n, т. е. в данном случае значения лi(k) при k > k0 не несут никакой дополнительной информации, и тогда имеет смысл оборвать процесс последовательного определения наборов величин л1(k), …, лn(k) на значении k = k0.

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

Утверждение 5. Пусть в орграфе D = (V, X), где V = { х1, …, хn}, любая вершина хi, i € {2, …, n}, достижима из х1. Тогда, для того чтобы в D отсутствовали простые контуры отрицательной длины, необходимо и достаточно, чтобы выполнялось условие лi(n -1) = лi(n), i = 1, …, n.

Алгоритм (алгоритм Форда - Беллмана) нахождения минимального пути в нагруженном орграфе D из х1 в хi1, (i ? 1):

Шаг 1. Пусть мы уже составили таблицу величин лi(k), i = 1, 2, … , n, k = 0, 1, 2, …, n - 1. Если лi(n-1) = ?, то вершина хi1 не достижима из х1 (предполагаем, что все величины l(x), x € X конечны). В этом случае работа алгоритма заканчивается.

Шаг 2. Пусть лi1(n-1) < ?, тогда число лi1(n-1) выражает длину любого минимального пути из х1 в хi1 в нагруженном орграфе D. Определим минимальное число k ? 1, при котором выполняется равенство лi1(k1) = лi1(n-1). По определению чисел лi(k) получаем, что k1 - минимальное число дуг в пути среди всех минимальных путей х1 в хi1 в нагруженном орграфе D.

Шаг 3. Последовательно определяем номера i2, …, ik1+1 такие, что

лi2(k1-1) + сi2,i1 = лi1(k1)

лi3(k1-2) + сi3,i2 = лi1(k1 - 1)

лi(0) + ci j = лi(1)

k1+1 k1+1 k1 k1

(эти номера найдутся в силу (2)).

Из (4) с учетом того, что лi1(k1)=лi1(n - 1) < ?, имеем ci2, i1<?,…,ci, i < ?, лi(0) < ?,

k1+1 k1 k1+1

откуда, используя (1), получаем

(хi2, хi1), …, (хi, хi) € X, l(хi2, хi1) = ci2, i1, …, l(хi2, хi1) = ci,I;

1+1 k1 k1+1 k1 k1+1 k1

лi(0) = 0, i = 1, хi = х1 (5)

k1+1 k1+1 k1+1

Складывая равенства (4) и учитывая (5), имеем

l(х1k1 хi … хi2 хi1) = лi1(k1),

т. е. х1 хi … хi2 хi1 - исходный минимальный путь из х1 в хi1 в нагруженном орграфе D. Заметим, что в этом пути ровно ki дуг. Следовательно мы определили путь с минимальным числом дуг среди всех минимальных путей из х1 в хi1 в нагруженном орграфе D.

Замечание 4. Номера i2, i3, …, ik1, удовлетворяющие (6), вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных путей из х1 в хi1 c минимальным числом дуг среди минимальных путей из х1 в хi1 в нагруженном орграфе D.

Замечание 5. Алгоритм можно модифицировать, с тем х1 в хi1, содержащих не более k0 дуг, где k0 - заданное число, k0 > 1. Xтобы определить минимальный путь из х1 в заданную вершину хi1 среди путей из х1 в хi1. Для этого в алгоритме вместо лi(n - 1) следует воспользоваться лi1(k0). Отметим, что при использовании указанной модификации алгоритма предположение об отсутствии простых контуров отрицательной длины излишне. При том, если в орграфе D имеются простые контуры отрицательной длины, может выполняться неравенство л1(k0) < 0.

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

Замечание 7. Нетрудно доказать, что утверждение 1, а следовательно, и алгоритм вместе с его модификацией останутся справедливыми и для нагруженного ориентированного псевдографа. При этом в случае кратных дуг следует учитывать лишь дуги минимальной длины, а при наличии петель - лишь, петли отрицательной длины. Это замечание переносится и на неориентированные псевдографы.

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

2.1 Поиск минимального пути

Составим таблицу

	лi(0)	лi(1)	лi(2)	лi(3)	лi(4)	лi(5)	лi(6)
i1	-	-	-	-	-	-	-
i2	-	-	-	-	-	-	-
i3	-	-	-	-	-	-	-
i4	-	-	-	-	-	-	-
i5	-	-	-	-	-	-	-
i6	-	-	-	-	-	-	-
i7	-	-	-	-	-	-	-

и будем последовательно определять ее элементы, используя рекуррентное соотношение (2) и исходя из (1).

л1(0) = 0, лi(0) = ?, i = 2, …, n.

Используя (2) определим элементы лi(k), i = 2, 3, 4, 5, 6, 7; k = 1, 2, 3, 4, 5, 6. матричный граф смежность инцидентность

л2(1) = min{лj(0) + cj2}, 1 ? j ? 7

при j = 1 л1(0) + с12 = 0 + ? = ?

при j = 2 л2(0) + с22 = ? + ? = ?

при j = 3 л3(0) + с32 = ? + 1 = ?

при j = 4 л4(0) + с42 = ? + 1 = ?

при j = 5 л5(0) + с52 = ? + 2 = ?

при j = 6 л6(0) + с62 = ? + ? = ?

при j = 7 л7(0) + с72 = ? + 2 = ?

Следовательно л2(1) = ?

л3(1) = min{лj(0) + cj3}, 1 ? j ? 7

при j = 1 л1(0) + с13 = 0 + 9 = 9

при j = 2 л2(0) + с23 = ? + ? = ?

при j = 3 л3(0) + с33 = ? + ? = ?

при j = 4 л4(0) + с43 = ? + 1 = ?

при j = 5 л5(0) + с53 = ? + ? = ?

при j = 6 л6(0) + с63 = ? + ? = ?

при j = 7 л7(0) + с73 = ? + 1 = ?

Следовательно л2(1) = 9

л4(1) = min{лj(0) + cj4}, 1 ? j ? 7

при j = 1 л1(0) + с14 = 0 + ? = ?

при j = 2 л2(0) + с24 = ? + ? = ?

при j = 3 л3(0) + с34 = ? + ? = ?

при j = 4 л4(0) + с44 = ? + ? = ?

при j = 5 л5(0) + с54 = ? + 2 = ?

при j = 6 л6(0) + с64 = ? + ? = ?

при j = 7 л7(0) + с74 = ? + ? = ?

Следовательно л4(1) = ?

л5(1) = min{лj(0) + cj5}, 1 ? j ? 7

при j = 1 л1(0) + с15 = 0 + ? = ?

при j = 2 л2(0) + с25 = ? + 1 = ?

при j = 3 л3(0) + с35 = ? + 1 = ?

при j = 4 л4(0) + с45 = ? + ? = ?

при j = 5 л5(0) + с55 = ? + ? = ?

при j = 6 л6(0) + с65 = ? + ? = ?

при j = 7 л7(0) + с75 = ? + 1 = ?

Следовательно л5(1) = ?

л6(1) = min{лj(0) + cj6}, 1 ? j ? 7

при j = 1 л1(0) + с16 = 0 + 2 = 2

при j = 2 л2(0) + с26 = ? + 2 = ?

при j = 3 л3(0) + с36 = ? + ? = ?

при j = 4 л4(0) + с46 = ? + 1 = ?

при j = 5 л5(0) + с56 = ? + ? = ?

при j = 6 л6(0) + с66 = ? + ? = ?

при j = 7 л7(0) + с76 = ? + 2 = ?

Следовательно л6(1) = 2

л7(1) = min{лj(0) + cj7}, 1 ? j ? 7

при j = 1 л1(0) + с17 = 0 + 12 = 12

при j = 2 л2(0) + с27 = ? + 4 = ?

при j = 3 л3(0) + с37 = ? + 2 = ?

при j = 4 л4(0) + с47 = ? + ? = ?

при j = 5 л5(0) + с57 = ? + ? = ?

при j = 6 л6(0) + с67 = ? + 8 = ?

при j = 7 л7(0) + с77 = ? + ? = ?

Следовательно л7(1) = 12

л2(2) = min{лj(1) + cj2}, 1 ? j ? 7

при j = 1 л1(1) + с12 = 0 + ? = ?

при j = 2 л2(1) + с22 = ? + ? = ?

при j = 3 л3(1) + с32 = 9 + 1 = 10

при j = 4 л4(1) + с42 = ? + 1 = ?

при j = 5 л5(1) + с52 = ? + 2 = ?

при j = 6 л6(1) + с62 = 2 + ? = ?

при j = 7 л7(1) + с72 = 12 + 2 = 14

Следовательно л2(2) = 10

л2(2) = min{лj(1) + cj2}, 1 ? j ? 7

при j = 1 л1(1) + с12 = 0 + ? = ?

при j = 2 л2(1) + с22 = ? + ? = ?

при j = 3 л3(1) + с32 = 9 + 1 = 10

при j = 4 л4(1) + с42 = ? + 1 = ?

при j = 5 л5(1) + с52 = ? + 2 = ?

при j = 6 л6(1) + с62 = 2 + ? = ?

при j = 7 л7(1) + с72 = 12 + 2 = 14

Следовательно л2(2) = 10

л3(2) = min{лj(1) + cj3}, 1 ? j ? 7

при j = 1 л1(1) + с13 = 0 + 9 = 9

при j = 2 л2(1) + с23 = ? + ? = ?

при j = 3 л3(1) + с33 = 9 + ? = ?

при j = 4 л4(1) + с43 = ? + 1 = ?

при j = 5 л5(1) + с53 = ? + ? = ?

при j = 6 л6(1) + с63 = 2 + ? = ?

при j = 7 л7(1) + с73 = 12 + 1 = 13

Следовательно л3(2) = 9

л4(2) = min{лj(1) + cj4}, 1 ? j ? 7

при j = 1 л1(1) + с14 = 0 + ? = ?

при j = 2 л2(1) + с24 = ? + ? = ?

при j = 3 л3(1) + с34 = 9 + ? = ?

при j = 4 л4(1) + с44 = ? + ? = ?

при j = 5 л5(1) + с54 = ? + 2 = ?

при j = 6 л6(1) + с64 = 2 + ? = ?

при j = 7 л7(1) + с74 = 12 + ? = ?

Следовательно л4(2) = ?

л5(2) = min{лj(1) + cj5}, 1 ? j ? 7

при j = 1 л1(1) + с15 = 0 + ? = ?

при j = 2 л2(1) + с25 = ? + 1 = ?

при j = 3 л3(1) + с35 = 9 + 1 = 10

при j = 4 л4(1) + с45 = ? + ? = ?

при j = 5 л5(1) + с55 = ? + ? = ?

при j = 6 л6(1) + с65 = 2 + 1 = 3

при j = 7 л7(1) + с75 = 12 + 1 = 13

Следовательно л5(2) = 3

л6(2) = min{лj(1) + cj6}, 1 ? j ? 7

при j = 1 л1(1) + с16 = 0 + 2 = 2

при j = 2 л2(1) + с26 = ? + 2 = ?

при j = 3 л3(1) + с36 = 9 + ? = ?

при j = 4 л4(1) + с46 = ? + 1 = ?

при j = 5 л5(1) + с56 = ? + ? = ?

при j = 6 л6(1) + с66 = 2 + ? = ?

при j = 7 л7(1) + с76 = 12 + 2 = 14

Следовательно л6(2) = 2

л7(2) = min{лj(1) + cj7}, 1 ? j ? 7

при j = 1 л1(1) + с17 = 0 + 12 = 12

при j = 2 л2(1) + с27 = ? + 4 = ?

при j = 3 л3(1) + с37 = 9 + 2 = 11

при j = 4 л4(1) + с47 = ? + ? = ?

при j = 5 л5(1) + с57 = ? + ? = ?

при j = 6 л6(1) + с67 = 2 + 8 = 10

при j = 7 л7(1) + с77 = 12 + ? = ?

Следовательно л7(2) = 10

л2(3) = min{лj(2) + cj2}, 1 ? j ? 7

при j = 1 л1(2) + с12 = 0 + ? = ?

при j = 2 л2(2) + с22 = 10 + ? = ?

при j = 3 л3(2) + с32 = 9 + 1 = 10

при j = 4 л4(2) + с42 = ? + 1 = ?

при j = 5 л5(2) + с52 = 3 + 2 = 5

при j = 6 л6(2) + с62 = 2 + ? = ?

при j = 7 л7(2) + с72 = 10 + 2 = 12

Следовательно л2(3) = 5

л3(3) = min{лj(2) + cj3}, 1 ? j ? 7

при j = 1 л1(2) + с13 = 0 + 9 = 9

при j = 2 л2(2) + с23 = 10 + ? = ?

при j = 3 л3(2) + с33 = 9 + ? = ?

при j = 4 л4(2) + с43 = ? + 1 = ?

при j = 5 л5(2) + с53 = 3 + ? = ?

при j = 6 л6(2) + с63 = 2 + ? = ?

при j = 7 л7(2) + с73 = 10 + 1 = 11

Следовательно л3(3) = 9

л4(3) = min{лj(2) + cj4}, 1 ? j ? 7

при j = 1 л1(2) + с14 = 0 + ? = ?

при j = 2 л2(2) + с24 = 10 + ? = ?

при j = 3 л3(2) + с34 = 9 + ? = ?

при j = 4 л4(2) + с44 = ? + ? = ?

при j = 5 л5(2) + с54 = 3 + 2 = 5

при j = 6 л6(2) + с64 = 2 + ? = ?

при j = 7 л7(2) + с74 = 10 + ? = ?

Следовательно л4(3) = 5

л5(3) = min{лj(2) + cj5}, 1 ? j ? 7

при j = 1 л1(2) + с15 = 0 + ? = ?

при j = 2 л2(2) + с25 = 10 + 1 = 11

при j = 3 л3(2) + с35 = 9 + 1 = 10

при j = 4 л4(2) + с45 = ? + ? = ?

при j = 5 л5(2) + с55 = 3 + ? = ?

при j = 6 л6(2) + с65 = 2 + 1 = 3

при j = 7 л7(2) + с75 = 10 + 1 = 11

Следовательно л5(3) = 3

л6(3) = min{лj(2) + cj6}, 1 ? j ? 7

при j = 1 л1(2) + с16 = 0 + 2 = 2

при j = 2 л2(2) + с26 = 10 + 2 = 12

при j = 3 л3(2) + с36 = 9 + ? = ?

при j = 4 л4(2) + с46 = ? + 1 = ?

при j = 5 л5(2) + с56 = 3 + ? = ?

при j = 6 л6(2) + с66 = 2 + ? = ?

при j = 7 л7(2) + с76 = 10 + 2 = 12

Следовательно л6(3) = 2

л7(3) = min{лj(2) + cj7}, 1 ? j ? 7

при j = 1 л1(2) + с17 = 0 + 12 = 12

при j = 2 л2(2) + с27 = 10 + 4 = 14

при j = 3 л3(2) + с37 = 9 + 2 = 11

при j = 4 л4(2) + с47 = ? + ? = ?

при j = 5 л5(2) + с57 = 3 + ? = ?

при j = 6 л6(2) + с67 = 2 + 8 = 10

при j = 7 л7(2) + с77 = 10 + ? = ?

Следовательно л7(3) = 10

л2(4) = min{лj(3) + cj2}, 1 ? j ? 7

при j = 1 л1(3) + с12 = 0 + ? = ?

при j = 2 л2(3) + с22 = 5 + ? = ?

при j = 3 л3(3) + с32 = 9 + 1 = 10

при j = 4 л4(3) + с42 = 5 + 1 = 6

при j = 5 л5(3) + с52 = 3 + 2 = 5

при j = 6 л6(3) + с62 = 2 + ? = ?

при j = 7 л7(3) + с72 = 10 + 2 = 12

Следовательно л2(4) = 5

л3(4) = min{лj(3) + cj3}, 1 ? j ? 7

при j = 1 л1(3) + с13 = 0 + 9 = 9

при j = 2 л2(3) + с23 = 5 + ? = ?

при j = 3 л3(3) + с33 = 9 + ? = ?

при j = 4 л4(3) + с43 = 5 + 1 = 6

при j = 5 л5(3) + с53 = 3 + ? = ?

при j = 6 л6(3) + с63 = 2 + ? = ?

при j = 7 л7(3) + с73 = 10 + 1 = 11

Следовательно л3(4) = 6

л4(4) = min{лj(3) + cj4}, 1 ? j ? 7

при j = 1 л1(3) + с14 = 0 + ? = ?

при j = 2 л2(3) + с24 = 5 + ? = ?

при j = 3 л3(3) + с34 = 9 + ? = ?

при j = 4 л4(3) + с44 = 5 + ? = ?

при j = 5 л5(3) + с54 = 3 + 2 = 5

при j = 6 л6(3) + с64 = 2 + ? = ?

при j = 7 л7(3) + с74 = 10 + ? = ?

Следовательно л4(4) = 5

л5(4) = min{лj(3) + cj5}, 1 ? j ? 7

при j = 1 л1(3) + с15 = 0 + ? = ?

при j = 2 л2(3) + с25 = 5 + 1 = 6

при j = 3 л3(3) + с35 = 9 + 1 = 10

при j = 4 л4(3) + с45 = 5 + ? = ?

при j = 5 л5(3) + с55 = 3 + ? = ?

при j = 6 л6(3) + с65 = 2 + 1 = 3

при j = 7 л7(3) + с75 = 10 + 1 = 11

Следовательно л5(4) = 3

л6(4) = min{лj(3) + cj6}, 1 ? j ? 7

при j = 1 л1(3) + с16 = 0 + 2 = 2

при j = 2 л2(3) + с26 = 5 + 2 = 7

при j = 3 л3(3) + с36 = 9 + ? = ?

при j = 4 л4(3) + с46 = 5 + 1 = 6

при j = 5 л5(3) + с56 = 3 + ? = ?

при j = 6 л6(3) + с66 = 2 + ? = ?

при j = 7 л7(3) + с76 = 10 + 2 = 12

Следовательно л6(4) = 2

л7(4) = min{лj(3) + cj7}, 1 ? j ? 7

при j = 1 л1(3) + с17 = 0 + 12 = 12

при j = 2 л2(3) + с27 = 5 + 4 = 9

при j = 3 л3(3) + с37 = 9 + 2 = 11

при j = 4 л4(3) + с47 = 5 + ? = ?

при j = 5 л5(3) + с57 = 3 + ? = ?

при j = 6 л6(3) + с67 = 2 + 8 = 10

при j = 7 л7(3) + с77 = 10 + ? = ?

Следовательно л7(4) = 9

л2(5) = min{лj(4) + cj2}, 1 ? j ? 7

при j = 1 л1(4) + с12 = 0 + ? = ?

при j = 2 л2(4) + с22 = 5 + ? = ?

при j = 3 л3(4) + с32 = 6 + 1 = 7

при j = 4 л4(4) + с42 = 5 + 1 = 6

при j = 5 л5(4) + с52 = 3 + 2 = 5

при j = 6 л6(4) + с62 = 2 + ? = ?

при j = 7 л7(4) + с72 = 9 + 2 = 11

Следовательно л2(5) = 5

л3(5) = min{лj(4) + cj3}, 1 ? j ? 7

при j = 1 л1(4) + с13 = 0 + 9 = 9

при j = 2 л2(4) + с23 = 5 + ? = ?

при j = 3 л3(4) + с33 = 6 + ? = ?

при j = 4 л4(4) + с43 = 5 + 1 = 6

при j = 5 л5(4) + с53 = 3 + ? = ?

при j = 6 л6(4) + с63 = 2 + ? = ?

при j = 7 л7(4) + с73 = 9 + 1 = 10

Следовательно л3(5) = 6

л4(5) = min{лj(4) + cj4}, 1 ? j ? 7

при j = 1 л1(4) + с14 = 0 + ? = ?

при j = 2 л2(4) + с24 = 5 + ? = ?

при j = 3 л3(4) + с34 = 6 + ? = ?

при j = 4 л4(4) + с44 = 5 + ? = ?

при j = 5 л5(4) + с54 = 3 + 2 = 5

при j = 6 л6(4) + с64 = 2 + ? = ?

при j = 7 л7(4) + с74 = 9 + ? = ?

Следовательно л4(5) = 5

л5(5) = min{лj(4) + cj5}, 1 ? j ? 7

при j = 1 л1(4) + с15 = 0 + ? = ?

при j = 2 л2(4) + с25 = 5 + 1 = 6

при j = 3 л3(4) + с35 = 6 + 1 = 7

при j = 4 л4(4) + с45 = 5 + ? = ?

при j = 5 л5(4) + с55 = 3 + ? = ?

при j = 6 л6(4) + с65 = 2 + 1 = 3

при j = 7 л7(4) + с75 = 9 + 1 = 10

Следовательно л5(5) = 3

л6(5) = min{лj(4) + cj6}, 1 ? j ? 7

при j = 1 л1(4) + с16 = 0 + 2 = 2

при j = 2 л2(4) + с26 = 5 + 2 = 7

при j = 3 л3(4) + с36 = 6 + ? = ?

при j = 4 л4(4) + с46 = 5 + 1 = 6

при j = 5 л5(4) + с56 = 3 + ? = ?

при j = 6 л6(4) + с66 = 2 + ? = ?

при j = 7 л7(4) + с76 = 9 + 2 = 11

Следовательно л6(5) = 2

л7(5) = min{лj(4) + cj7}, 1 ? j ? 7

при j = 1 л1(4) + с17 = 0 + 12 = 12

при j = 2 л2(4) + с27 = 5 + 4 = 9

при j = 3 л3(4) + с37 = 6 + 2 = 8

при j = 4 л4(4) + с47 = 5 + ? = ?

при j = 5 л5(4) + с57 = 3 + ? = ?

при j = 6 л6(4) + с67 = 2 + 8 = 10

при j = 7 л7(4) + с77 = 9 + ? = ?

Следовательно л7(5) = 8

л2(6) = min{лj(5) + cj2}, 1 ? j ? 7

при j = 1 л1(5) + с12 = 0 + ? = ?

при j = 2 л2(5) + с22 = 5 + ? = ?

при j = 3 л3(5) + с32 = 6 + 1 = 7

при j = 4 л4(5) + с42 = 5 + 1 = 6

при j = 5 л5(5) + с52 = 3 + 2 = 5

при j = 6 л6(5) + с62 = 2 + ? = ?

при j = 7 л7(5) + с72 = 9 + 2 = 11

Следовательно л2(6) = 5

л3(6) = min{лj(5) + cj3}, 1 ? j ? 7

при j = 1 л1(5) + с13 = 0 + 9 = 9

при j = 2 л2(5) + с23 = 5 + ? = ?

при j = 3 л3(5) + с33 = 6 + ? = ?

при j = 4 л4(5) + с43 = 5 + 1 = 6

при j = 5 л5(5) + с53 = 3 + ? = ?

при j = 6 л6(5) + с63 = 2 + ? = ?

при j = 7 л7(5) + с73 = 9 + 1 = 10

Следовательно л3(6) = 6

л4(6) = min{лj(5) + cj4}, 1 ? j ? 7

при j = 1 л1(5) + с14 = 0 + ? = ?

при j = 2 л2(5) + с24 = 5 + ? = ?

при j = 3 л3(5) + с34 = 6 + ? = ?

при j = 4 л4(5) + с44 = 5 + ? = ?

при j = 5 л5(5) + с54 = 3 + 2 = 5

при j = 6 л6(5) + с64 = 2 + ? = ?

при j = 7 л7(5) + с74 = 9 + ? = ?

Следовательно л4(6) = 5

л5(6) = min{лj(5) + cj5}, 1 ? j ? 7

при j = 1 л1(5) + с15 = 0 + ? = ?

при j = 2 л2(5) + с25 = 5 + 1 = 6

при j = 3 л3(5) + с35 = 6 + 1 = 7

при j = 4 л4(5) + с45 = 5 + ? = ?

при j = 5 л5(5) + с55 = 3 + ? = ?

при j = 6 л6(5) + с65 = 2 + 1 = 3

при j = 7 л7(5) + с75 = 9 + 1 = 10

Следовательно л2(6) = 3

л6(6) = min{лj(5) + cj6}, 1 ? j ? 7

при j = 1 л1(5) + с16 = 0 + 2 = 2

при j = 2 л2(5) + с26 = 5 + 2 = 7

при j = 3 л3(5) + с36 = 6 + ? = ?

при j = 4 л4(5) + с46 = 5 + 1 = 6

при j = 5 л5(5) + с56 = 3 + ? = ?

при j = 6 л6(5) + с66 = 2 + ? = ?

при j = 7 л7(5) + с76 = 9 + 2 = 11

Следовательно л6(6) = 2

л7(6) = min{лj(5) + cj7}, 1 ? j ? 7

при j = 1 л1(5) + с17 = 0 + 12 = 12

при j = 2 л2(5) + с27 = 5 + 4 = 9

при j = 3 л3(5) + с37 = 6 + 2 = 8

при j = 4 л4(5) + с47 = 5 + ? = ?

при j = 5 л5(5) + с57 = 3 + ? = ?

при j = 6 л6(5) + с67 = 2 + 8 = 10

при j = 7 л7(5) + с77 = 9 + ? = ?

Следовательно л7(6) = 8

Заполним таблицу получившимися значениями

	лi(0)	лi(1)	лi(2)	лi(3)	лi(4)	лi(5)	лi(6)
i1	0	0	0	0	0	0	0
i2	?	?	10	5	5	5	5
i3	?	9	9	9	6	6	6
i4	?	?	?	5	5	5	5
i5	?	?	3	3	3	3	3
i6	?	2	2	2	2	2	2
i7	?	12	10	10	9	8	8

Величина л7(6) = 8 выражает длину минимального пути из х1 в х7 в нагруженном орграфе D. Найдем минимальное число k ? 1, при котором выполняется равенство л7(k+1) = л7(6). Получаем, что k = 5. Таким образом, минимальное число дуг в пути среди всех минимальных путей из х1 в х7 в нагруженном орграфе D равняется 5. Определим теперь последовательность номеров i1, i2, i3, i4, i5, i6, где i1 = 7, удовлетворяющих (4), для этого используем формулу (2). Из таблицы получаем, что в качестве такой последовательности гадо взять номера 7, 3, 4, 5, 6, 1, так как

л3(4) +c37 = 6 + 2 = л7(5)

л4(3) +c43 = 5 + 1 = л3(4)

л5(2) +c54 = 3 + 2 = л4(3)

л6(1) +c65 = 2 + 1 = л5(2)

л1(0) +c16 = 0 + 2 = л6(1)

Тогда х1 х6 х5 х4 х3 х7 - искомый минимальный путь из х1 в х7 в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из х1 в х7.

2.2 Построение матрицы смежности

Рисунок 3

Построим матрицу смежности для данного орграфа.

2.3 Построение матрицы инцидентности

Произвольно обозначим ребра орграфа Х1, Х2, …, Х23, как показано на рисунке 4.

Рисунок 4

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



Заключение

Приведенный в данной работе алгоритм позволяет по таблице величин лi(k), i = 1, 2, …, n, k = 0, 1, …, n - 1, определить минимальный путь в нагруженном орграфе D из х1 в любую достижимую вершину, причем из всех возможных путей он выделяет путь с наименьшим числом дуг.

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

1. Нефедов В. Н. Курс дискретной математики / В. Н. Нефедов, В. А. Осипова. Изд - во МАИ, 2012. 262 с.

2. Емеличев В. А. Лекции по теории графов. / В. А. Емеличев, О. И. Мельников. М.: Наука, Гл. ред. физ. - мат. лит., 1990. 384 с.

3. Свами М. Графы, сети, алгоритмы / М. Свами, К. Тхуласираман. М.: Мир, 2014. 455 с.

Приложение

На рисунке 5 показан минимальный путь из V1 в V7 в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из V1 в V7.

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

...