20
правок
Omeln (обсуждение | вклад) Нет описания правки |
Omeln (обсуждение | вклад) Нет описания правки |
||
Строка 3: | Строка 3: | ||
= Постановка задачи = | = Постановка задачи = | ||
Алгоритм Фрюхтермана-Рейнгольда относится к семейству силовых (forced-directed) алгоритмов укладки графов на плоскости, в котором используятся пружинная физическая модель, где вершины графа определяются как тела системы, а ребра как пружины. Силы могут действовать только на вершины, вес пружин при этом не учитывается. Имеется простой неориентированный граф <math>G = (V, E)</math>. У каждой вершины из множества V в качестве переменных используются координаты ее размещения <math> | Алгоритм Фрюхтермана-Рейнгольда относится к семейству силовых (forced-directed) алгоритмов укладки графов на плоскости, в котором используятся пружинная физическая модель, где вершины графа определяются как тела системы, а ребра как пружины. Силы могут действовать только на вершины, вес пружин при этом не учитывается. Имеется простой неориентированный граф <math>G = (V, E)</math>. У каждой вершины из множества <math>V</math> в качестве переменных используются координаты ее размещения <math>V_x</math> и <math>V_y</math>, а также <math>V_f</math> - вектор силы, направленный на приведение физической системы в равновесие. | ||
= Описание алгоритма = | = Описание алгоритма = | ||
Строка 16: | Строка 16: | ||
= Описание модели = | = Описание модели = | ||
<math> l = \sqrt{area/|V|} </math> - Идеальная длина пружины для ребра e | <math> l = \sqrt{area/|V|} </math> - Идеальная длина пружины для ребра <math>e</math> | ||
<math>p_v = (x_v, y_v)</math> - Вектор положения вершины v | <math>p_v = (x_v, y_v)</math> - Вектор положения вершины <math>v</math> | ||
<math>||p_v - p_u || </math> - Евклидовое расстояние между вершинами u и v | <math> ||p_v - p_u || </math> - Евклидовое расстояние между вершинами <math>u</math> и <math>v</math> | ||
<math> (p_u, p_v) </math> - | <math> (p_u, p_v) </math> - Направленный вектор из вершины <math>u</math> в <math>v</math> | ||
Для всех вершин действует сила отталкивания | Для всех вершин действует сила отталкивания |
правок