《2013四川师范大学 图论期末考试复习题》由会员分享，可在线阅读，更多相关《2013四川师范大学 图论期末考试复习题（23页珍藏版）》请在金锄头文库上搜索。
1、2013四川师范大学 图论考试复习题关于图论中的图，以下叙述不正确的是A图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B图论中的图，画边时长短曲直无所谓。C图中的边表示研究对象，点表示研究对象之间的特定关系。 D图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。一个图中最长的边一定不包含在最优生成树内。下面哪个图形不与完全二分图K3,3同构？ABCD有10条边的5顶单图必与K5同构。完全二分图Km,n的边数是AmBnCm+nDmn无向完全图Kn的边数为AnBn2Cn(n-1)Dn(n-1)/2若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边
2、。对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。有15个顶的单图的边数最多是A105B210C21D45图G如右，则dacbebA是G中的一条道路B是G中的一条道路但不是行迹C是G中的一条行迹但不是轨道D不是G的一条道路图G如右，则befcdefA是G的一个圈B是G的一条道路但不是行迹C是G的一条行迹但不是轨道D是G的一条轨道但不是圈图G如右图所示，则w (G)=A1B2C7D8下列图形中与其补图同构的是ABCD求下图中顶u0到其余各顶点的最短轨长度。u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=
3、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
4、，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解：下面的表格给出了求解
5、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的最短轨及最短距
6、离。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个人组成的人群，n2，证明至少有两位，他们在人群中的朋友一样多。证明：把n个人看做n个点，如果两个人是朋友，则在这两个点之间连一条边，这样可以得到一个含n个顶的单图。显然顶的最大次数为n-1，如果这n个顶的次数不一样，则它们必为0,1,2,n-1，而次为0的顶
7、与各顶都不相邻，因此不可能有顶的次为n-1，出现矛盾。因此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条边的树有几个顶点？Am B Cm+1 D完全二分图Km,n的
8、边数是：Am Bn Cm+n Dmn有n个顶的图中，圈的长度最大值为A2n Bn Cn+1 Dn1含5个顶、3条边的不同构的无向图有A2个B3个C4个D5个图G如右所示，与G同构的图是A B C Dv1，v2，v3，v4，v5，v6是6个城市，下面矩阵的（i，j）号元素是vi到vj的机票票价，试为一个旅行者制作一张由v1到各城去旅游的最便宜的航行路线图。完全图K4的生成树的数目为 。一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点的个数是A5B7C8D9有6个顶的不同构的树共有 棵。设图G是有6个顶点的连通图，顶点的总度数为18，则可从G中删去 条边后使之变成树。 4已知一棵无
9、向树T中有8个顶点，4度、3度、2度的顶点各一个，T的树叶数为 。有n（n1）个顶的树T，下面说法不正确的是AT是二分图 BT是可平面图 CT中存在完美匹配 DT中任意两点间有唯一轨道相连接设G是有n个结点，m条边的连通图，为了得到G的一棵生成树，必须从G中删去的边数是Amn+1 Bmn Cm+n+1 Dnm+1无向简单图G是棵树，当且仅当AG连通且边数比顶点数少1 BG连通且顶点数比边数少1 CG的边数比顶点数少1 DG中没有圈下面给出的集合中，哪一个是前缀码A0，10，110，101111 B01，001，000，1 Cb，c，aa，ab，aba D1，11，101，001，0011给定一
10、个序列集合1，01，10，11，001，000，若去掉其中的元素 ，则该序列集合构成前缀码。若一棵典型有序二元树有2n-1个顶点，则它的树叶数是 An B2n Cn-1 D2 下面那种描述的单图不一定是树。 A无回路的连通图B有n个顶点，n-1条边的图C每对顶点都有通路的图D连通但删去一条边则不连通的图 下列无向图一定是树的是A连通图 B无圈但添加一条边后有圈的图 C每对顶点间都有路的图 D连通且E(G)=V(G)-1求生成树个数时，将一个树对应一个Prufer序列，如果树T的对应Prufer序列为(2,3,2,3)，则标号为2的顶点的次数是A1B2C3D4右图是二分图。一个有13个顶的简单图
11、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。求下图的
12、最小生成树，并给出权值(只给结果，不要过程)答：权和为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树。
