Главная | Обратная связь

Практическое занятие №8. Задачи оптимизации на графах. Эйлеровы и гамильтоновы графы.

Если дуге ориентированного графа 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, в которой любые два соседних элемента инцидентны. Путь называется простым, если все ребра и все вершины на нем, кроме первой и последней, различны.

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

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

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

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

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

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