Формулы

Основные формулы

Теория графов

Алгоритм Дейкстры

d(x)=min{d(x); d(y)+ a_y,x}- формула пересчета текущего пути до вершины x на каждом шаге алгоритма.

Алгоритм Флойда

d_i,j^m=min{ d_i,m^m-1+ d_m,j^m-1; d_i,j^m-1}- формула расчета элементов матрицы D^m по известным элементам матрицы D^m-1

Медиана графа

CВВ(i)=Σ_jd_i,j – формула для расчета суммаронго расстояния вершина-вершина

Главная медиана графа

d'(j, (r, s))= d_j,r+ d_j,s +a_r,s/2 – расчет элемента матрицы D’ в случае если дуга (r, s) – ориентированная

d'(j, (r, s))= d_j,r+ a_r,s – расчет элемента матрицы D’ в случае если дуга (r, s) неориентированная.

СВД(i)=Σ_jd'(j, (r, s)) – формула для расчета суммарного расстояния вершина-дуга

Абсолютная медиана графа

d(f—(r,s ), j)=min{f×а_r,s +d_r,j, (1—f)×а_{r, s}+d_s,j} – формула для расчета расстояний точка-вершина

СТВ (f — (r, s) = Σ d(f — (r, s), j) – формула для расчета суммарного расстояния точка-вершина

Центр графа

МВВ(i)=max {d(i, j)} – формула для расчета максимального расстояния вершина-вершина (расстояние от вершины i до наиболее удаленной вершины графа).

Главный центр графа

d'(j, (r, s))= d_j,r+ d_j,s +a_r,s/2 – расчет элемента матрицы D’ в случае если дуга (r, s) – ориентированная

d'(j, (r, s))= d_j,r+ a_r,s – расчет элемента матрицы D’ в случае если дуга (r, s) неориентированная.

МВД(i)=max{d'(j, (r, s))} – формула для расчета максимального расстояния вершина-дуга (расстояние от вершины i до маиболее удаленной точки на дуге графа.

Абсолютный центр графа

d(f—(r,s ), j)=min{f×а_r,s +d_r,j, (1—f)×а_{r, s}+d_s,j} – формула для расчета расстояний точка-вершина

МТВ (f — (r, s) = max {d(f — (r, s), j)} – формула для расчета максимального расстояния точка-вершина (расстояние от точки на дуге (r, s) до наиболее удаленной вершины графа).

Линейное программирование

Симплекс метод (формулы пересчета элементов симплекс-таблиц)
a_k,l‘= 1/a_k,l – для ведущего элемента
a_i,l‘=-a_i,l/a_k,l – для ведущего столбца
a_k,j‘=a_k,i/a_k,l – для ведущей строки
a_i,j‘= a_i,j– a_i,l×a_k,j/ a_k,l – для остальных элементов таблицы