Warning
- 计算度时，无向图自环算两次
- 基本图
- 点 边 有向图 无向图
- 基图 := 有向图の对称闭包 (一定是无向图)
- $n$ 阶图 := 有 $n$ 个点の图
- 零图 := 没有边の图
- 简单图 := 不含重边&自环
- 度
- 度数$d(v)$ 入度$d^{-}(v)$ 出度$d^{+}(v)$
- 悬挂点 := 度数为 1
- 悬挂边 := 悬挂点の唯一那条边
- 孤立点 := 度数为 0
- 握手定理
- 无向图 $\sum d(v)=2\lvert E \rvert$
- 有向图 $\sum d^{-}(v)=\sum d^{+}(v)=\lvert E \rvert$
- 任何图の奇度顶点个数为偶数个
- 对称图
- $k$正则图 := 所有点的度都为 $k$
- 完全图 $K_{n}$ := 任意两点均有邻接
- 圈 $C_{n}$
- 轮 := $C_{n}$ + 一个与圈上所有点邻接的轴点
- $n$立方图 $Q_{n}$ :=
- 有 $2^{n}$ 个顶点
- 顶点有连线 $\equiv$ 二进制编码相差恰一位
- 二部
- 二部图
- $V=V_{1}+V_{2}$
- $V_{1,2}$ 内部无邻接，相互之间有邻接
- 完全二部图 $K_{m,n}$
- 二部图 且 $\lvert V_{1} \rvert=m,\lvert V_{2} \rvert=n$
- $V_{1}$ 所有点都与 $V_{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'$
- 存在 $f:V\to V$
- $\forall (u,v)\in E(\exists!(u’,v’)\in E’(u’=f(u)\land v’=f(v)))$
- $\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’$ :=
- $\forall V’’\subset V’\subset V$
- $p(G-V’)>p(G)$
- $p(G-V’’)=p(G-V’)$
- 连通度 $k(G)=\mathrm{min} { \lvert V’ \rvert | V’是G点割集 }$
- 边割集 $E’$ :=
- $\forall E’’\subset E’\subset E$
- $p(G-E’)>p(G)$
- $p(G-E’’)=p(G-E’)$
- 边连通度 $\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)$
- 弱连通 := 基图是连通图