基本图

• 点 边 有向图 无向图
• 基图 := 有向图の对称闭包 (一定是无向图)
• $n$ 阶图 := 有 $n$ 个点の图
• 零图 := 没有边の图
• 简单图 := 不含重边&自环
• 度
  • 度数$d(v)$ 入度$d^{-}(v)$ 出度$d^{+}(v)$
  • 悬挂点 := 度数为 1
    • 悬挂边 := 悬挂点の唯一那条边
  • 孤立点 := 度数为 0
  • 握手定理
    1. 无向图 $\sum d(v)=2\lvert E \rvert$
    2. 有向图 $\sum d^{-}(v)=\sum d^{+}(v)=\lvert E \rvert$
    3. 任何图の奇度顶点个数为偶数个
• 对称图
  • $k$ 正则图 := 所有点的度都为 $k$
  • 完全图 $K_{n}$ := 任意两点均有邻接
  • 圈 $C_{n}$
  • 轮 $W_{n}$ := $C_{n}$ + 一个与圈上所有点邻接的轴点
    • $n\neq3$ 的轮不是正则图！中心点度不一定是 $3$
  • $n$ 立方图 $Q_{n}$ :=
    1. 有 $2^{n}$ 个顶点
    2. 顶点有连线 $\equiv$ 二进制编码相差恰一位
  • 正则图判定
    1. 完全图 $K_{n}$ $\in$ $n-1$ 正则图
    2. 圈 $C_{n}$ $\in$ $2$ 正则图
    3. 轮 $W_{3}$ $\in$ $3$ 正则图
       1. $W_{n\neq 3}$ $\notin$ 正则图
    4. $n$ 立方图 $\in$ $n$ 正则图
• 二部
  • 二部图
    1. $V=V_{1}+V_{2}$
    2. $V_{1,2}$ 内部无邻接，相互之间有邻接
  • 完全二部图 $K_{m,n}$
    1. 二部图 且 $\lvert V_{1} \rvert=m,\lvert V_{2} \rvert=n$
    2. $V_{1}$ 所有点都与 $V_{2}$ 所有点有邻接
  • 二部图判定
    • 特殊图判定
      • $K_{1},K_{2}$ $\in$ 二部图
        • $K_{n\geq3}$ $\notin$ 二部图
      • $C_{2k}$ $\in$ 二部图
        • $C_{奇数}$ $\notin$ 二部图
      • $W_{n}$ $\notin$ 二部图
      • $Q_{n}$ $\in$ 二部图
    • 一般判定
      1. $\Leftrightarrow$ 无奇圈
      2. 黑白染色，相邻异色
• 子图
  • 子图$(V’,E’)$ := $V’\subset V \land E’\subset E$
  • 生成子图$(V’,E’)$ := $V’=V\land E’\subset E$
  • 导出子图$(V’,E’)$ := $V’\subset V \land E’={ e | uev \land u,v\in V’ }$ $\equiv$ 保留两端均在 $V’$ 的边
• 删除
  • 删点 := $(V,E)-V’=(V-V’,两端都不在V’的E)$
  • 删边 := $(V,E)-E’=(V,E-E’)$
  • 删子图 := $(V,E)-(V’,E’)=(V,E-E’)$
  • 加边 := $G\cup(u,v)$ 或 $G+(u,v)$
  • 补图 $\bar{G}$ := $K_{n}-G$
• 同构 $G\sim G'$
  1. 存在 $f:V\to V$
  2. $\forall (u,v)\in E(\exists!(u’,v’)\in E’(u’=f(u)\land v’=f(v)))$
  3. $\forall (u’,v’)\in E’(\exists!(u,v)\in E(u=f^{-1}(u’)\land v=f^{-1}(v’)))$

连通性

• 通路
• 回路 := 首尾顶点相同
• 简单通路/回路 := 无重复边
• 初级通路/回路 := 无重复点
  • 初级 $\subset$ 简单
• 无向图
  • 连通分支 = 连通分量 := $u/ \leftrightarrow$ 或 $[u]_{\leftrightarrow}$
  • 连通分支数 $p(G)$ := $\lvert [u]_{\leftrightarrow} \rvert$
  • 连通图 := $p(G)=1$
  • 点割集 $V’$ :=
    1. $\forall V’’\subset V’\subset V$
    2. $p(G-V’)>p(G)$
    3. $p(G-V’’)=p(G)$ $\Rightarrow$ 删更少点不会改变连通度！
  • 连通度 $k(G)=\mathrm{min} { \lvert V’ \rvert | V’是G点割集 }$
  • 边割集 $E’$ :=
    1. $\forall E’’\subset E’\subset E$
    2. $p(G-E’)>p(G)$
    3. $p(G-E’’)=p(G)$ $\Rightarrow$ 删更少边不会改变连通度！
  • 边连通度 $\lambda(G)=\mathrm{min} { \lvert E’ \rvert | E’是G边割集 }$
• 有向图 (精髓：强连通缩点)
  • 强连通 := $\forall u\forall v (u\to v \land v\to u)$
  • 有向连通 := $\forall u\forall v(u\to v\lor v\to u)$
  • 弱连通 := 基图是连通图

应用

• 最短路 = dijkstra 画表格
  1. 第 0 行 $v_{s}=0$
  2. 框中本行最小，再从该点往外遍历，填本行
  3. 本行除最小点外下移到下一行，重复 2.
  4. 直到所有点都框过