8.图
图的分类
- n 阶图：n个顶点的图
- 连通图：节点度数都大于等于1
- 有限图：V，E 都是又穷集合的图
- 零图：\(E= \emptyset\)
- 平凡图：1阶零图
- 空图：\(V=\emptyset\)
- 完全图：每个节点都与其余节点邻接
- 边数m = n(n-1)/2；任意节点度数为 \(n-1\)，度数和 \(n(n-1)\)
- 正则图：所有定点的度数都为 k；性质类似完全图
- 简单图：不包含环和平行边的图
- 多重图：允许存在环和平行边的图
- 补图：
子图
一个图的节点集和边集的子集构成的图
生成子图
节点集等于原图，边集的子集构成的图
例题
8阶简单图的最大边数-> 8阶完全图
\(\frac{n(n-1)}{2}\)
图的连通性
通路
\[\Gamma = v_{i_0} e_{j_1} v_{i_1}e_{j_1} v_{i_2}... e_{j_n} v_{i_n}\]
称之为 连接 \(v_{i_0}\) 到 \(v_{i_n}\)的通路
| 分类 | 边都不同 | 起点终点相同 | 所有顶点不同（起终除外） |
|---|---|---|---|
| 初级通路 | ✅ | ||
| 初级回路 | ✅ | ✅ | |
| 简单通路 | ✅ | ||
| 简单回路 | ✅ | ✅ |
Note
- 初级：点不同
- 简单：边不同
- 哈密顿图研究的是初级通路
- 欧拉图研究的是简单通路
- 记法：欧拉图比较简单，欧拉图走桥（边）
通路相关的定理
- n 阶图的两个节点存在通路，则长度一定小于等于 n-1
- n 阶图的两个节点存在通路，则存在一个初级通路（节点不同），长度小于等于 n-1
- 回路则长度 小于等于 n
- 如存在一个简单回路，则存在一个初级回路长度小于等于n
连通分支数 W
- W，图中不连通的部分的个数
- W(G) = 1 图是连通的
割
点割集：删除这些点后 W 变大，并且是最少的；只有一个元素时称为割点 边割集：删除这些边后 W 变大，并且是最少的；只有一个元素时称为割边或桥
有向图可达
- u可达v：u 到v 有通路，节点自身是可达的
- 弱连通：基图为无向连通图
- 单向连通：任意两个节点，有一边可达
- 强连通：任意两个节点，都相互可达
邻接矩阵M相关定理
设 A 为n阶有向图 D 的邻接矩阵， 则 \(A^l (l \ge 1)\)中元素
- \(a_{ij}\) 为D 中 \(v_i\) 到 \(v_j\) 边的个数
- \({a_{ij}}^{(l)}\) 为 D 中 \(v_i\) 到 \(v_j\) 长度为 l 的通路数
- \({a_{ii}}^{(l)}\) 为 D 中 \(v_i\) 到自身 长度为 l 的回路数
- \(\sum_{i=1}^{n} \sum_{j=1}^{n} {a_{ij}}^{(l)}\) 为 D 中长度为 l 的通路总数
- \(\sum_{i=1}^{n} {a_{ii}}^{(l)}\) 为 D 中长度为 l 的回路总数
设 \(B_l = A + A^2 + A^3 +...+ A^{l}\)，则\(B_l\)中元素
- \(\sum_{i=1}^{n} \sum_{j=1}^{n} {b_{ij}}^{(l)}\) 为D 中长度小于或等于 l 的通路数
- \(\sum_{i=1}^{n} {b_{ii}}^{(l)}\) 为 D 中长度小于或等于 l 的回路数
可达矩阵 P(G)
- 可达矩阵由连通矩阵生成，
\[B_n = A + A^2+ A^2+...+ A^n\]
\[B_n = A \lor A^2 \lor A^2 \lor ... \lor A^n\]
再将 \(B_n\)中大于1的元素改为1
握手定理
- 所有定点的度数之和等于边数的两倍；有向图的出度等于入度
- \(\Sigma Deg(v) = 2|E|\)
- 推论：图中奇数顶点点的个数一定为偶数