图

• 表示:$G=(V,E)$

无向图

• 弧(边):$(v_i,v_j)$
  • $(v_i,v_j)=(v_j,v_i)$
• 完全图:$\exists G=(V,E) |V|=n , E=\frac{n(n-1)}{2}$
• 度:$D(v)$
  • $|E|=\frac{1}{2}\sum^{|V|}_{i=1}D(v_i)$
• 路径:$\forall G=(V,E) , \exists v_p,v_q \in V , P=\{(v_p,v_{i\cdots}),(\cdots),(v_{i\cdots},v_q)\} \subseteq E$
• 环:$C=\{(v_p,v_q) \in P(G) : v_p=v_q\}$
  • 简单路径:$\exists C=(v_p,v_q) \iff v_p=v_q$
• 子图:$\exists G=(V,E) G'=(V',E'), G \subseteq G' \iff V \subseteq V' \& E \subseteq E'$
• 连通图:$\forall {v_n,v_m} \in V(G), (v_n,v_m) \in E(G)$
  • 连通分量(极大子图):$G'=G$

有向图

• 弧(边):$<v_i,v_j>$
  • $<v_i,v_j> \neq <v_i,v_j>$
• 完全图:$\exists G=(V,E) |V|=n , E=\frac{n(n-1)}{2}$
• 度:$D(v)$
  • 出度:$ID(v)$
  • 入度:$OD(v)$
  • $|E|=\frac{1}{2}\sum^{|V|}_{i=1}D(v_i)$
• 路径:$\forall G=(V,E) , \exists v_p,v_q \in V , P=\{<v_p,v_{i\cdots}>,(\cdots),<v_{i\cdots},v_q>\} \subseteq E$
• 环:$C=\{(v_p,v_q) \in P(G) : v_p=v_q\}$
  • 简单路径:$\exists C=(v_p,v_q) \iff v_p=v_q$
• 子图:$\exists G=(V,E) G'=(V',E'), G \subseteq G' \iff V \subseteq V' \& E \subseteq E'$
• 强连通图:$\forall {v_n,v_m} \in V(G), <v_n,v_m> \in E(G)$
  • 强连通分量(极大子图):$G'=G$

网（赋权图）

$$G=(V,E) \iff \forall e \in E(G), |e| \in \R$$

有向树

$$G=(V,E) \iff |{v \in V : ID(v)=0}|=1$$

AOV

使用有向图

AOE

使用有向赋权图表示

McCabe度量程序复杂度

$$G=(V,E) \text{环路复杂度}=\text{G的环路的个数}=|E|-|V|+2|G'|$$