【图论笔记】图论基础（8）：分解与覆盖

---

目录

• 1. 图分解
• 2. 图覆盖
• 返回【图论笔记】

---

1. 图分解

设$G$是一个图，$\mathcal{F}$是一个由$G$的边不交的子图构成的图族．如果$\mathcal{F}$满足：$\bigcup_{F\in \mathcal{F}}F=G,$则称$\mathcal{F}$是$G$的一个分解．

• 如果$\mathcal{F}$的每个成员都是圈，则称这个分解是图$G$的圈分解．
• 并不是所有图都有圈分解，下面的定理表明只有偶图才有圈分解．
• 所谓偶图，即所有顶点的度都是偶数的图．

定理1.（Veblen定理） 一个图有圈分解，当且仅当它是偶图．

证明. $(\Rightarrow)$ 因为图分解是边不交的，所以此方向显然成立．

$(\Leftarrow)$. 设$G$是偶图．对$e(G)$做归纳．当$e(G)=0$时，只需取$\mathcal{F}$为空集即可．假定$e(G)<m$时结论仍成立，现在考虑$e(G)=m$的情况．在$G$中删除所有的孤立点，设所得的图为$H$，显然$H$仍然是偶图且$e(H)=e(G)=m$．因为$H$是没有孤立点的偶图，所以$\delta(H)\ge 2$，那么$H$有圈$C$，令$H'=H\setminus E(C)$．显然$H'$仍然是偶图但边数更少，由归纳假设知$H'$有圈分解，所以$H$有圈分解，进而$G$有圈分解．$\Box$

---

2. 图覆盖

设$G$是一个图，$\mathcal{F}$是一个由$G$的子图构成的图族（不要求边不交）．如果$\mathcal{F}$满足：$\bigcup_{F\in \mathcal{F}}F=G,$则称$\mathcal{F}$是$G$的一个覆盖．

• 如果$G$的每条边都被$\mathcal{F}$覆盖$k$次，则称这个覆盖是 $k$-覆盖．
• $1$-覆盖就是分解．
• $2$-覆盖也称 双覆盖．
• 如果$\mathcal{F}$的成员都是圈，那么$\mathcal{F}$叫做$G$的一个圈覆盖．
• 如果一个覆盖既是$G$的圈覆盖，又是$G$的双覆盖，那么我们称之为$G$的双圈覆盖．
• 关于双圈覆盖有著名的双圈覆盖猜想．

设$e$是连通图$G$的一个边，如果$G\setminus e$不连通，则称$e$是$G$的一个割边．

双全覆盖猜想. 无割边的图有双圈覆盖．

---

返回【图论笔记】