《图论及其应用》复习
以下为《《图论及其应用》复习》的无排版文字预览，完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。
《图论及其应用》复习 基础与前沿研究院 谭某某 2019 年 6 月 30 日 声明：此复习资料整理自王某某老师课堂 PPT 和作业习题，我只是搬运工，其中如有 书写错误，还请见谅，另，此资料只作复习使用，更多的知识在课堂之外． ——基础与前沿研究院：谭某某 做题细心一点，时间是足够的，错的往往是自己会的，预祝各位同学考出满意的 成绩． ——王某某老师 3 ( 4 )点非同构简单图 4 ( 11 )个 自补图除以 4 的余数只能为 0 或 1 G1 ∨ G2, 点 : n1 + n2, 边 : m1 + m2 + n1n2 G1 × G2, 点 : n1n2, 边 : n1m2 + n2m1 G1 [G2] , 点 : n1n2, 边 : n1m2 + n22m1 A2 的元素 ai(i2) 是 vi 的度数 A3 的元素 ai(i3) 是含 vi 的三角形的数目的两倍 vi 到 vj 长度为 k 的通道的数目是 ai(jk) 矩阵 A 的所有特征值的平方和等于该图边数的 2 倍 Kn 的最大特征值为 n − 1 n 阶完全偶图 一、图的基本概念 非同构的 4, 5, 6 阶树的个数分别为 2, 3, 6 由 k 颗树组成的森林满足 m = n − k τ (Kn) = nn−2, τ (km,n) = nm−1mn−1 二、树 阶数 ≥ 3 的无环连通图，有割边 ⇒ 有割点 (1)κ (Kn) = n − 1, (2)κ (Cn) = 2， 其中 Cn为n圈 , n ≥ 3. (1)λ (Kn) = n − 1, (2)λ (Cn) = 2， 其中 Cn为n圈 , n ≥ 2. k 连通一定是 k 边连通的 κ(G) ≤ λ(G) ≤ δ(G) ， κ(G) ≤ ⌊2m/n⌋. 图 G 的顶点数为 n 且 7 连通，则其边数至少为 ⌈7n/2⌉ 三、图的连通度 Euler图没有割边，有可能有割点 一必要( ω(G − S) ≤ "#S"# ) 四充分( δ(G) ≥ n 2 , d(u) + d(v) ≥ n， 闭包是完全图， "#E(G)"# > ( n−1 2 )+1 ) 一充要(闭包是 H图) ∀m < n/2 ，或有 dm > m ，或有 dn−m ≥ n − m ，则H图 具有 5 个点的度极大非XX尔顿图族为 C15 和 C25 n 阶完全图中H圈的个数为 (n − 1)! 四、Euler图与Hamilton图 m 元完全树： mi = t + i − 1 二元完全树： m(T ) = 2(t − 1) 高度为h的二元完全树最少有h + 1片叶子 八、有向图 《图论及其应用》 知识大纲总结 基础与前沿研究院 谭某某 任课教师:Prof.王某某 五、匹配与因子分解 (Hall): "#N(S)"# ≥ "#S"# K2n 完美匹配个数： (2n − 1)!! Kn,n 完美匹配个数： n! 每个没有割边的 3 正则图都有完美匹配。 有割边的 3 正则图不一定就没有完美匹配。 3 正则图有割边，则不可 1 因子分解 无割边的 3 正则图可能也没有 1 因子分解 奇数阶图不能有 1 因子 一个连通图是 2 可因子化的当且仅当它是偶数度正则图 具有H圈的 3 正则图是 1 可因子化的(反之不一定成立) ∑ deg(f) = 2m. 欧拉公式：n − m + φ = 2 简单平面图满足 m ≤ 3n − 6 至少有 9 个点的简单可平面图的补图是不可平面的 可平面的当且仅当它不含与 K5 或 K3,3 同胚的子图 极大平面图必连通，且 n ≥ 3 则无割边，三角形特征 六、平面图 极大平面图满足： m = 3n–6, φ = 2n–4 极大外平面图当且仅当其外部面的边界是圈，内部面是三角形 极大外平面图有 n − 2 个内部面 至少有 7 个顶点的外可平面图的补图不是外可平面图 G∗的点数 = G的面数; G∗的边数 = G的边数； G∗的面数 = G的点数(G连通)； 同构的平面图可以有不同构的对偶图 七、图的着色 χ′ (Km,n) = Δ ， 偶图的边某某 χ′ = Δ n = 2k + 1 且边数 m > kΔ ，则 χ′ = Δ + 1 奇阶 χ 正则简单图，则 χ′ = Δ + 1 n为奇数，χ′ (Kn) = (n − 1) + 1 = n，χ′ (Cn) = 2 + 1 = 3 n为偶数，χ′ (Kn) = n − 1，χ′ (Cn) = 2 完全图和奇圈的 χ = Δ + 1 彼得森图的点色数为 3 ，边某某为 4 n 个点的树，则 Pk(G) = k(k − 1)n−1 h(G, x) = ∏it=1 h (Hi , x) . 同构的图有相同的色多项式，但其逆不真 1 1 图的基本概念 1.1 图的基本定义 3 个顶点的非同构的所有简单图有 4 个，4 个顶点的非同构的所有简单图有 11 个． Theorem 1. 若 n 阶图 G 是自补的 (即 G ∼= G)，则 n = 0, 1(mod4). 例：存在 18 阶自补图（错误，因为 18 除以 4 的余数是 2） k 正则图: 每个点的度均为 k 的简单图 (1) 在任何图中，奇点个数为偶数． (2) 正则图的阶数和度数不同时为奇数． Theorem 2 (握手定理). 对任意的有 m 条边的图 G = (V, E)，有 ∑ d(v) = 2m. v∈V De?nition 1. 一个图 G 的各个点的度 d1, d2, · · · , dn 构成的非负整数组 (d1, d2, · · · , dn) 称为 G 的度序列． Theorem 3. 非负整数组 (d1, d2, · · · , dn) 是图的度序列的充分必要条件是：∑ di 为偶数． De?nition 2. 对于一个非负整数组 (d1, d2, · · · , dn)，若存在一个简单图 G，以它为度序列，则 称这个数组是可图的．可图的序列简称为可图序列或图序列． Example 1. 试判断非负整数组 I = (5, 5, 3, 3, 2, 2, 2) 是否可图? Solution. 7 阶图，最大度为 5，而且度数之和为偶数，根据定理可得下列非负整数组 Π1 = ( 4, 2, 2, 1, 1, 2) Π1 = ( 4, 2, 2, 2, 1, 1) Π2 = ( 1, 1, 1, 0, 1) 显然 Π2 是可图序列，因此 Π = (5, 5, 3, 3, 2, 2, 2) 是可图的． Theorem 4 (以前考过证明). 一个简单图 G 的 n 个点的度不能互不相同． Solution. 因为图 G 为简单图，所以 "(G) ≤ n − 1. • 情形 1：若 G 没有孤立点，则 1 ≤ d(v) ≤ n − 1, ∀v ∈ V (G) 因为顶点个数为 n，所以必有两个顶点度数相同． 2 • 情形 2：若 G 仅有一个孤立点，设 G1 表示 G 去掉孤立点后的部分，则 1 ≤ d(v) ≤ n − 2, ∀v ∈ V (G1) 同理，在 G1 中必有两顶点度数相同． • 情形 3：若 G 有两个以上的孤立点，则定理显然成立． De?nition 3. 设 n 阶图 G 的各点的度取 s 点有 bi 个 ∑ ( bi = n)，则称 (b1, b2, · · · , bs) 个不同的非负整数 为 G 的频序列． d1, d2, · · · , ds．又设度为 di 的 Theorem 5 (以前考过证明). 一个 n 阶图 G 和它的补图有相同的频序列． 证明. 由补图的定义知，点 v 在图 G 及其补图中的度数之和为 n − 1，即 dG(v) + dG(v) = n − 1 因此，若 G 中有 bi 个度为 di 的点，则这 bi 个点在 G 的补图中的度变为 n − 1 − di ． 故 G 与其补图有相同的频序列． 1.2 图的运算 Theorem 6. 具有 m 条边的简单标号图的生成子图的个数为 2m． 差图 G1 − G2 ：在 G1 中去掉 G2 中的边组成的图． 对称差 G1△G2：G1△G2 = (G1 − G2) ∪ (G2 − G1). De?nition 4. 在不相交的 G1 和 G2 的并图 G1 + G2 中，把 G1 的每个顶点和 G2 的每个顶 点连接起来所得到的图称为 G1 和 G2 的联图，记为 G1 ∨ G2. 若 G1 的点数和边某某 n1, m1，G2 的点数和边某某 n2, m2，经过联、积、合成三种运算， 图的点数和边某某 (考过填空题，不止一次，考联图、积图的点数和边数是多少) 超立方体 Qn 是具有 2n 个顶点，n2n−1 条边的 n 正则二部图． 3 运算 点数 边数 G1 ∨ G2 G1 × G2 G1 [G2] G2 [G1] n1 + n2 n1n2 n1n2 n1n2 m1 + m2 + n1n2 n1m2 + n2m1 n1m2 + n22m1 n2m1 + n21m2 1.3 路和连通性 Theorem 7. 设图 G 为 n 阶图，若 G 中任意两个不相邻顶点 u 与 v 满足 d(u) + d(v) ≥ n − 1， 则 G 是连通图． Theorem 8 (偶图判定定理). 一个图是偶图当且当它不包含奇圈． 1.4 最短路及其算法 (填空题) Example 2. 如图所示，求点 a 到点 b 的最短距离．(以前考过大题，2005 年) Solution. 红色表示依次选取的标号 1. A1 = {a}, t(a) = 0, T1 = ∅ 2. b(11) = v3 3. m1 = 1, a2 = v3, t (v3) = t(a) + l (av3) = 1(最小), T2 = {av3} 4. m2 = 1, a3 = v1, t (v1) = t(a) + l (av1) = 2(最小), T3 = {av3, av1} 5. A3 = {a, v3, v1} , b(13) = v2, b(23) = v2, b(33) = v4 6. m3 = 3, a4 = v4, t (v4) = t (v1) + l (v1v4) = 3(最小), T4 = {av3, av1, v1v4} 7. A4 = {a, v3, v1, v4} , b(14) = v2, b(24) = v2, b(34) = v2, b(44) = v5 8. m4 = 4, a5 = v5, t (v5) = t (v4) + l (v4v5) = 6(最小), T5 = {av3, av1, v1v4, v4v5} 9. A5 = {a, v3, v1, v4, v5} , b1(5) = v2, b2(5) = v2, b3(5) = v2, b4(5) = v2, b5(5) = v2 10. m5 = 4, a6 = v2, t (v2) = t (v4) + l (v4v2) = 7(最小), T6 = {av3, av1, v1v4, v4v5, v4v2} 11. A6 = {a, v3, v1, v4, v5, v2} , b(26) = v6, b(46) = b, b(56) = v6, b(66) = v6 12. m6 = 6, a7 = v6, t (v6) = t (v2) + l (v2v6) = 9(最小), T7 = {av3, av1, v1v4, v4v5, v4v2, v2v6} 4 13. A7 = {a, v3, v1, v4, v5, v2, v6} , b4(7) = b, b(57) = b, b(77) = b 14. m7 = 7, a8 = b, t(b) = t (v6) + l (v6b) = 11(最小), T8 = {av3, av1, v1v4, v4v5, v4v2, v2v6, v6b} 于是知 a 与 b 的距离 d(a, b) = t(b) = 11，最短路为 a → v1 → v4 → v2 → v6 → b． 1.5 图的代数表示及特征 De?nition 5 (邻接矩阵). G 的邻接矩阵是一个 n × n 矩阵 A(G) = [aij]，其中若 vi 邻接 vj， 则 aij =1；否则 aij = 0． 注：若 aij 取为连接 vi 与 vj 的边的数目，则称 A 为推广的邻接矩阵． Theorem 9 (以前考过填空题). 令 G 是一个有推广邻接矩阵 A 的 p 阶标定图，则 An 的 i 行 j 列元素 a(ijn) 等于由 vi 到 vj 的长度为 n 的通道的数目． 推论：A2 的元素 a(ii2) 是 vi 的度数，A3 的元素 a(ii3) 是含 vi 的三角形的数目的两倍． De?nition 6 (关联矩阵). 关联矩阵 B(G) = [bij] 是一个 n × m 矩阵，当点 vi 与边 ej 关联 时 bij = 1，否则 bij = 0． Example 3. vi 到 vj 长度为 k 的通道的数目是 a(ijk). Example 4. 给你一个 A2，长度为 2 的途径有 ∑ i,j a(ij2). Example 5. 给你一个 A2，问 A 有多少条边，结果：主对角线元素之和除以 2. 设简单图 G 的邻接矩阵为 A，且 31120 A2 = 1 1 2 2 1 1 1 3 0 1 0 2 1 2 0 01202 则图 G 的边某某 6（主对角线元素除以 2） 矩阵 A 的所有特征值的平方和等于该图边数的 2 倍． ( ) Spec (Kn) = −1 n − 1 n−1 1 完全图 Kn 的特征值有 −1(n − 1 重) 和 n − 1(1 重)，所以 Kn 的最大特征值为 n − 1(考 过填空题)． 5 1.6 极图 完全 l 部图 Kn1,n2,··· ,nl 的点数：∑li=1 ni，边数 ∑ 1≤i 2n − 2 所以，m > n − 1，与 G 是树矛盾！ Theorem 15. 设 G 是具有 n 个点 m 条边的图，则下列命题等价： 1. G 是树． 2. G 无环且任意两个不同点之间存在唯一的路． 3. G 连通，删去任一边便不连通． 4. G 连通，且 n = m + 1． 5. G 无圈，且 n = m + 1． 6. G 无圈，添加任何一条边可得唯一的圈． Example 9. 设 T 为具有 12 条边的树，其顶点度的取值为 1, 2, 5．如果 T 恰有 3 个度为 2 的顶点，那么 T 有多少片树叶? Solution. 设 T 有 x 片树叶．根据树的点数与边数的关系知，由握手定理 1 × x + 2 × 3 + 5 × (13 − 3 − x) = 2 × 12 得 x = 8，即 T 有 8 片树叶． Example 10. 设树 T 中度数为 i 的顶点的个数为 ni(1 ≤ i ≤ k)，则 ∑k 1 ini = 2(∑k1 ni − 1). n1 = 2 + n3 + 2n4 + · · · + (k − 2)nk. 2.2 树的中心和形心 (考过填空写中心点) 离 v 最远的点的距离称为顶点 v 的离心率，最小的离心率称为半径，等于半径的点称为 中心点． 图 1: 半径是 4，中心点是 u 树 T 在点 u 处的一个分枝是指包含 u 作为一个叶子点的极大子树，树 T 在点 u 的分枝 中边的最大数目称为点 u 的权，树 T 中权值最小的点称为它的一个形心点． 7 2.3 生成树 图 2: 权值为 4 的顶点为该树的形心． 图 3: 收缩边 e1, e2, e3, e4, e5. Theorem 16 (Cayley 定理，考过证明). 若 e 是图 G 的边，则 τ (G) = τ (G − e) + τ (G · e) 证明. 由于 G 的每一颗不包含 e 的生成树也是 G − e 的生成树，所以 τ (G − e) 就是 G 的不 包含 e 的生成树的个数，τ (G · e) 就是 G 的包含 e 的生成树的个数． 图 4: τ (G) = 4 + 4 = 8. Theorem 17 (考过填空题). τ (Kn) = nn−2, τ (km,n) = nm−1mn−1.K5 = 125, K3,3 = 81. 2.4 最小生成树 (填空题) 图 5: W ( 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 Pk(G) = [k]2 + 4[k]3 + 4[k]4 + [k]5 Example 69. 求下图 G 的色多项式 Pk(G). 并求出点色数． Solution. 图 G 的补图 G 为 G 具有两个连通分支，分别记为 G1 和 G2 G1 的伴随多项式为 h1 = x + x2 56 G2 的伴随多项式为 h2 = 2x2 + 4x3 + x4 所以 G 的伴随多项式为 h = h1 × h2 = 2x3 + 6x4 + 5x5 + x6 因此 G 的色多项式为 Pk(G) = 2[k]3 + 6[k]4 + 5[k]5 + [k]6，其中 [k]i = k(k − 1) · · · (k − i + 1)．整理得 Pk(G) = k(k − 1)(k − 2)2 (k2 − 5k + ) 8 = k6 − 10k5 + 41k4 − 84k3 + 84k2 − 32k 因为图 G 中包含三角形，所以 χ(G) ≥ 3． 用 3 种颜色可以给出图 G 的一种正常点着色，如图： 所以 χ(G) = 3． 57 [文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]
以上为《《图论及其应用》复习》的无排版文字预览，完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。
图片预览
