2021年秋计算系统概论。9.6-12.27
教学用书是《图论导论》。
1.1 图的定义
定义1.1. 一个无向图$G$是一个有序三元组$G=(V(G),E(G),\psi_G)$，其中，
- $V(G)\neq\empty$是顶点集合，任给$v\in V(G)称为一个顶点。
- $E(G)$是边集合，任给$e\in E(G)$称为一条边。
- $\psi_G:E(G)\rightarrow\{\{u,v\}|u,v\in V(G\}$称为边与顶点之间的关联函数。
给定图$G$，顶点的个数$|V(G)|$称为图$G$的阶，记为$v(G)$。图$G$的边数$E(G)$记为$\epsilon(G)$。若$v(G)+\epsilon(G)$为无穷大，则称$G$为无限图，否则称$G$为有限图。
- 在不引起混淆的情况下，$V(G),E(G),v(G),\epsilon(G)$和$\psi_G$分别简写记为$V,E,v,\epsilon$和$\psi$。
边与点关联：$\psi_G(e)=${$u,v$}。端点、相邻。重边，环。无环也没有重边的图叫简单图。
完全图$K_n$：其中任意两个顶点都相邻。
二分图：$V(G)=X\cup Y,X\neq\varnothing,Y\neq\varnothing,X\cap Y=\varnothing$。
完全二分图$K_{|X|,|Y|}$：其中$X$中任意一个顶点与$Y$中的任意一个顶点都相邻。
星图：完全二分图$K_{|1|,|n|}$或者$K_{|n|,|1|}$。
零图：图中仅有顶点没有边。
1.2 顶点度数
顶点度数$deg(v)$：$deg(v)=d_1(v)+2\times l(v)$。
顶点度数的最小值：$\delta(G)$；顶点度数的最大值：$\Delta(G)$。
子图：给定图 $G=(V(G),E(G))$ 与 $H=(V(H),E(H))$，若$V(H)\subseteq V(G)$且$E(H)\subseteq E(G)$，则称 $H$ 是 $G$ 的一个子图。记做 $H\subseteq G$。
真子图：$H\subseteq G$且$H\ne G$。记做$H\subset G$。
生成子图：$H\subseteq G$且$V(H)=V(G)$。
顶点导出子图：设顶点子集$V’$。顶点导出子图$G[V’]=(V’,E’)$，其中$E’=${$uv|uv\in E(G),u,v\in V’$}。将两个端点都在$V’$中的边放到顶点导出子图中。
边导出子图：设边子集$E’$。边导出子图$G[E’]=(V’,E’)$，其中$V’=${$v|$存在边$uv\in E$}。将在$E$中的每条边的两个端点放到边导出子图中。
⚠️顶点导出和边导出子图都是以其对应的子集作为筛选标准的。
补图：$G^c=(V(G^c),E(G^c))$。其中$V(G^c)=V(G)$，$E(G^c)=${$uv|u,v\in V(G^c)=V(G)$且$uv\notin E(G)$}。顶点集合相同，边取补集。
边图：$L(G)=(V(L(G)),E(L(G)))$。
图论的常用定理
第一章
1.1 (Euler，1736) 任给无向图G，$\sum_{v\in V(G)}deg(v)=2\varepsilon(G)$。
推论：任给图G，G中度数为奇数的顶点个数为偶数。
1.