图

点/边

图是一个二元集合组：$G = (V(G), E(G))$

• $V(G)$ $:=$ 点集 (vertex set)
  • $\forall v \in V(G)$ $:=$ 顶点(vertex)/节点(node)
  • $\left| V(G) \right|$ $:=$ 阶 (order)
• $E(G)$ $:=$ 边集 (edge set)
  • 无向边(undirected edge)：$\forall e \in E(G)$，$e = (u,v)$ 无序
  • 有向边(directed edge)/弧(arc)：$\forall e \in E(G)$，$e = (u,v)$ 有序，aka $e = u \to v$
    • 其中 $u$ $:=$ 起点(tail)
    • 其中 $v$ $:=$ 终点(head)
  • 若边有权，则图为赋权图。权全为正实数，则图为正权图

相邻

在无向图 $G = (V, E)$ 中

• 边点关联/相邻：$\mathrm{adjacent(e,v)}$ / $\mathrm{incident}(e, v)$ $:=$ $\exists \ e = (u, v) \in E$

• 点点相邻：$\mathrm{adjecent}(u,v) := \exists \ e = (u,v) \in E$

• 单点邻域：$N(v) := { u \in V \ | \ \mathrm{adjacent(u,v)} }$

• 点集邻域：$N(S) := \bigcup\limits_{v \in V} N(v)$