Алгоритм Форда-Беллмана
Введение
граф алгоритм маршрут
При конструировании радиоаппаратуры и других электронных устройств возникает задача об оптимальном размещении компонентов на печатной плате, или отдельных элементов в корпусе устройства. Помощь в ее решении могут оказать различные алгоритмы теории графов, один из них будет изложен в этой работе.
1. Теоретическая часть
.1 Постановка задачи
1) Определить минимальный путь из υ1 в υ7 в нагруженном орграфе D, причем он должен иметь минимальное число дуг среди всех возможных минимальных путей. Орграф D: около каждой дуги указана ее длина.
Составлена (7 ˟ 7) - матрица C(D) длин дуг нагруженного орграфа D.
υ1υ2υ3υ4υ5υ6υ7υ1∞∞9∞∞212υ21∞∞∞124υ321∞∞1∞2υ4∞11∞∞1 ∞υ512∞2∞∞∞υ6∞∞∞∞1∞8υ7∞21∞12∞
2) Составить матрицу смежности A = (aij) для данного графа.
) Составить матрицу инцидентности 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 - ориентированный мультиграф с непустым множеством дуг, тогда:
) сумма строк матрицы B(D) есть нулевая строка
) любая строка B(D) есть линейная комбинация остальных
) ранг матрицы B(D) не превосходит числа вершин - 1 (минус 1)
) для любого контура в D сумма столбцов матрицы B(D) соответствующих дугов входящих в этот контур равна нулевому столбцу.
A(G) - матрица смежности
k(G) = A * A * … * A
Элемент qkij матрицы Ak(G) ориентированного псвдографа равен числу всех путей длины k из вершины υi в υj.
Теорема: для того, чтобы n - вершинный орграф D с матрицей смежности A(D) имел хотя бы один контур необходимо и достаточно, чтобы матрица k = A2 + + A3 + … + An имела не нулевые диагональные элементы.
Объединением графов G1(V1, X1) и G2(V2, X2) называется граф