2021秋季《离散数学》_图的度与同构

省流小助手：

• 判定度数列可否化为简单无向图，以及由度数列作图

顶点的度数与握手定理

度

无向图中，称$v_i$作为边的端点的次数之和为$v_i$的度数（度），记为$d_G(v_i)$，或简写为$d(v_i)$.

每个环提供给它的端点2度。

有向图中，

• $v_i$作为边的始点的次数之和为$v_i$的出度，记为$d_D^{?}(v_i)$，或简写为$d^{?}(v_i)$.
• $v_i$作为边的始点的次数之和为$v_i$的入度，记为$d_D^{+}(v_i)$，或简写为$d^{+}(v_i)$.
• 度：$d_D(v_i)$，或简写为$d(v_i)=d^{?}(v_i)+d^{+}(v_i)$.

最大度和最小度

最大度 Δ ( G ) = max ? { d ( v ) ∣ v ∈ V } \Delta(G)=\max \{d(v)|v\in V\} Δ(G)=max{ d(v)∣v∈V}，简写为$\Delta$.

最小度 δ ( G ) = min ? { d ( v ) ∣ v ∈ V } \delta(G)=\min\{d(v)|v\in V\} δ(G)=min{ d(v)∣v∈V}，简写为$\delta$.

同理定义最大/小出/入度。

握手定理

设$G=<V,E>$为任意一图（有向的或无向的）， V = { v 1 , v 2 , ? , v n } V=\{v_1,v_2,\cdots,v_n\} V={ v1?,v2?,?,vn?}，边的条数$|E|=m$，则
$$\sum _{i=1}^{n}d(v_i)=2m$$

推论

任何图（有向的或无向的）中，度数为奇数的顶点个数是偶数。

有向图

$$\sum _{i=1}^n{d}^{+}(v_i)=\sum _{i=1}^n{d}^{?}(v_i)=m$$

特殊的图

简单图

既无环也无平行边
$$0\le \Delta (G)\le n?1$$

可简单图化

充要条件

$\mathrm{H}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{l}$定理

设非负整数列 d = { d 1 , d 2 , ? , d n } d=\{d_1,d_2,\cdots,d_n\} d={ d1?,d2?,?,dn?}满足：
$$d_1+d_2+?+d_n\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)$$

$$n?1\ge d_1\ge d_2\ge ?\ge d_n\ge 0$$

则$d$可简单图化$?$
$$d^{\prime }=(d_2?1,d_3?1,?,d_{d_1+1}?1,d_{d_1+2},?,d_n)$$
可简单图化。

画图

$\mathrm{P}.\mathrm{E}\mathrm{r}\mathrm{d}\ddot{\mathrm{o}}\mathrm{s},\mathrm{T}.\mathrm{G}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{a}\mathrm{i},1960$

设非负整数列 d = { d 1 , d 2 , ? , d n } d=\{d_1,d_2,\cdots,d_n\} d={ d1?,d2?,?,dn?}满足：
$$d_1+d_2+?+d_n\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)$$

$$n?1\ge d_1\ge d_2\ge ?\ge d_n\ge 0$$

则$d$可简单图化$?$

对$r=1,2,?,$==$n?1$==有
d 1 + d 2 + ? + d r ≤ r ( r ? 1 ) + min ? { r , d r + 1 } + min ? { r , d r + 2 } + ? + min ? { r , d n } d_1+d_2+\cdots+d_r\leq r(r-1)+\min\{r,d_{r+1}\}+\min\{r,d_{r+2}\}+\cdots+\min\{r,d_{n}\} d1?+d2?+?+dr?≤r(r?1)+min{ r,dr+1?}+min{ r,dr+2?}+?+min{ r,dn?}

等价形式

设非负整数列 d = { d 1 , d 2 , ? , d n } d=\{d_1,d_2,\cdots,d_n\} d={ d1?,d2?,?,dn?}满足：
$$d_1+d_2+?+d_n\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)$$
则$d$可简单图化$?$

对$r=1,2,?,$==$n$==有
d 1 + d 2 + ? + d r ≤ r ( r ? 1 ) + min ? { r , d r + 1 } + min ? { r , d r + 2 } + ? + min ? { r , d n } d_1+d_2+\cdots+d_r\leq r(r-1)+\min\{r,d_{r+1}\}+\min\{r,d_{r+2}\}+\cdots+\min\{r,d_{n}\} d1?+d2?+?+dr?≤r(r?1)+min{ r,dr+1?}+min{ r,dr+2?}+?+min{ r,dn?}

k-正则图

所有顶点的度数都是$k$

完全图

无向完全图：$K_n$

有向完全图没有符号。

彼得森图

经常用来举反例（证明不充分/不必要）

r部图

顶点可以被分为$r$个部分的无向图，$V=V_1\cup V_2\cup ?\cup V_r,V_i\cap V_j=?(i?=j),E{?}_{i?=j}=U(V_i\&V_j)$，也记作$G=<V_1,V_2,?,V_r;E>$.

偶图（2部图）

$G=<V_1,V_2;E>$

条件

• $V=V_1\cup V_2,V_1\cap V_2=?$
• $?e\in E,|e\cap V_1|=|e\cap V_2|=1$

常给资源分配问题建立模型

完全偶图

$K_{|V_1|,|V_2|}$

容易证明$K_{|V_1|,|V_2|}$有$|V_1||V_2|$条边。

超立方体图

$Q_n$

• 有$2^n$个顶点

• 将两个$Q_{n?1}$的对应顶点连接，可得$Q_n$

在并行计算和超级计算中运用（处理器和处理器之间的连接）

子图

导出子图

选定顶点后需要带出所有的边/选定边后需要带出所有的顶点

图同构

无向图中，若存在双射$f:V_1\to V_2$，满足$?u,v\in V_1,(u,v)\in E_1?(f(u),f(v))\in E_2$，则称$G_1,G_2$同构，记作$G_1?G_2$.

有向图中，若存在双射$f:V_1\to V_2$，满足$?u,v\in V_1,<u,v>\in E_1?<f(u),f(v)>\in E_2$，则称$D_1,D_2$同构，记作$D_1?D_2$.

同构的图，其图论性质完全一致。

判定

NAUTY算法是性质非常好的算法

• 点数、边数、度数列
• 回路由多少顶点构成