(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