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

2026电子科技大学图论考试复习题关于图论中的图，以下叙述不正确的是A．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。B．图论中的图，画边时长短曲直无所谓。C．图中的边表示研究对象，点表示研究对象之间的特定关系。D．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。一个图中最长的边一定不包含在最优生成树内。下面哪个图形不与完全二分图K3,3同构？A． B． C． D．有10条边的5顶单图必与K5同构。完全二分图Km,n的边数是A．m B．n C．mn D．mn无向完全图Kn的边数为A．n B．n2 C．n(n1) D．n(n1)/2若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有条边。对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。有15个顶的单图的边数最多是A．105 B．210 C．21 D．45图G如右，则dacbebA．是G中的一条道路 B．是G中的一条道路但不是行迹C．是G中的一条行迹但不是轨道 D．不是G的一条道路图G如右，则befcdefA．是G的一个圈 B．是G的一条道路但不是行迹C．是G的一条行迹但不是轨道 D．是G的一条轨道但不是圈图G如右图所示，则(G)A．1 B．2 C．7 D．8下列图形中与其补图同构的是A． B． C． D．求下图中顶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个顶的无向简单图的个数为A．1 B．2 C．3 D．4画出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点到其他任意一点的最短路。v1v3v1v2v1v2v5v1v3v4v1v2v5v6v1v2v5v6v7设有城市v1，v2，v3，v4，v5，v6，各城市之间的距离如下表。使用Dijkstra算法求城市v1到其他各城市的最短路径以及最短距离。要求说明求解过程（提示：应将城市之间的道路图看作是无向图）。道路v1v2v1v3v2v3v2v4v2v5v3v5v4v5v4v6v5v6距离142751326解：下面的表格给出了求解v1到其他各顶点之间的最短距离的Dijkstra算法执行过程：步骤v1v2v3v4v5v601/(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 长度为1v1到v3的最短路径是：v1v2v3 长度为3v1到v4的最短路径是：v1v2v3v5v4 长度为7v1到v5的最短路径是：v1v2v3v5 长度为4v1到v6的最短路径是：v1v2v3v5v4v6 长度为9求下图中顶v1到v11的最短轨及最短距离。L100个顶点的星的最大顶点次数是。做一个图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个人组成的人群，n≥2，证明至少有两位，他们在人群中的朋友一样多。证明：把n个人看做n个点，如果两个人是朋友，则在这两个点之间连一条边，这样可以得到一个含n个顶的单图。显然顶的最大次数为n1，如果这n个顶的次数不一样，则它们必为0,1,2,…,n1，而次为0的顶与各顶都不相邻，因此不可能有顶的次为n1，出现矛盾。因此n个顶的次数必至少有两个是相等的。所以至少有两位，他们在人群中的朋友一样多。设G是一个含n个顶点的无向简单图，n是大于等于2的奇数．证明图G与它的补图GC中的奇数次顶点个数相等。E(GC)是由完全图Kn的边删去E(G)所得到的．所以对于任意结点u∈V(G)，u在G和GC中的次数之和等于u在Kn中的次数．由于n是大于等于2的奇数，从而Kn的每个顶点都是偶数度的（n−1≥(2)度），于是若u∈V(G)在G中是奇数次顶点，则它在GC中也是奇数次顶点．故图G与它的补图GC的奇数次顶点个数相等。具有m条边的树有几个顶点？A．m B． C．m1 D．完全二分图Km,n的边数是：A．m B．n C．m+n D．mn有n个顶的图中，圈的长度最大值为A．2n B．n C．n+1 D．n−1含5个顶、3条边的不同构的无向图有A．2个 B．3个 C．4个 D．5个图G如右所示，与G同构的图是A． B． C． D．v1，v2，v3，v4，v5，v6是6个城市，下面矩阵的（i，j）号元素是vi到vj的机票票价，试为一个旅行者制作一张由v1到各城去旅游的最便宜的航行路线图。完全图K4的生成树的数目为。一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点的个数是A．5 B．7 C．8 D．9有6个顶的不同构的树共有棵。设图G是有6个顶点的连通图，顶点的总度数为18，则可从G中删去条边后使之变成树。4已知一棵无向树T中有8个顶点，4度、3度、2度的顶点各一个，T的树叶数为。有n（n>1）个顶的树T，下面说法不正确的是A．T是二分图 B．T是可平面图C．T中存在完美匹配 D．T中任意两点间有唯一轨道相连接设G是有n个结点，m条边的连通图，为了得到G的一棵生成树，必须从G中删去的边数是A．m−n+1 B．m−n C．m+n+1 D．n−m+1无向简单图G是棵树，当且仅当A．G连通且边数比顶点数少1 B．G连通且顶点数比边数少1C．G的边数比顶点数少1 D．G中没有圈下面给出的集合中，哪一个是前缀码A．{0，10，110，101111} B．{01，001，000，1}C．{b，c，aa，ab，aba} D．{1，11，101，001，0011}给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素，则该序列集合构成前缀码。若一棵典型有序二元树有2n1个顶点，则它的树叶数是A．n B．2n C．n1 D．2下面那种描述的单图不一定是树。A．无回路的连通图 B．有n个顶点，n1条边的图C．每对顶点都有通路的图 D．连通但删去一条边则不连通的图下列无向图一定是树的是A．连通图 B．无圈但添加一条边后有圈的图C．每对顶点间都有路的图 D．连通且E(G)V(G)1求生成树个数时，将一个树对应一个Prufer序列，如果树T的对应Prufer序列为(2,3,2,3)，则标号为2的顶点的次数是A．1 B．2 C．3 D．4右图是二分图。一个有13个顶的简单图G中有3个顶的次数是4，4个顶的次数是3，6个顶的次数是1，则图G一定是树。设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有片树叶。10若T是图G的生成树，则A．T必唯一

B．G不一定是连通图

C．T中必不含圈

D．G中不含圈若G是一个含p个顶点，q条边的图，若q≥p，则G中必有圈。有4个连通片组成的17个顶的森林的边数为A．16 B．15 C．14 D．13设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条边，则这个图的边数是A．3 B．4 C．5 D．6图H是下面平面图G的一个平面嵌入，则图H的面数是A．5 B．6 C．7 D．8如果平面图G有v个顶点，e条边和f个平面，则A．vef2 B．evf2 C．vef2 D．evf2具有6个顶点，12条边的连通简单平面图中，每个面的边数是A．2 B．3 C．4 D．5设G为一个连通的平面图，G有5个顶点和9条边，则G有个面。6n(n≥3)阶极大平面图的面数等于。2n4n(n≥3)阶极大平面图的边数等于。3n6100个顶点的极大连通平面图中最多有个面。196100个面的极大连通平面图中最多有个顶点。52画出面数最多的5顶点连通平面图的平面嵌入，并指出它有几个面。6个面。如果单图G是平面图，那么它一定有一个次数不超过5的顶。不妨设G是连通的，否则考虑它的每一个连通分支。设G有n个顶，m条边，f个面。因为G是单图，每个面至少有三条边，所以3f≤2m。如果每个顶的次数都不小于6，那么有6n≤2m。由欧拉公式得2nmf≤m/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因子分解的是A． B． C． D．给5位同学各写好一封信的信笺，又写好了给这5位同学的信封，把信笺都插错了信封的方法数为A．48 B．44 C．36 D．24有n把钥匙和n把锁混在一起，确定知道每把锁都能有一把钥匙打开，锁匠想把它们一对对的分开，那么有多少种分法是每对中的钥匙都无法打开锁的。（1）给出求解上述问题的递归公式，并证明之；（2）算出n=6时问题的解。（1）设第i把钥匙为xi，第i把锁为yi，X={x1,x2,…,xn}，Y={y1,y2,…,yn}。把xi和yi视为顶点，当且仅当i≠j时，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)A．b(n1)b(n2) B．(n1)[b(n1)b(n2)] C．n[b(n1)b(n2)] D．2(n1)[b(n1)b(n2)]给6位同学各写好一封信的信笺，又写好了给这6位同学的信封，把信笺都插错了信封的方法数为A．120 B．240 C．265 D．288下列哪个图无完备匹配A．k次正则2分图 B．Petersen图（单星妖怪）C．K2n D．K2,4r=5,当s=时，完全二部图Kr,s才可能存在完美匹配。5K10,10有种完美匹配。10右图G的覆盖数(G)＝A．2 B．3 C．4 D．5K3,5的覆盖数(K3,5)＝A．2 B．3 C．4 D．5某公司有5名工作人员x1,x2,x3,x4,x5，他们每人承担y1,y2,y3,y4,y5这5项工作中的一项，每人对每项工作创造的价值用下边的矩阵表示，公司领导根据每个人的特长如何合理分工，使得这5个工作人员对公司创造的总价值最大？答：最佳匹配是{x1y4，x2y1，x3y3，x4y2，x5y5}用匈牙利算法求下图的最大匹配。{x1y1，x2y2，x3y5，x4y3，x5y4}用匈牙利算法求下图的最大匹配。{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的单图 B．K5C．K3,3 D．正方体把平面分为α个区域，使任两个区域相邻，则α的最大值为A．5 B．4 C．3 D．2下列哪个图不是极大平面图A．正四面体 B．正六面体 C．正八面体 D．正二十面体下面哪个图是平面图A．K5 B．K2,3 C．K6 D．K3,3Kuratowsky认为可作为判定图的可平面性依据的基本不可平面图之一是A．K3 A．K4 A．K5 A．K6以下说法错误的是A．同构的图具有相同的顶点数和边数B．同胚的图边数相同，但顶点数不同C．如果一个图是可平面的，那么与它同构的图也是可平面的D．如果一个图是可平面的，那么与它同胚的图也是可平面的下列图中哪个的对偶图是自身？A．K3 B．K4 C．K5 D．K615阶圈C15的顶色数是A．2 B．3 C．6 D．15设G为n顶m条边的无向连通单图，下列命题为假的是A．G一定有生成树 B．m一定大于nC．G的边色数'(G)≥Δ(G) D．G的最大度Δ(G)≤n1完全图K15的顶色数是A．2 B．3 C．6 D．15完全图G的色多项式P(G，t)是A．t(t1)2 B．t(t1)(t2) C．t3 D．t(t1)(t) 图G的色多项式P(G，t)是t44t36t23t，则图G的边数是A．3 B．4 C．5 D．6图G的色多项式P(G，t)是t44t36t23t，则图G的顶数是A．3 B．4 C．5 D．6完全图K15的边色数是A．2 B．3 C．6 D．1515阶圈C15的边色数是A．2 B．3 C．6 D．15完全图K8的边色数是A．2 B．3 C．7 D．8求下图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+12kK3,4的边色数为。Petersen图（单星妖怪）的边色数为。下图的点色数为_______；边色数为_______有8个顶的轮，其顶色数是。有8个顶的轮，其顶色数是。顶大于2的树T的顶色数是。右图G的独立数(G)＝A．1 B．2 C．3 D．4右图G的支配数(G)＝A．1 B．2 C．3 D．4右图G的独立数(G)＝A．1 B．2 C．3 D．4右图G的支配数(G)＝A．1 B．2 C．3 D．4任意一个p阶图，总有K3子图或4个点的独立集，则p的最小值为A．6 B．7 C．8 D．9一群人中，总有3个人互相认识或者彼此不认识，则这群人的人数至少是A．5 B．6 C．7 D．8任意一个p阶图，总有K3子图或3个点的独立集，则p的最小值为()A．4 B．5 C．6 D．7有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存在欧拉行迹，当且仅当A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点以下必为欧拉图的是A．顶点度数全为偶数的连通图 B．奇数顶点只有2个的图C．存在欧拉迹的图 D．没有回路的连通图。下图中是Euler图的是A． B． C． D．下列图中为欧拉图的是A． B． C． D．下图中既是欧拉图又是哈密顿图的是A．K9 B．K10 C．K2,3 D．K3,3设G为完全二部图K2,3，下面命题中为真的是A．G为Euler图 B．G为Hamilton图 C．G为平面图 D．G为正则图在Petersen图（单星妖怪）中至少添加条边才能构成欧拉图。5有4个顶的无向连通图G是欧拉图，则它的顶次数序列可能是A．1,2,3,4 B．2,4,6,8 C．1,2,4,6 D．5,2,3,4设m≥1，n≥3，下面命题中，为真的是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，如果它的所有顶点的度数都是偶数，那么它具有一条A．Hamilton回路 B．Euler回路 C．Hamilton轨 D．含所有顶的圈设完全图Kn有n个顶点(n≥2)，m条边，Kn中存在欧拉回路的条件是A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数K7中两两无公共边的Hamilton圈有A．2 B．3 C．4 D．7下面哪个图不是Hamilton图A． B． C． D．Petersen图（单星妖怪）是Hamilton图。若G是一个Hamilton图，则G一定是()．A．平面图 B．自对偶图 C．欧拉图 D．连通图若G是一个Euler图，则G一定是()．A．平面图 B．Hamilton图 C．连通图 D．自对偶图Petersen图（单星妖怪）是A．Hamilton图 B．Euler图 C．平面图 D．非平面图K11中有条边不重的Hamilton回路。5若图G的任一对顶u，v皆有d(u)d(v)≥V(G)，则G是Hamilton图。若G是H