第一章习题 1.对任何简单图G,(1)证明:E(G)≤ 2:(2)(G) U(U-1) 2当且仅当G≡K, 2.证明:(1)E(Kn)=m;(2)若G是完全二部图,则E(G)≤0 3.图G有21条边,12个3度顶点,其余顶点的度均为2,求图G的阶数 4.证明:任何简单图必有至少两个顶点具有相等的度。 5.设G是简单图,求G的所有不同的生成子图的个数(包括G本身和空图)。 6.证明:任何图中,奇度顶点的个数总是偶数(包括0)。并由此证明:在任一次聚会上握过奇数 次手的人必为偶数个。 7.证明或反证:如果u和γ是图G中仅有的具有奇数度的顶点,则G包含一条u,v路 8.证明:若U≥4且E=v+1,则存在v∈(G)使得d(v)≥3。由此证明:n个球队比赛(n≥4) 已赛完n+1场,则必定有一个球队已参加过至少3场比赛 9.在一个运动联盟中,将所有运动队组织成两个赛区,每个赛区有13个队,能否恰当安排比赛使 得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛? 10.在平面上有n个点S={x,x2,…xn},其中任两个点之间的距离至少是1。证明在这n个点中 距离为1的点对数不超过3n。 11.某次会议有n人参加,其中有些人互相认识,但每两个互相认识的人,都没有共同的熟人,每 两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人 12.在一个化学实验室里,有n个药箱,其中每两个不同的药箱恰有一种相同的化学品,而且每种 化学品恰好在两个药箱中出现,问:(1)每个药箱有几种化学品?(2)这n个药箱中共有几种 不同的化学品? 13.在一次舞会中,A、B两国留学生各n(m>2)人,A国每个学生都与B国一些(不是所有)学生跳 过舞,B国每个学生至少与A国一个学生跳过舞。证明一定可以找到A国两个学生a1,a2及B 国两个学生b1,b2,使得a1和b,a2和b2跳过舞,而a1和b2,a2和b没有跳过舞。 14.证明:d≤二≤Δ,(其中二称为顶点平均度)。 15.令G是至少有两个顶点的图。证明或反证:(1)删除一个度为△(G)的顶点不会增加顶点的平均 度;(2)删除一个度为(G)的顶点不会减小顶点的平均度 16令G是一个顶点平均度为a=2的无圈图。(1)证明:G-x的顶点平均度至少为a当且仅当 d(x)≤。(2)利用(1)的结果给出一个算法来证明:如果a>0,则G有一个最小度大于的 子图
第一章习题 1. 对任何简单图 G，(1) 证明： ( 1) ( ) 2 G υ υ ε − ≤ ；(2) ( 1) ( ) 2 G υ υ ε − = 当且仅当G K≅ ν 。 2. 证明：(1) , ( ) K mn m n ε = ；(2) 若 G 是完全二部图，则 2 ( ) 4 G υ ε ≤ 。 3. 图 G 有 21 条边，12 个 3 度顶点，其余顶点的度均为 2，求图 G 的阶数。 4. 证明：任何简单图必有至少两个顶点具有相等的度。 5. 设 G 是简单图，求 G 的所有不同的生成子图的个数（包括 G 本身和空图）。 6. 证明：任何图中，奇度顶点的个数总是偶数（包括 0）。并由此证明：在任一次聚会上握过奇数 次手的人必为偶数个。 7. 证明或反证：如果 u 和 v 是图 G 中仅有的具有奇数度的顶点，则 G 包含一条 u, v 路。 8. 证明：若υ ≥ 4 且ε =ν + 1，则存在v ∈V (G) 使得d(v) ≥ 3 。由此证明：n 个球队比赛（ n ≥ 4 ）， 已赛完 n+1 场，则必定有一个球队已参加过至少 3 场比赛。 9. 在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有 13 个队，能否恰当安排比赛使 得每个队在其所在赛区中进行 9 场比赛而与另一个赛区中的运动队进行 4 场比赛？ 10. 在平面上有 n 个点 1 2 {, , , }n S xx x = ⋅⋅⋅ ，其中任两个点之间的距离至少是 1。证明在这 n 个点中， 距离为 1 的点对数不超过 3n。 11. 某次会议有 n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每 两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人。 12. 在一个化学实验室里，有 n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种 化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这 n 个药箱中共有几种 不同的化学品？ 13. 在一次舞会中，A、B 两国留学生各 n n( 2) > 人，A 国每个学生都与 B 国一些(不是所有)学生跳 过舞，B 国每个学生至少与 A 国一个学生跳过舞。证明一定可以找到 A 国两个学生 1 2 a a, 及 B 国两个学生 1 2 b b, ，使得 1 a 和 1 2 b a , 和 2 b 跳过舞，而 1 a 和 2 2 b a , 和 1 b 没有跳过舞。 14. 证明： 2ε δ υ ≤ ≤Δ ，（其中 2ε υ 称为顶点平均度）。 15. 令 G 是至少有两个顶点的图。证明或反证：(1) 删除一个度为 Δ( ) G 的顶点不会增加顶点的平均 度；(2) 删除一个度为δ ( ) G 的顶点不会减小顶点的平均度。 16. 令 G 是一个顶点平均度为 2 a ε υ = 的无圈图。(1) 证明：G x − 的顶点平均度至少为 a 当且仅当 ( ) 2 a d x ≤ 。(2) 利用(1)的结果给出一个算法来证明：如果 a > 0 ，则 G 有一个最小度大于 2 a 的 子图
17.如果U≥2,Ev时,图中有圈。(b)E≥v+4时,图中有两个无公共边的圈。 27.证明:若G是δ(G)≥的简单图,则G是连通图。( 28.证明:(a)若e∈E(G),则o(G)≤o(G-e)≤(G)+1;(o(G)表示图G的连连同分支数)。 (b)若v∈(G),则o(G)≤o(G-v)≤O(G)+1未必成立,试举反例。 29.证明:若G是连通图,且每顶皆偶次,则o(G-v)≤-d(v)。 30.证明或反证:如果G是一个n顶点简单图,且其最大度是 2最小度是/ 2|-1,则G是连 通的 31.在一电路中,A,B两点间连接着一电阻,问至少要多少电阻,怎样连接,才能使得任意损坏9 个电阻时,A点与B点的电路仍连通且不短路? 32.证明G三H当且仅当G≡H。 33.证明:如果图G不连通,则其补图G必连通 34.如果图G满足G≡G,则称G是自补图。证明:若阶图G是自补图,则U=0,1(mod4)。 35.一个非连通简单图的补图一定是连通图吗?说明理由。 36.证明从一个8×8的方格棋盘中去掉对角的两个小方格后,不能被1×2和2×1的矩形覆盖 37.令G是一个4顶点图,删除其中的一个点后得到的子图系列如下,试确定G
17. 如果υ ≥ ν 时，图中有圈。 (b) ε ≥ + ν 4 时，图中有两个无公共边的圈。 27. 证明：若 G 是 1 ( ) 2 G υ δ − ≥ 的简单图，则 G 是连通图。（ 28. 证明：(a) 若e EG ∈ ( ) ，则ω() ( ) ()1 G Ge G ≤ −≤ + ω ω ；（ω( ) G 表示图 G 的连连同分支数）。 (b) 若v VG ∈ ( ) ，则ω() ( ) ()1 G Gv G ≤ −≤ + ω ω 未必成立，试举反例。 29. 证明：若 G 是连通图，且每顶皆偶次，则 1 ( ) () 2 ω G v dv − ≤ 。 30. 证明或反证：如果 G 是一个 n 顶点简单图，且其最大度是 2 ⎡n ⎤ ⎢ ⎥ ⎢ ⎥ 、最小度是 1 2 ⎡ ⎤ n − ⎢ ⎥ ⎢ ⎥ ，则 G 是连 通的。 31. 在一电路中，A，B 两点间连接着一电阻，问至少要多少电阻，怎样连接，才能使得任意损坏 9 个电阻时，A 点与 B 点的电路仍连通且不短路？ 32. 证明G H≅ 当且仅当G H≅ 。 33. 证明：如果图 G 不连通，则其补图G 必连通。 34. 如果图 G 满足G G≅ ，则称 G 是自补图。证明：若υ 阶图 G 是自补图，则υ = 01 4 , (mod ) 。 35. 一个非连通简单图的补图一定是连通图吗？说明理由。 36. 证明 从一个8 8 × 的方格棋盘中去掉对角的两个小方格后，不能被1 2 × 和 2 1× 的矩形覆盖。 37. 令 G 是一个 4 顶点图，删除其中的一个点后得到的子图系列如下，试确定 G
38下面两图是否同构? 39.讨论下列三个图的同构性 40.证明: Peterson图与下列图同构 41.已知n阶简单图G有m条边,各顶点的度数均为3,(1)若m=3n-6,证明G在同构意义下 唯一,并求m,n;(2)若n=6,证明G在同构意义下不唯一。 42若图G有n个顶点,n-1条边,则G一定是树吗?说明理由 43证明非平凡树中最长路的起点和终点都是叶子(1度点)。 44证明恰有两个叶子的树必是路。 45证明:若G是树且Δ≥k,则G至少有k个1度顶点 46证明每个树都是二部图。 47设n表示树T中度为i的顶点的个数。(1)证明对非平凡树T的叶子数n1有下面公式成立 2+n2+2n+3n+…=2+∑(-2)
38. 下面两图是否同构？ 39. 讨论下列三个图的同构性 40. 证明：Peterson 图与下列图同构 41. 已知 n 阶简单图 G 有 m 条边，各顶点的度数均为 3，(1) 若m n = 3 6 − ，证明 G 在同构意义下 唯一，并求 m n , ；(2) 若 n = 6 ，证明 G 在同构意义下不唯一。 42 若图 G 有 n 个顶点， n −1条边，则 G 一定是树吗？说明理由。 43 证明非平凡树中最长路的起点和终点都是叶子（1 度点）。 44 证明恰有两个叶子的树必是路。 45 证明：若 G 是树且 Δ ≥ k ，则 G 至少有 k 个 1 度顶点。 46 证明每个树都是二部图。 47 设 i n 表示树 T 中度为 i 的顶点的个数。(1) 证明对非平凡树 T 的叶子数 1 n 有下面公式成立： 1 345 3 2 2 3 2 ( 2) i i n nnn in ∞ = = + + + +⋅⋅⋅ = + − ∑ . d a c b h g e f v1 v2 v8 v7 v6 v5 v4 v3 u v t s z y x w
(2)证明∑m只依赖于树T的顶点数。 48不含圈的图称为森林( forest),证明: (1)G是森林当且仅当E=v-w;(2)无孤立点的森林至少有2w个1度顶点。 这里w表示G的连通分支数,孤立点指零度顶点。 49证明:具有m条边的任意n顶点图至少有m-n+1个圈 50令T是一棵n顶点数,对于2≤i≤k的每个i值,树中有一个度为i的顶点;其余的n-k+1个 顶点都是叶子。确定n并表示成k的形式 51令T是一棵非平凡树,其中所有与叶子相邻的顶点的度至少为3,证明:T中某一对叶子有公共 的相邻顶点 52令G是一个连通的n顶点图,证明:G恰有一个圈当且仅当G恰有n条边 53令T是一棵树,证明:T的顶点全为奇度点当且仅当对ve∈E(T),T-e的两个连通分支都具 有奇数的阶 4令T是一棵阶为偶数的树,证明:T恰有一个生成子图使得其中每个顶点的度均为奇数。 55证明:若T是一个具有k条边的树,G是一个简单图且o(G)≥k,则G含有与T同构的子图。 56令G是一棵树,其中2k个顶点具有奇数度,证明:G可分解成k条路。 57对n≥4,令G是满足(G)≥2n-3的简单n点图,证明:G有两个等长的圈 58令u是连通图G的一个顶点,证明不可能选出从u到其他各顶点的最短路使得这些路的并是 棵树。 59令T、T是连通图G的两棵生成树,对于e∈E(T)-E(T"),证明存在一条边e’∈E(T)-E(T), 使得T+e-e和T-e+e’都是G的生成树。 60设G是一个加权的连通图并且其各边上的权值互不相同。不使用 Kruskal算法,证明:G只有 棵权值最小的生成树(提示:利用上题结论)。 61为n阶完全图Kn的所有边分配整数权值。假设一个圈的权值是该圈上所有边的权值之和。证明: 所有圈的权值均为偶数当且仅当具有奇数权值的那些边构成的子图是一个生成二部图。(提示 对于具有偶数权值的边构成的子图,其任意连通分量都是一个完全图)。 62求下图中从l到其余各点的最短路。 63修改 Kruskal算法用以
（2）证明 1 i i in ∞ = ∑ 只依赖于树 T 的顶点数。 48 不含圈的图称为森林（forest），证明： （1）G 是森林当且仅当ε =ν − w ；（2）无孤立点的森林至少有 2w 个 1 度顶点。 这里 w 表示 G 的连通分支数，孤立点指零度顶点。 49 证明：具有 m 条边的任意 n 顶点图至少有 m n − +1个圈。 50 令 T 是一棵 n 顶点数，对于 2 ≤ ≤i k 的每个 i 值，树中有一个度为 i 的顶点；其余的 n k − +1个 顶点都是叶子。确定 n 并表示成 k 的形式。 51 令 T 是一棵非平凡树，其中所有与叶子相邻的顶点的度至少为 3，证明：T 中某一对叶子有公共 的相邻顶点。 52 令 G 是一个连通的 n 顶点图，证明：G 恰有一个圈当且仅当 G 恰有 n 条边。 53 令 T 是一棵树，证明：T 的顶点全为奇度点当且仅当对∀e ET ∈ ( ) ，T e − 的两个连通分支都具 有奇数的阶。 54 令 T 是一棵阶为偶数的树，证明：T 恰有一个生成子图使得其中每个顶点的度均为奇数。 55 证明：若 T 是一个具有 k 条边的树，G 是一个简单图且δ ( ) G k ≥ ，则 G 含有与 T 同构的子图。 56 令 G 是一棵树，其中 2k 个顶点具有奇数度，证明：G 可分解成 k 条路。 57 对 n ≥ 4 ，令 G 是满足ε () 2 3 G n ≥ − 的简单 n 点图，证明：G 有两个等长的圈。 58 令 u 是连通图 G 的一个顶点，证明不可能选出从 u 到其他各顶点的最短路使得这些路的并是一 棵树。 59 令 T、T′ 是连通图 G 的两棵生成树，对于e ET ET ∈ () ( ) − ′ ，证明存在一条边e ET ET ′ ′ ∈ − ( ) () ， 使得T ee ′ ′ + − 和Tee − + ′ 都是 G 的生成树。 60 设 G 是一个加权的连通图并且其各边上的权值互不相同。不使用 Kruskal 算法，证明：G 只有一 棵权值最小的生成树（提示：利用上题结论）。 61 为 n 阶完全图 Kn 的所有边分配整数权值。假设一个圈的权值是该圈上所有边的权值之和。证明： 所有圈的权值均为偶数当且仅当具有奇数权值的那些边构成的子图是一个生成二部图。（提示： 对于具有偶数权值的边构成的子图，其任意连通分量都是一个完全图）。 62 求下图中从 u0 到其余各点的最短路。 63 修改 Kruskal 算法用以： u0 u1 u2 u3 u4 u5 u6 u7 1 2 2 2 3 3 1 3 4 4 4 5 6 6 7 7 8
(1)求赋杈连通图中的最大权生成树;(2)求不连通赋权图中的最小权生成森林 证明:直径为k,围长为2k+1的图是正则图 65证明:对任一简单连通图G有radG≤ diam≤2radG。 66证明:对任意树T,若只有一个中心,则 diam=2radT,若有两个中心,则 diam=2radT-1 67设G是一个简单图。证明:若damG≥3,则 diag≤3:若radG≥3,则radG≤2 68证明:若G是自补图,则 diam≤3。 69证明:任一非平凡自补图的直径为2或3。 70设G是直径为2的简单图,且△(G)=v-2,则E≥2v-4。 71 Peterson图是否二部图?试求其围长、半径、直径 72如果n≥4,证明直径为2且最大度为n2的n顶点简单图的最小边数是2n-4。 73令x和y是图G中顶点ν的两个不同的邻点,证明:如果G是一棵树,则离心率 2e(v)≤e(x)+e(y) 74证明树T的中心是一个顶点当且仅当damT=2radT。 75证明:一棵树要么只有一个重心,要么有两个相邻的重心。(提示:对相邻顶点u和ν,考虑 g(u)-g(v)) 76令G是一棵树,它有n个顶点、k个叶子且最大度为k。(1)证明G是k条具有同一个公共端点 的路的并。(2)确定damG的可能的最大值和最小值。 77证明:具有n+1条边的任意n顶点图的围长最大值为 3 78证明:在所有直径为k但不是树的图中,2k+1是围长的最大值(提示:证明若G有一个长至 少为2k+2的圈,则G必有长度更小的圈)。 79已知图G如下 (1)求G的邻接矩阵A和关联矩阵M (2)求A2,A3,A4,说明从顶点b到d长度为1,2,3,4的路分别有几条
(1) 求赋权连通图中的最大权生成树；（2）求不连通赋权图中的最小权生成森林。 64 证明：直径为 k，围长为2 1 k + 的图是正则图。 65 证明： 对任一简单连通图 G 有 rad diam 2rad G GG ≤ ≤ 。 66 证明：对任意树 T，若只有一个中心，则diam 2rad T T = ，若有两个中心，则diam 2rad 1 T T = − . 67 设 G 是一个简单图。证明：若diam 3 G ≥ ，则diam 3 G ≤ ；若 rad 3 G ≥ ，则 rad 2 G ≤ 。 68 证明： 若 G 是自补图，则diam 3 G ≤ 。 69 证明：任一非平凡自补图的直径为 2 或 3。 70 设 G 是直径为 2 的简单图，且 Δ(G) =ν − 2 ，则ε ≥ 2ν − 4 。 71 Peterson 图是否二部图？试求其围长、半径、直径。 72 如果 n ≥ 4 ，证明直径为 2 且最大度为 n-2 的 n-顶点简单图的最小边数是 2n-4。 73 令 x 和 y 是图 G 中顶点 v 的两个不同的邻点，证明：如果 G 是一棵树，则离心率 2() () ( ) ev ex ey ≤ + 。 74 证明树 T 的中心是一个顶点当且仅当diam 2rad T T = 。 75 证明：一棵树要么只有一个重心，要么有两个相邻的重心。（提示：对相邻顶点 u 和 v，考虑 gu gv () () − ）。 76 令 G 是一棵树，它有 n 个顶点、k 个叶子且最大度为 k。(1) 证明 G 是 k 条具有同一个公共端点 的路的并。(2) 确定 diam G 的可能的最大值和最小值。 77 证明：具有 n+1 条边的任意 n 顶点图的围长最大值为 2 2 3 ⎢ n + ⎥ ⎢ ⎥ ⎣ ⎦ 。 78 证明：在所有直径为 k 但不是树的图中， 2 1 k + 是围长的最大值（提示：证明若 G 有一个长至 少为 2 2 k + 的圈，则 G 必有长度更小的圈）。 79 已知图 G 如下： （1）求 G 的邻接矩阵 A 和关联矩阵 M； （2）求 234 AAA , , ，说明从顶点 b 到 d 长度为 1，2，3，4 的路分别有几条。 d c b a
思考题1.网络会议 某种网络会议系统允许三个地点同时进行网络会议。下图描述的是一个传输网络, 其中圆圈代表客户所在的城市,每条线段两端的客户都可以直接通话。为了让三地同时 通话,公司需要激活一些直接连接,使得三个客户端连通。由于激活不同的直接连接的 费用不同,公司希望你为它找一个最省钱的激活方式 例如下图中,为了连接客户1,4,6,最好的方式是激活加粗的直接连接,总费用 是27 思考题2.公平会面 两位外交官处在不同的城市A和B,他们打算请你选择一座城市X作为他们会面的 地点,并分别为他们制定详细的到达路线。为公平起见,两位外交官行走的路线总长要 样,任何一位外交官不能经过同一座城市两次,并且除了会面地点外,两位外交官不 会到达过同一座城市。在这个基础上,你应该使得路线长度最短。假设这样的会面地点 和到达路线一定存在
思考题 1. 网络会议 某种网络会议系统允许三个地点同时进行网络会议。下图描述的是一个传输网络， 其中圆圈代表客户所在的城市，每条线段两端的客户都可以直接通话。为了让三地同时 通话，公司需要激活一些直接连接，使得三个客户端连通。由于激活不同的直接连接的 费用不同，公司希望你为它找一个最省钱的激活方式。 例如下图中，为了连接客户 1，4，6，最好的方式是激活加粗的直接连接，总费用 是 27. 思考题 2. 公平会面 两位外交官处在不同的城市 A 和 B，他们打算请你选择一座城市 X 作为他们会面的 地点，并分别为他们制定详细的到达路线。为公平起见，两位外交官行走的路线总长要 一样，任何一位外交官不能经过同一座城市两次，并且除了会面地点外，两位外交官不 会到达过同一座城市。在这个基础上，你应该使得路线长度最短。假设这样的会面地点 和到达路线一定存在。 7 8 4 5 6 2 3 1 6 5 1 7 2 3 9 8 4 3 6 20