Задачи оптимизации на графах

Если дуге ориентированного графа G₁ (V, E) поставлено в соответствие некоторое вещественное число a (u, v), называемое весом, то последовательность вершин v ₀, v ₁,..., v_p определяет путь в G₁ а его длина определяется как сумма весов: . Если в произвольном графе вес каждой дуги равен единице, то длина пути равна числу дуг.

Задача о кратчайшем пути возникает чаще всего при решении транспортных и дискретных задач динамического программирования и др. Длину кратчайшего пути обозначают r (v_i, v_j) и называют расстоянием от v_i до v_j (расстояние может быть отрицательным). Для любого орграфа можно построить матрицу расстояний R=r (i, j). Заполняется матрица построчно, выбирая вершину слева (справа). Значением является наименьшее число дуг, связывающее вершину слева с одной из вершин строки.

Если не существует ни одного пути из v_i в v_j, то полагаем r (v_i, v_j) = ¥. Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v ₁,..., v_p не будет повторов.

Среднее отклонение вершины v_i от центра графа D(v_i) равно:

,

где m - число дуг в графе, v - пробегает вершины графа, n – количество вершин графа, i = 1..n.

Вершина, для которой D(v_i) окажется минимальным, называется центром графа (возможно несколько вершин – центр графа).

Путем или маршрутом на графе G₁(V,E) называется последовательность его вершин и ребер v1e1v2e2v3…vnen vn+1, в которой любые два соседних элемента инцидентны. Путь называется простым, если все ребра и все вершины на нем, кроме первой и последней, различны.

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

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

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

Если в графенет циклов, то он называется ациклическим.

Теперь можно иначе определить понятие дерева. Связный граф без циклов называется деревом.

Примеры выполнения заданий

7) 1. Орграф задан геометрически.

Постройте матрицу расстояний.

Вычислите центр орграфа.

Решение:

построим матрицу расстояний:

R= r (i, j):