Пути во взвешенных ориентированных графах

Определение. Ориентированный граф называется нагруженным, если дугам этого графа поставлены в соответствии веса, так, что дуге (xi,xj) сопоставлено некоторое число Cij, называемое длиной (или весом или стоимостью) дуги.

Длиной (весом или стоимостью) пути S состоящего из некоторой последовательности дуг, называется некоторое число L(s) равное сумме длин дуг, входящих в этот путь. Причём суммирование ведется по всем дугам принадлежащим пути S.

Матрица C ={cij} называется матрицей весов или матрицей длин дуг.

Определение. Четверка с элементами {x,y,f,g} называется помеченным графом, где пара функций fg пометка или распределение графа G(x,y).

F – распределение меток вершин, g – распределение меток дуг.

Для вершины A принадлежащей X элемент f(A) называется весом вершины A. Для дуги y принадлежащей Y элемент G(Y) называется весом дуги.

Составим матрицу C

X- множество вершин. X={a1,a2,a3,a4}.

Y- множество дуг. Y=[a,a2] [a2,a3] [a1,a4] [a2,a4]

F(a1) – Омск, F(a2) – Новосибирск, F(a3) –Кемерово, F(a4) – Павлодар.

G(a1,a2) = 681, G(a2,a3)=274, G(a1,a4)=413,G(a2,a4)=589

Составить помеченный граф, который будет схемой дорог между городами. И подставим информацию о весах дуг в виде матрицы весов.

Если число дуг в графе мало по сравнению с числом вершин, то этот граф называется разреженным. И более эффективным способом является задание его с посредством списка дуг. Этот список задается двумя наборами.

Вектор m=(1,1,2,3,4,4)

Вектор n=(1,2,3,4,3,4)

Другим представлением графа удобным при работе с графами в котором удаляются или добавляются вершины является структурой смежности, получаемая составлением для каждой вершины xi добавляется список номеров её последователей, т.е. номеров вершин xj для которых имеется дуга (xi,xj).