《2015电子科技大学》由会员分享，可在线阅读，更多相关《2015电子科技大学（25页珍藏版）》请在金锄头文库上搜索。
1、有 10 条边的 5 顶单图必与 K5 同构。完全二分图K的边数是m,nA. mB. nC. m+nD. mn无向完全图K的边数为nA. nB. n2C. n(n-l)D. n(n-l)/2若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有条边。对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。有 l5 个顶的单图的边数最多是A. l05B. 2l0图 G 如右，则 dacbebA. 是G中的一条道路B. 是G中的一条道路但不是行迹C. 是G中的一条行迹但不是轨道D. 不是G的一条道路图 G 如右，则 befcdefA. 是G的一个圈B. 是G的
2、一条道路但不是行迹C. 是G的一条行迹但不是轨道D. 是G的一条轨道但不是圈C. 2lD. 452015 电子科技大学 图论考试复习题关于图论中的图，以下叙述不正确的是A. 图中点表示研究对象，边或有向边表示研究对象之间的特定关系。B. 图论中的图，画边时长短曲直无所谓。C. 图中的边表示研究对象，点表示研究对象之间的特定关系。D. 图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。一个图中最长的边一定不包含在最优生成树内。CD.下面哪个图形不与完全二分图K3,3同构?AB图G如右图所示，则（G）=A. 1B. 2C. 7D. 8下列图形中与其补图同构的是A.B.C.D.V2V
3、4=2, V2V7=3, V3V5=3,求下图中顶u0到其余各顶点的最短轨长度。请画出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. 1B. 2C. 3D. 4画出5个具有5个结点5条边的非同构的无向连通简单图。u0到v1的最短轨长度为6，u0到v2的最短轨长度为1，u0到v3的最短轨长度为4，u0
4、到v4 的最短轨长度为2，u0到v5的最短轨长度为6，u0到v6的最短轨长度为9，u0到v7的最短轨 长度为3。用 Dijkstra 算法求下图中从 v 1 点到其他任意一点的最短路。v1vv1vv1v2vv1v3vv1v2v5vv1v2v5v6v设有城市v1，v2，v3，v4，v5，v6，各城市之间的距离如下表。使用Dijkstra算法求城市v1 到其他各城市的最短路径以及最短距离。要求说明求解过程（提示：应将城市之间的道路图 看作是无向图）。道路VV2VV3V2V3V2V4V2V5V3V5V4V5V4V6V5V6距离4275326解：下面的表格给出了求解V到其他各顶点之间的最短距离的Dij
5、kstra算法执行过程:步骤V2V3V4V5V60心）4心）000000心）3/(v2)8/(v2)6/(v2)00/(v2)8/(v2)4/(v3)007/(v5)/(v3)0/(v5)/(v5)9/(v/(v4)最后得到V到其他各城市的最短路径及最短距离为:V到V2的最短路径是：VV2长度为1V1 到 V3 的最短路径是： V1V2V3长度为 3V到V4的最短路径是：VV2V3V5V4长度为7V1 到 V5 的最短路径是： V1V2V3V5长度为 4V 到 V6 的最短路径是： VV2V3V5V4V6长度为 9求下图中顶V到V的最短轨及最短距离。vii100个顶点的星的最大顶点次数是做一个
6、图G,使其顶的次序列为（5,5,4,4,3,322,2）。I (10分求理到訂I勺最鬼通路b 10ei下列哪个序列不可能构成一个图的顶点次数序列？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个顶的单图。显然顶的最大次数为n-1，如果这n个顶的次数不一样，则它们必为0,1,2,.n-l，而次
7、为0 的顶与各顶都不相邻，因此不可能有顶的次为n-1,出现矛盾。因此n个顶的次数必至少有 两个是相等的。所以至少有两位，他们在人群中的朋友一样多。设G是一个含n个顶点的无向简单图，n是大于等于2的奇数.证明图G与它的补图Gc中 的奇数次顶点个数相等。E(Gc)是由完全图K”的边删去E(G)所得到的.所以对于任意结点uV(G)，u在G和Gc中 的次数之和等于u在Kn中的次数.由于n是大于等于2的奇数，从而Kn的每个顶点都是偶 数度的(n-12(2)度),于是若u V(G)在G中是奇数次顶点,则它在Gc中也是奇数次顶点.故 图G与它的补图Gc的奇数次顶点个数相等。具有m条边的树有几个顶点？A. m
8、B. m 1C. m 1完全二分图K的边数是：m,nA. mB. nC. m+n有 n 个顶的图中，圈的长度最大值为A. 2nB. nC. n+1D.D. mnD. n 1含 5 个顶、3 条边的不同构的无向图有A. 2 个B. 3个C. 4 个D. 5 个图 G 如右所示，与 G 同构的图是A.B.D.C.v1， v2， v3， v4， v5， v6是6个城市，下面矩阵的（i, j）号兀素是v.到与的机票票价，试为 一个旅行者制作一张由v1到各城去旅游的最便宜的航行路线图。7050OO4025105001520OQ25OQ1501020OQ4020100102525OQ20100551025
9、OO25550完全图K4的生成树的数目为。一棵树有2个2度顶点, 1 个3度顶点, 3个4度顶点,则其1度顶点的个数是A. 5B. 7C. 8D. 9有6个顶的不同构的树共有棵。设图G是有6个顶点的连通图，顶点的总度数为18,则可从G中删去条边后使之变成树。 4已知一棵无向树T中有8个顶点，4度、3度、2度的顶点各一个，T的树叶数为。有n (n1 )个顶的树T下面说法不正确的是A. T是二分图B. T是可平面图C. T中存在完美匹配D. T中任意两点间有唯一轨道相连接设G是有n个结点，m条边的连通图, 是A. mn+lB. mn无向简单图G是棵树，当且仅当A. G连通且边数比顶点数少1C. G
10、的边数比顶点数少1下面给出的集合中，哪一个是前缀码A. 0， 10， 110， 101111C. b， c， aa， ab， aba为了得到G的一棵生成树，必须从G中删去的边数C. m+n+1D. nm+1B. G连通且顶点数比边数少1D. G中没有圈B. 01， 001， 000， 1D. 1， 11， 101， 001， 0011，则该序给定一个序列集合1，01，10，11，001，000，若去掉其中的元素列集合构成前缀码。A. nB. 2n下面那种描述的单图不一定是树。A.无回路的连通图C.每对顶点都有通路的图下列无向图一定是树的是A.连通图C.每对顶点间都有路的图C. n-1D. 2B
11、有n个顶点，n-1条边的图D.连通但删去一条边则不连通的图B.无圈但添加一条边后有圈的图D.连通且 E(G)=V(G)-1若一棵典型有序二元树有2n-1个顶点，则它的树叶数是求生成树个数时，将一个树对应一个Prufer序列，如果树T的对应Prufer序列为(2,3,2,3), 则标号为2的顶点的次数是A. 1B. 2C. 3D. 4一个有13个顶的简单图G中有3个顶的次数是4，4个顶的次数是3，6个顶的次数是1， 则图G 一定是树。设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有片树叶。10若 T 是图 G 的生成树，则AT 必唯一CT 中必不含圈BG 不一定是连通图DG 中
12、不含圈若G是一个含p个顶点，q条边的图，若q，则G中必有圈。有4个连通片组成的17个顶的森林的边数为A16B15C14D13设G是一个满足IE(G)|2IV(G)I的图，则G中必有圈。在下图中，用Kruskal算法构造最小生成树，写出边添加到生成树的边序列，并画出生成树。d答：求下图的最优树T (不要求中间过程，只要求画出最小生成树，并给出T的权和)。权和为 17。求下图的最小生成树，并给出权值(只给结果，不要过程)答：权和为 28。求下图的最小生成树，并给出权值。v6权和为 16。6画出带权 0,2，0.17，0.13，0.1，0.1，0.08，0.06，0.06，0.07, 0.03 的
13、Huffman 树。假设用于通信的电文仅由 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.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个不同花色的碗摞成一摞。妹妹把姐姐洗过的碗每次拿一个 放入消毒柜，也摞成一摞。由于小妹贪玩，碗被放入消毒柜可能不及时，姐姐则把洗过的碗 摞在旁边，则小妹摞起的碗摞可能的
