澹台千儿

在这篇文章中，我希望整理力导图的建模基础，为以后的改进做准备。选取的文章是 Graph Drawing by Force-directed Placement。 # 概述 力导图 (force-directed graph) 是无向图的平面布局方式。在力导图中，顶点建模为质点，质点间力的大小根据图中边的连接确定，当整个物理模型在力的作用下达到平衡，就完成了力导图的绘制。 下面，我们假设力导图所对应的图G(V,E)G(V,E)G(V,E)...

# 单源最短路问题 对有权有向图 G=(V,E)G = (V,E)G=(V,E), 我们定义其路径 p=⟨v0,v1,…,vk⟩p = \langle v_0,v_1,\dots,v_k \ranglep=⟨v0​,v1​,…,vk​⟩ 的权 w(p):=∑i=1kw(vi−1,vi)w(p):=\sum_{i=1}^kw(v_{i-1},v_i)w(p):=∑i=1k​w(vi−1​,vi​). 对顶点 u,vu,vu,v 若存在从 uuu 到 vvv 的路径，我们定义 uuu 到 vvv 的最短路权重...

# 向量和矩阵范数 我们采用范数作为向量或矩阵间距离的衡量。 # 向量范数 向量范数 (norm) 是一个 Rn→R\mathbb{R}^n \to \mathbb{R}Rn→R 的映射 ∥⋅∥\|\cdot\|∥⋅∥, 满足以下的性质： 非负性: ∥x∥≥0\|\boldsymbol{x}\| \geq 0∥x∥≥0; 正定性: ∥x∥=0\|\boldsymbol{x}\| = 0∥x∥=0 当且仅当x=0\boldsymbol{x} = \boldsymbol{0}x=0; 齐次性: ∥αx∥=∣α∣∥x∥\|\alpha \boldsymbol{x}\| =...

实际上是求连续问题的离散解。 # 初值问题 我们称形如条件 dydt=f(t,y),a≤t≤b, y(a)=α\frac{\mathrm dy}{\mathrm dt} = f(t,y), \quad a \leq t \leq b, \ y(a) = \alpha dtdy​=f(t,y),a≤t≤b, y(a)=α 的问题为常微分方程的初值问题 (initial-value problem). # 李普希茨条件 若函数 f:D→Rf: D \to \mathbb{R}f:D→R 满足对 ∀x1,x2∈D\forall x_1,x_2 \in...

# 最小生成树问题 在有权的无向连通图 G=(V,E)G=(V,E)G=(V,E) 中，我们希望寻找一棵树，使得树上全体边的权重和最小，即 w(T)=∑e∈T(E)w(e)w(T) = \sum_{e \in T(E)}w(e) w(T)=e∈T(E)∑​w(e) 最小。我们称这样的树为最小生成树 (minimum spanning tree, MST). 称其为最小的，因为其权重和是最小的。对于给定的图 G(V,E)G(V,E)G(V,E),...