图衍生

度

Laplacian矩阵

$L=D-A$：Laplacian矩阵，其中

• $A$：邻接矩阵
• $D$：度矩阵（对角线为各个顶点度）

性质

• 若$c$为图中各个节点权重，则$c^T L C$为各个节点与其 邻接节点差值平方和
  • 展开即可证明

边数量

Multigraph

多重图：含有平行边，即顶点之间边数大于1

• 允许顶点通过边和自己相连

边权

欧几里得类型加权图

欧几里得类型加权图：权重满足欧式几何条件

• 三角不等式：任意3点$i,j,k, d{ij} \leqslant d{ik}+d{kj}

• 对称性：任意两个点$i,j, d_{ij}=d{ji}$

连通性

Transitive closure

传递闭包：表示所有节点两两直接连通性的n阶布尔矩阵T

• $T={t{ij}}$，若节点i到节点j直接存在有效（长度>0）有向 路径，则$t{ij}=1$，否则为0

Hamiltonian Circuit

哈密顿回路：对图每个顶点只穿过一次的回路

• 可以理解为：n+1个相邻顶点的一个排列，其中首尾顶点相同， 而其余顶点互不相同

  • 因为是回路，可以不失一般性的假定回路开始、结束于相同 顶点，这样不影响回路性质

Eular Circuit

欧拉回路：将给定图每条边都只遍历一次的回路

• 无向图：当且仅当连通多重图的每个顶点连通度都为偶数时， 才具有欧拉回路

• 有向图：当且仅当图中所有顶点是否出度、入度相等时，才存在 欧拉回路

• 在$\O(n^)$内解决问题

State-Space Graph

状态空间图：把问题化简为标准图问题

• 顶点：表示问题可能状态
• 边：表示状态之间的可能转换
• 原问题转换为求初始状态到目标状态顶点路径问题