2015电子科技大学-图论期末考试复习题VIP

2015 电子科技大学 图论考试复习题 关于图论中的图，以下叙述不正确的是 A图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B图论中的图，画边时长短曲直无所谓。 C图中的边表示研究对象，点表示研究对象之间的特定关系。 D图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。 一个图中最长的边一定不包含在最优生成树内。 下面哪个图形不与完全二分图 K3,3同构？ ABCD 有 10 条边的 5 顶单图必与 K5同构。 完全二分图 Km,n的边数是 AmBnCmnDmn 无向完全图 Kn的边数为 AnBn2Cn(n1)Dn(n1)/2 若一个无向图有 5 个顶点，如果它的补图是连通图，那么这个无向图最多有条边。 对于两个图， 如果顶点数目相等， 边数相等， 次数相等的顶点数目也相等， 则这两个图同构。 有 15 个顶的单图的边数最多是 A105B210C21D45 图 G 如右，则 dacbeb A是 G 中的一条道路 B是 G 中的一条道路但不是行迹 C是 G 中的一条行迹但不是轨道 D不是 G 的一条道路 图 G 如右，则 befcdef A是 G 的一个圈 B是 G 的一条道路但不是行迹 C是 G 的一条行迹但不是轨道 D是 G 的一条轨道但不是圈 图 G 如右图所示，则(G) A1B2 C7D8 下列图形中与其补图同构的是 ABCD 求下图中顶 u0到其余各顶点的最短轨长度。 u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=4，v2v4=2，v2v7=3，v3v5=3， v3v6=6，v4v5=5，v4v7=1，v5v6=4，v5v7=3，v6v7=6， 请画出6阶3正则图。 请画出 4 个顶，3 条边的所有非同构的无向简单图。 设图 G=V(G)，E(G)其中 V=a1, a2, a3, a4, a5，E(G)=(a1, a2)，(a2, a4)，(a3, a1)，(a4, a5)， (a5, a2)，试给出 G 的图形表示并画出其补图的图形。 一个图的生成子图必是唯一的。 不同构的有 2 条边，4 个顶的无向简单图的个数为 A1B2C3D4 画出 5 个具有 5 个结点 5 条边的非同构的无向连通简单图。 u0到 v1的最短轨长度为 6，u0到 v2的最短轨长度为 1，u0到 v3的最短轨长度为 4，u0到 v4 的最短轨长度为 2，u0到 v5的最短轨长度为 6，u0到 v6的最短轨长度为 9，u0到 v7的最短轨 长度为 3。 用 Dijkstra 算法求下图中从 v1点到其他任意一点的最短路。 v1v3 v1v2 v1v2v5 v1v3v4 v1v2v5v6 v1v2v5v6v7 设有城市 v1，v2，v3，v4，v5，v6，各城市之间的距离如下表。使用 Dijkstra 算法求城市 v1到 其他各城市的最短路径以及最短距离。要求说明求解过程（提示：应将城市之间的道路图看 作是无向图） 。 道路v1v2v1v3v2v3v2v4v2v5v3v5v4v5v4v6v5v6 距离142751326 解：下面的表格给出了求解 v1到其他各顶点之间的最短距离的 Dijkstra 算法执行过程： 步骤v1v2v3v4v5v6 01/(v1)4/(v1) /(v1)3/(v2)8/(v2)6/(v2) /(v2)8/(v2)4/(v3) 7/(v5)/(v3)10/(v5) /(v5)9/(v4) /(v4) 最后得到 v1到其他各城市的最短路径及最短距离为： v1到 v2的最短路径是：v1v2长度为 1 v1到 v3的最短路径是：v1v2v3长度为 3 v1到 v4的最短路径是：v1v2v3v5v4长度为 7 v1到 v5的最短路径是：v1v2v3v5长度为 4 v1到 v6的最短路径是：v1v2v3v5v4v6长度为 9 求下图中顶 v1到 v11的最短轨及最短距离。 L 100 个顶点的星的最大顶点次数是。 做一个图 G，使其顶的次序列为(5,5,4,4,3,3,2,2,2)。 下列哪个序列不可能构成一个图的顶点次数序列？ A(2,2,2,2,2)B(3,3,3,3)C(1,2,3,4,5)D(2,2,3,4,5) 已知图 G 中有 1 个 1 度结点，2 个 2 度结点，3 个 3 度结点，4 个 4 度结点，则 G 的边数 是 任取 n 个人组成的人群，n2，证明至少有两位，他们在人群中的朋友一样多。 证明：把 n 个人看做 n 个点，如果两个人是朋友，则在这两个点之间连一条边，这样可以得 到一个含 n 个顶的单图。 显然顶的最大次数为 n1，如果这 n 个顶的次数不一样，则它们必为 0,1,2,n1，而次为 0 的顶与各顶都不相邻，因此不可能有顶的次为 n1，出现矛盾。因此 n 个顶的次数必至少有 两个是相等的。 所以至少有两位，他们在人群中的朋友一样多。 设 G 是一个含 n 个顶点的无向简单图，n 是大于等于 2 的奇数证明图 G 与它的补图 GC中 的奇数次顶点个数相等。 E(GC)是由完全图 Kn的边删去 E(G)所得到的所以对于任意结点 uV(G)，u 在 G 和 GC中 的次数之和等于 u 在 Kn中的次数由于 n 是大于等于 2 的奇数，从而 Kn的每个顶点都是偶 数度的 （n1(2)度） ， 于是若 uV(G)在G 中是奇数次顶点， 则它在 GC中也是奇数次顶点 故 图 G 与它的补图 GC的奇数次顶点个数相等。 具有 m 条边的树有几个顶点？ AmB1m-Cm1D 2 m 完全二分图 Km,n的边数是： AmBnCm+nDmn 有 n 个顶的图中，圈的长度最大值为 A2nBnCn+1Dn1 含 5 个顶、3 条边的不同构的无向图有 A2 个B3 个C4 个D5 个 图 G 如右所示，与 G 同构的图是 AB CD v1，v2，v3，v4，v5，v6是 6 个城市，下面矩阵的（i，j）号元素是 vi到 vj的机票票价，试为 一个旅行者制作一张由 v1到各城去旅游的最便宜的航行路线图。 050402510 500152025 1501020 40201001025 252010055 102525550 轾 犏 犏 犏 犏 犏 犏 犏 犏 犏 犏 犏 臌 完全图 K4的生成树的数目为。 一棵树有 2 个 2 度顶点，1 个 3 度顶点，3 个 4 度顶点，则其 1 度顶点的个数是 A5B7C8D9 有 6 个顶的不同构的树共有棵。 设图 G 是有 6 个顶点的连通图，顶点的总度数为 18，则可从 G 中删去条边后使之变 成树。4 已知一棵无向树 T 中有 8 个顶点，4 度、3 度、2 度的顶点各一个，T 的树叶数为。 有 n（n1）个顶的树 T，下面说法不正确的是 AT 是二分图BT 是可平面图 CT 中存在完美匹配DT 中任意两点间有唯一轨道相连接 设 G 是有 n 个结点，m 条边的连通图，为了得到 G 的一棵生成树，必须从 G 中删去的边数 是 Amn+1BmnCm+n+1Dnm+1 无向简单图 G 是棵树，当且仅当 AG 连通且边数比顶点数少 1BG 连通且顶点数比边数少 1 CG 的边数比顶点数少 1DG 中没有圈 下面给出的集合中，哪一个是前缀码 A0，10，110，101111B01，001，000，1 Cb，c，aa，ab，abaD1，11，101，001，0011 给定一个序列集合1，01，10，11，001，000，若去掉其中的元素，则该序 列集合构成前缀码。 若一棵典型有序二元树有 2n1 个顶点，则它的树叶数是 AnB2nCn1D2 下面那种描述的单图不一定是树。 A无回路的连通图B有 n 个顶点，n1 条边的图 C每对顶点都有通路的图D连通但删去一条边则不连通的图 下列无向图一定是树的是 A连通图B无圈但添加一条边后有圈的图 C每对顶点间都有路的图D连通且 E(G)V(G)1 求生成树个数时，将一个树对应一个 Prufer 序列，如果树 T 的对应 Prufer 序列为(2,3,2,3)， 则标号为 2 的顶点的次数是 A1B2C3D4 右图是二分图。 一个有 13 个顶的简单图 G 中有 3 个顶的次数是 4，4 个顶的次数是 3，6 个顶的次数是 1， 则图 G 一定是树。 设树 T 中有 2 个 3 度顶点和 3 个 4 度顶点，其余的顶点都是树叶，则 T 中有片树叶。 10 若 T 是图 G 的生成树，则 AT 必唯一BG 不一定是连通图 CT 中必不含圈DG 中不含圈 若 G 是一个含 p 个顶点，q 条边的图，若 qp，则 G 中必有圈。 有 4 个连通片组成的 17 个顶的森林的边数为 A16B15C14D13 设 G 是一个满足|E(G)|V(G)|的图，则 G 中必有圈。 在下图中， 用 Kruskal 算法构造最小生成树， 写出边添加到生成树的边序列， 并画出生成树。 答： 求下图的最优树 T（不要求中间过程，只要求画出最小生成树, 并给出 T 的权和） 。 答： 权和为 17。 求下图的最小生成树，并给出权值(只给结果，不要过程) 答： 权和为 28。 求下图的最小生成树，并给出权值。 权和为 16。 假设用于通信的电文仅由 8 个字母 a, b, c, d, e, f, g, h 构成，它们在电文中出现的概率分 别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，试为这 8 个字母设计哈夫曼编码。 解：a, 1100；b, 00；c, 11110；d, 1110；e,10；f, 11111；g, 01；h,1101 画出带权 0,2，0.17，0.13，0.1，0.1，0.08，0.06，0.06， 0.07，0.03 的 Huffman 树。 画出带权 0.1，0.1，0.1，0.1，0.15，0.2，0.25 的 Huffman 树。 假定通信中出现的字母为 a, b, c, d, e, f, g, h，其出现的频率如下表。试画出这组字母（权） 的 Huffman 树，要求给出求解过程。 字母abcdefgh 频率25%20%15%15%10%5%5%5% 设 T 是树叶权为 1，2，3，4，5 的 Huffman 树，那么树 T 的带权路径长为。33 有 99 个顶点的典型有序二元树的叶子数是。 一个出城汽车队行驶时不得超车， 但每车都可以进入路过的一个胡同里去加油， 再在某时刻 退出胡同插队继续开行，共有 5 辆不同的汽车。则开出城的不同车队种数是。 行餐后姊妹去洗碗， 洗前已把 5 个不同花色的碗摞成一摞。 妹妹把姐姐洗过的碗每次拿一个 放入消毒柜，也摞成一摞。由于小妹贪玩，碗被放入消毒柜可能不及时，姐姐则把洗过的碗 摞在旁边，则小妹摞起的碗摞可能的种数是。 答：42 对一个括号序列进行检测，从左向右数到第 99 个括号时，记录了右括号个，因此得出 结论为坏括号序列。50 对一个好括号序列进行检测，从左向右至少数到第个括号时，会记录下 50 个右括号。 100 画出所有不同构的 5 顶点树。 以下说法错误的是 A. 同构的图具有相同的顶点数和边数B. 同胚的图边数相同，但顶点数不同 C. 如果一个图是可平面的，那么与它同构的图也是可平面的 D. 如果一个图是可平面的，那么与它同胚的图也是可平面的 如果一个 3正则简单平面图的每个面都有 3 条边，则这个图的边数是 A3B4C5D6 图 H 是下面平面图 G 的一个平面嵌入，则图 H 的面数是 A5B6C7D8 如果平面图 G 有 v 个顶点，e 条边和 f 个平面，则 Avef2Bevf2Cvef2Devf2 具有 6 个顶点，12 条边的连通简单平面图中，每个面的边数是 A2B3C4D5 设 G 为一个连通的平面图，G 有 5 个顶点和 9 条边，则 G 有个面。6 n(n3)阶极大平面图的面数等于。 2n4 n(n3)阶极大平面图的边数等于。 3n6 100 个顶点的极大连通平面图中最多有个面。196 100 个面的极大连通平面图中最多有个顶点。52 画出面数最多的 5 顶点连通平面图的平面嵌入，并指出它有几个面。 6 个面。 如果单图 G 是平面图，那么它一定有一个次数不超过 5 的顶。 不妨设 G 是连通的，否则考虑它的每一个连通分支。 设 G 有 n 个顶，m 条边，f 个面。因为 G 是单图，每个面至少有三条边，所以 3f2m。 如果每个顶的次数都不小于 6，那么有 6n2m。 由欧拉公式得 2nmfm/3m2m/30，矛盾。 所以至少一个顶次数不超过 5。 证明不存在 7 条棱的多面体。 若有 7 条棱的多面体，因为每个面上至少三条边，所以 2(G) 3(G)，(G)14/3，所以 (G)4。代入 Euler 公式得(G)5，但(G)4 的多面体是惟一的，它有四个顶，与(G) 5 矛盾。故无七棱多面体。 若简单平面图 G 的顶数不少于 11 个，则 GC不是平面图。 画出面数最多的 6 顶点连通二分平面图的平面嵌入，并指出它有几个面。 4 个面 完全图 K2n能够分解为_个边不相交的 1 因子之并。 n1 完全图 K2n+1能够分解为_个边不相交的 2 因子之并。 n 下列图中可 1 因子分解的是 ABCD 给 5 位同学各写好一封信的信笺， 又写好了给这 5 位同学的信封， 把信笺都插错了信封的方 法数为 A48B44C36D24 有 n 把钥匙和 n 把锁混在一起， 确定知道每把锁都能有一把钥匙打开， 锁匠想把它们一对对 的分开，那么有多少种分法是每对中的钥匙都无法打开锁的。 （1）给出求解上述问题的递归 公式，并证明之； （2）算出 n=6 时问题的解。 （1）设第 i 把钥匙为 xi，第 i 把锁为 yi，X=x1,x2, ,xn，Y=y1,y2, ,yn。把 xi和 yi视为顶 点，当且仅当 ij 时，xi和 yj相邻，得到二分图 G。图 G 是 n1 次正则的二分图，G 有完 备匹配。问题转化为求 G 的完备匹配个数 b(n)。 如果钥匙 x1错配给锁 y2时， （1）x2错配给 y1，则可能的 G 中的完备匹配之个数为 b(n2)。 （2）x2不错配给 y1，则可能的 G 中的完备匹配之个数为 b(n1)。 而 x1错配的可能有 n1 种。所以 b(n)=(n1)b(n1)+b(n2)。 （2）显然，b(1)=0，b(2)=1， 所以 b(3)=2，b(4)=9，b(5)=44，b(6)=265。 给 n 位同学各写好一封信的信笺， 又写好了给这 5 位同学的信封， 把信笺都插错了信封的方 法数设为 b(n)，则 b(n) Ab(n1)b(n2)B(n1)b(n1)b(n2) Cnb(n1)b(n2)D2(n1)b(n1)b(n2) 给 6 位同学各写好一封信的信笺， 又写好了给这 6 位同学的信封， 把信笺都插错了信封的方 法数为 A120B240C265D288 下列哪个图无完备匹配 Ak 次正则 2 分图BPetersen 图（单星妖怪） CK2nDK2,4 r=5,当 s=时，完全二部图 Kr,s才可能存在完美匹配。5 K10,10有种完美匹配。10 右图 G 的覆盖数(G) A2B3 C4D5 K3,5的覆盖数(K3,5) A2B3C4D5 某公司有 5 名工作人员 x1,x2,x3,x4,x5，他们每人承担 y1,y2,y3,y4,y5这 5 项工作中的一项， 每人对每项工作创造的价值用下边的矩阵表示，公司领导根据每个人的特长如何合理分工， 使得这 5 个工作人员对公司创造的总价值最大？ 答：最佳匹配是x1y4，x2y1，x3y3，x4y2，x5y5 用匈牙利算法求下图的最大匹配。 x1y1，x2y2，x3y5，x4y3，x5y4 用匈牙利算法求下图的最大匹配。 12345 1 2 3 4 5 35541 22022 24410 01100 12133 yyyyy x x x x x 轾 犏 犏 犏 犏 犏 犏 犏 犏 犏 臌 x1y2，x2y1，x3y3，x5y5 今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知 赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周 都只熟悉数学、物理两门课程。问能否安排他们都只上他们熟悉的一门课程，使得每门课程 都有人教（用图论方法求解） 。 解：用 x1,x2,x3,x4,x5表示赵、钱、孙、李、周五位教师，用 y1,y2,y3,y4,y5表示语文、数学、物 理、化学、英语五门课程。某位教师熟悉某门课程，则在两点之间连一条边，因此得到下面 的二分图。 取 S=x3,x4,x5，则 N(S)=y1,y2，故|N(S)|S|。 由 Hall 定理知，不存在把 x1,x2,x3,x4,x5皆许配的匹配， 因此不能安排他们都只上他们熟悉的一门课程，使得每门课程都有人 教。 对于下面的二分图，图中虚线给出了初始匹配 M=x1y1，x2y4，x3y2，x4y3，x6y5，从该初始 匹配开始，利用匈牙利算法求其最大匹配。要求写出求解过程。 （提示：虚线和实线都是该 二分图的边） 解：由不饱和点 x5出发构造增广路径 P：x5y2x3y1x1y3x4y6，构造新的匹配： M=x5y2，x3y1，x1y3，x4y6，x2y4，x6y5，M是一个最大匹配，如下图虚线所示。 从下图中给定的 M=x1y1，x3y5，x5y3开始，用匈牙利算法求下图中 的完备匹配。 取未被 M 许配的顶 x2，由 x2出发得可增广轨 x2y3x5y5x3y2， 构造新的匹配：M=x1y1，x2y3，x5y5，x3y2。 再取未被 M许配的顶 x4，由 x4出发得可增广轨 x4y3x2y2x3y5x5y4，构 造新的匹配：M=x1y1，x4y3，x2y2，x3y5，x5y4。 分派甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间 如下表，试确定总花费时间为最少的指派问题。 任务 人 ABCDE 甲127979 乙89666 丙71712149 丁15146610 戊4107109 用 x1,x2,x3,x4,x5表示甲、乙、丙、丁、戊五个人，y1,y2,y3,y4,y5表示 A、B、C、D、E 五项工 作，对应的权取 20工作时间，得权矩阵为 取正常初始顶标 l(yi)=0，l(x1)=13，l(x2)=14，l(x3)=13，l(x4)=14，l(x5)=16，构作 G1如图， 用匈牙利算法求得最大匹配 M=x1y2，x2y4，x3y5，x4y3，x5y1，这是个完备匹配，因此即为 最佳匹配。 因此甲完成 B 工作，乙完成 D 工作，丙完成 E 工作，丁完成 C 工作，戊完成 A 工作，总花 费时间最少为 7+6+7+6+4=30。 平面图的对偶图是连通图。 下图 G 是平面图。 设连通平面图 G 有 6 个面，8 个顶点，则 G条边。12 关于平面图 G 和其几何对偶图 G*的关系，下列说法中不正确的是 A平面图 G 的面数等于其对偶图的顶点数 B平面图 G 的边数等于其对偶图的边数 C平面图(G*)*G，其中 G*表示 G 的对偶图 D平面图的对偶图是连通平面图。 下列哪个图是极大平面图 A顶为 7，边数为 15 的单图BK5 CK3,3D正方体 把平面分为个区域，使任两个区域相邻，则的最大值为 A5B4C3D2 下列哪个图不是极大平面图 12345 1 2 3 4 5 813111311 1211 141414 1338611 56141410 1610131011 yyyyy x x x x x 轾 犏 犏 犏 犏 犏 犏 犏 犏 犏 臌 A正四面体B正六面体C正八面体D正二十面体 下面哪个图是平面图 AK5BK2,3CK6DK3,3 Kuratowsky 认为可作为判定图的可平面性依据的基本不可平面图之一是 AK3AK4AK5AK6 以下说法错误的是 A同构的图具有相同的顶点数和边数 B同胚的图边数相同，但顶点数不同 C如果一个图是可平面的，那么与它同构的图也是可平面的 D如果一个图是可平面的，那么与它同胚的图也是可平面的 下列图中哪个的对偶图是自身？ AK3BK4CK5DK6 15 阶圈 C15的顶色数是 A2B3C6D15 设 G 为 n 顶 m 条边的无向连通单图，下列命题为假的是 AG 一定有生成树Bm 一定大于 n CG 的边色数(G)(G)DG 的最大度(G)n1 完全图 K15的顶色数是 A2B3C6D15 完全图 G 的色多项式 P(G，t)是 At(t1)2Bt(t1)(t2)Ct3Dt(t1)(t) 图 G 的色多项式 P(G，t)是 t44t36t23t，则图 G 的边数是 A3B4C5D6 图 G 的色多项式 P(G，t)是 t44t36t23t，则图 G 的顶数是 A3B4C5D6 完全图 K15的边色数是 A2B3C6D15 15 阶圈 C15的边色数是 A2B3C6D15 完全图 K8的边色数是 A2B3C7D8 求下图 G 的色多项式 P(G，k) 答：P(G，k)=k(k1)(k2)(k3)(k4)+3k(k1)(k2)(k3)+k(k1)(k2) =k57k4+18k320k2+8k 求下图 G 的色多项式 P(G，k) 答：P(G，k)=k(k1)(k2)(k3)(k4)+3k(k1)(k2)(k3)+2k(k1)(k2) =k57k4+20k326k2+10k 求下图 G 的色多项式 P(G，k) 答：P(G，k)=k(k1)(k2)(k3)(k4)+2k(k1)(k2)(k3)+k(k1)(k2) =k58k4+24k331k2+14k 求下图 G 的色多项式 P(G，k) 答：P(G，k)=k(k1)(k2)(k3)(k4)+2k(k1)(k2)(k3) =k58k4+23k328k2+12k K3,4的边色数为。 Petersen 图（单星妖怪）的边色数为。 下图的点色数为_；边色数为_ 有 8 个顶的轮，其顶色数是。 有 8 个顶的轮，其顶色数是。 顶大于 2 的树 T 的顶色数是。 右图 G 的独立数(G) A1B2 C3D4 右图 G 的支配数(G) A1B2 C3D4 右图 G 的独立数(G) A1B2 C3D4 右图 G 的支配数(G) A1B2 C3D4 任意一个 p 阶图，总有 K3子图或 4 个点的独立集，则 p 的最小值为 A6B7C8D9 一群人中，总有 3 个人互相认识或者彼此不认识，则这群人的人数至少是 A5B6C7D8 任意一个 p 阶图，总有 K3子图或 3 个点的独立集，则 p 的最小值为() A4B5C6D7 有 8 种化学品 a，b，c，d，e，f，g，h 要放进贮藏室保管。出于安全原因，下列各组药品 不能贮在同一个室内：a-f，a-c，a-h，e-f，e-g，g-h，b-h，b-d，c-d，f-g，b-f，d-e，c-g， d-g，问贮藏这 8 种药品至少需要多少个房间？ 以 8 种药品作为顶点， 若两种药品不能贮在同一个室内， 则它们之间有一条边， 这样得右图， 转化为图的正常顶着色问题。 （1）对各顶点按次数的递减顺序排列为 gfdechab； （2）对 g 及不与之相邻点 a、b 着 1 色； （3）对 f 及不与之相邻点 d、h 着 2 色； （4）对 e 和 c 着 3 色。 故(G)3； 又因为e， f， g为K3子图， 故着色数(G)3， 从而(G)=3。 因此贮藏这 8 种药品至少需要 3 个房间。贮藏方式之一为 gab，dfh， ce。 以下说法错误的是 A欧拉回路必经过图中所有的边B. 欧拉回路必经过图中所有的顶点 C. 哈密顿回路必经过图中所有的边D. 哈密顿回路必经过图中所有的顶点 无向图 G 存在欧拉行迹，当且仅当 AG 中所有结点的度数全为偶数BG 中至多有两个奇数度结点 CG 连通且所有结点的度数全为偶数DG 连通且至多有两个奇数度结点 以下必为欧拉图的是 A顶点度数全为偶数的连通图B奇数顶点只有 2 个的图 C存在欧拉迹的图D没有回路的连通图。 下图中是 Euler 图的是 ABCD 下列图中为欧拉图的是 ABCD 下图中既是欧拉图又是哈密顿图的是 AK9BK10CK2,3DK3,3 设 G 为完全二部图 K2,3，下面命题中为真的是 AG 为 Euler 图BG 为 Hamilton 图CG 为平面图DG 为正则图 在 Petersen 图（单星妖怪）中至少添加条边才能构成欧拉图。5 有 4 个顶的无向连通图 G 是欧拉图，则它的顶次数序列可能是 A1,2,3,4B2,4,6,8C1,2,4,6D5,2,3,4 设 m1，n3，下面命题中，为真的是 A完全图 Kn都是 Euler 图B完全二分图 Kn,m都是 Euler 图 C完全图 Kn都是 Hamilton 图D完全二分图 Kn,m都是 Hamilton 图 构造 Euler 图，其顶点数 p 和边数 q 满足 p，q 的奇偶性相反。 有四个村庄的地下各有一个防空洞甲、乙、丙、丁，相邻两个防空洞之间有地道相通，且每 个防空洞各有一条地道与地面相通，如下图所示（图中表示地道） 。问能否从某一个防空 洞开始，每个地道走一次且仅走一次后回到该防空洞。要求有一定的分析过程。 求下图的中国邮路问题，设 vi为邮局。 （1）写出“倍边”的过程； （2）列出最后所得的从 v1出发的中国邮路。 （1）图中，奇次顶集为v1,v2,v4,v3。计算出每对顶的距离： d(v1,v2)=4，d(v1,v3)=5，d(v1,v4)=7，d(v2,v3)=2，d(v2,v4)=5，d(v3,v4)=3， 求出v1,v2,v4,v3构成的完全加权图的最佳匹配 M=v1v2,v3v4， P(v1,v2)=v1v7v2，P(v3,v4)=v3v4，在 G 中沿 P(v1,v2)与 P(v3,v4)变成同权“倍边” 。 （2）v1v7v2v3v4v5v1v6v2v7v3v4v7v1。 一个连通的无向图 G，如果它的所有顶点的度数都是偶数，那么它具有一条 AHamilton 回路BEuler 回路CHamilton 轨D含所有顶的圈 设完全图 Kn有 n 个顶点(n2)，m 条边，Kn中存在欧拉回路的条件是 Am 为奇数Bn 为偶数Cn 为奇数Dm 为偶数 K7中两两无公共边的 Hamilton 圈有 A2B3C4D7 下面哪个图不是 Hamilton 图 ABCD Petersen 图（单星妖怪）是 Hamilton 图。 若 G 是一个 Hamilton 图，则 G 一定是() A平面图B自对偶图C欧拉图D连通图 若 G 是一个 Euler 图，则 G 一定是() A平面图BHamilton 图C连通图D自对偶图 Petersen 图（单星妖怪）是 AHamilton 图BEuler 图C平面图D非平面图 K11中有条边不重的 Hamilton 回路。5 若图 G 的任一对顶 u，v 皆有 d(u)d(v)V(G)，则 G 是 Hamilt