【图论笔记】图论基础（4）：图运算

---

目录

• 1. 并、交和差
• 2. 粘合与收缩
• 3. 分裂和细分
• 4. 图的笛卡尔积
• 返回【图论笔记】

---

1. 并、交和差

• 如果两个图的顶点集的交为空集，则称这两个图是不交的；如果两个图的边集的交为空集，则称这两个图是边不交的。

设$G$和$H$是两个图。

• $G\cup H$是一个新图，称为$G$和$H$的并，其顶点集$V(G\cup H)=V(G)\cup V(H)$，其边集$E(G\cup H)=E(G)\cup E(H)$；特别地，如果$G$和$H$是不交的，则称其并为不交并，记作$G+H$。

注：每个图都是其所有连通分支的不交并。

• $G\cap H$是一个新图，称为$G$和$H$的交，其顶点集$V(G\cap H)=V(G)\cap V(H)$，其边集$E(G\cap H)=E(G)\cap E(H)$；特别地，如果$G$和$H$是不交的，那么其交为零图。

• $G\setminus H$也是一个新图，称为$G$和$H$的差，其顶点集$V(G\setminus H)=V(G)\setminus V(H)$，其边集$E(G\setminus H)=E(G)\setminus E(H)$。

注：

• 设$A,B$是两个集合。$A\setminus B=\{x\in A:x\not\in B\}$。
• 有人也喜欢把$G\setminus H$写作$G-H$。

• $G\triangle H$是一个新图，称为$G$和$H$的对称差，其定义为$G\triangle H=(G\cup H)\setminus(G\cap H)$。

---

2. 粘合与收缩

• 设$G$是一个图，$u,v\in V(G)$。我们可以将$u$和$v$粘合为一个新顶点，使得在$G$上与$u$关联的所有边和与$v$关联的所有边都与新顶点关联，记所得的新图为$G/\{u,v\}$。

注意：

• 区分$G/\{u,v\}$和$G\setminus\{u,v\}$；
• 如果$uv\in E(G)$，那么粘合$u,v$会制造出一个环。

• 设$G$是一个图，$e=uv\in E(G)$。我们可以将边$e$收缩为一个新顶点，具体操作是：在$G$中删除$e$然后将$u,v$粘合，记所得的新图为$G/e$。

注意：区分$G/e$和$G\setminus e$。

• 更一般地，设$G$是一个图，$H$是$G$的子图，将$H$中的所有边都收缩得到的新图记作$G/H$。

---

3. 分裂和细分

• 设$G$是一个图，$v\in V(G)$。我们可以将$v$分裂为两个新顶点$v'$和$v''$，使得在$G$上与$v$关联的边要么与$v'$关联，要么与$v''$关联（环除外，如果$v$在$G$上关联一个环$e$，那么分裂后$e$与$v'$和$v''$都关联）。

• 设$G$是一个图，$e=uv\in E(G)$。我们可以将$e$细分，即删除$e$，在加入新顶点$x$，并连接$ux$和$vx$。

• 如果$G$是$H$经过一系列细分得到的，则称$G$是一个 $H$-细分。

边细分在拓扑图论中有特别的应用，例如一个图是可平面图当且仅当它没有$K_5$-细分和$K_{3,3}$-细分作为子图。

---

4. 图的笛卡尔积

• 设$A,B$是两个集合，定义$A\times B=\{(a,b):a\in A,b\in B\}$，称之为$A$和$B$的笛卡尔积。

• 设$G$和$H$是两个图。定义$G$和$H$的笛卡尔积为$G\Box H$，满足：

  • $V(G\Box H)=V(G)\times V(H)$；
  • $G\Box H$上两个顶点$(u_1,v_1)$和$(u_2,v_2)$相邻当且仅当如下两种情况之一发生：(1) $u_1u_2\in E(G)$且$v_1=v_2$，(2) $u_1=u_2$且$v_1v_2\in E(H)$。

• $n$个顶点的路和圈分别记作$P_n$和$C_n$（注意：$P_n$的长度是$n-1$）。
• 显然，$P_2\Box P_2=C_4$
• $P_m\Box P_n$通常称为 $m\times n$-网格，直观上看它确实与我们熟知的网格相似。

---

• 返回【图论笔记】