Главная|Решения онлайн |Теория | Основные формулы и обозначения |Обратная связь |


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

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

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

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

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

di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1}- формула расчета элементов матрицы Dm по известным элементам матрицы Dm-1

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

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

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

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

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

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

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

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

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

Центр графа

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

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

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

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

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

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

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

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

 

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

Симплекс метод (формулы пересчета элементов симплекс-таблиц)

ak,l'= 1/ak,l - для ведущего элемента

ai,l'=-ai,l/ak,l - для ведущего столбца

ak,j'=ak,i/ak,l - для ведущей строки

ai,j'= ai,j- ai,l×ak,j/ ak,l - для остальных элементов таблицы

 

 

 



R336709263964 - WebMoney 41001419134483 - Яндекс Деньги
WebMoneyПонравился сайт? Окажите помощь в развитиияндекс