Формулы

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

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

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

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 — для остальных элементов таблицы

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...