图论试题(中法07)08-09(1).doc

山东科技大学20082009学年第一学期图论考试试卷（A卷）班级 姓名 学号 题号一二三四总得分评卷人审核人得分一、填空题（每空2分，共30分） 1. 条边的图中全部顶点的总次数是100。 2.100个顶点的星的最大顶点次数是 。 3. 个顶点的图的生成子树中有 个顶点和100条边。 4.Peterson图 （是、否）Euler图， （是、否）Hamilton图。 5.的每个顶点次数为 ，总共有 条边，有 种完美匹配，它的平面嵌入的厚度下界为 。 6.对一个括号序列进行检测，从左向右数到第99个括号时，记录了右括号 个，因此得出结论为坏括号序列。 7.100个顶点的极大连通平面图中最多有 条边， 个面。 8.有向图的底图是连通的，则至少为一 连通有向图；若存在一个以的某个顶点为根的外向树，则为一 连通有向图。二、画图题（每题5分，共15分） 1.画出所有不同构的5顶点树。 2.画出5次正则完全图，证明它是否为Euler图。 3.画出面数最多的6顶点连通二分平面图的平面嵌入，并指出它有几个面。三、应用题（10分） 1.有把钥匙和把锁混在一起，确定知道每把锁都能有一把钥匙打开，锁匠想把它们一对对的分开，那么有多少种分法是每对中的钥匙都无法打开锁的。给出求解上述问题的递归公式，并证明之；算出时问题的解。四、算法题（第1、2、3每题10分，4题15分，共45分） 1.写出用Kruskal算法求图1生成子树的运行过程：图1按算法的运行顺序写出每一轮所选的边； 写出对所选的边所进行的操作及其原因（指出算法如何判断所选边是否符合生成树的条件）；给出算法终止的条件。（设算法按照下标由小到大的顺序遍历所有边，且对每条边，都有。） 2.若有5字符出现的概率表为字符abcde出现概率0.20.160.130.280.23写出用Huffman算法求上表中5字符Huffman编码的运行过程：依“左子概率小于右子”的原则，按算法的运行顺序写出每一轮构造的由有序二元树组成的森林；给出算法终止的条件；按照“左0右1”的原则给出这5个字符的Huffman编码。图2 3.写出用Hungarian算法求图2完备匹配的运行过程： 按算法的运行顺序写出每一轮所选择的点，写出从该点出发构造的可增广轨；按中所求的可增广轨求出的本轮所得匹配；给出算法终止的条件。（设初始匹配为，对算法中每条边都表示为，对顶点的遍历顺序为）图3 4.求图3的中国邮路问题，设为邮局。写出求图3的“倍边”（重边）的过程；写出用FE算法求Euler回路的过程；给出算法终止的条件，列出最后所得的中国邮路。（设算法按照下标由小到大的顺序遍历所有顶点，且对每条边，都有。）第 2 页/共 2 页山东科技大学20082009学年第一学期图论考试试卷（B卷）班级 姓名 学号 题号一二三四总得分评卷人审核人得分一、填空题（每空2分，共30分） 1.100个顶点的星中有 条边。 2.100条边的图中全部顶点的总次数是 。 3.100个顶点的图的生成子树中有 个顶点和 条边。 4.Peterson图 （是、否）Euler图， （是、否）Hamilton图。 5.的每个顶点次数为 ，总共有 条边，它 种完美匹配，它的平面嵌入的厚度下界为 。 6.对一个好括号序列进行检测，从左向右至少数到第 个括号时，会记录下50个右括号。 7.100个面的极大连通平面图中最多有 条边， 个顶点。 8.对有向图，若存在一个以的某个顶点为根的内向树，则为一 连通有向图；若存在一条有向Hamilton圈则为一 连通有向图。二、画图题（每题5分，共15分） 1.画出所有不同构的只含一个圈的4顶点单图。 2.画出3次正则完全二分图，证明它是否为Euler图。 3.画出面数最多的5顶点连通平面图的平面嵌入，并指出它有几个面。三、应用题（10分） 1.某次会议主席台上有个座位，但会议组织者把入座名单搞丢了，于是他们又重新摆上名字，那么有多少种摆法是每个座位上的名字都错了。给出求解上述问题的递归公式，并证明之；给出时问题的解。四、算法题（第1、2、3每题10分，4题15分，共45分）图1 1.写出用Dijkstra算法求图1中从点出发的单源最短轨的运行过程：按算法的运行顺序写出每一轮备选顶点集的变化和备选顶点的前驱；写出每一轮求出的最短轨；给出算法终止的条件。（设算法按照下标由小到大的顺序遍历所有顶点，且对每条边，都有。）2.若有5字符出现的概率表为字符abcde出现概率0.40.110.190.170.13写出用Huffman算法求上表中5字符Huffman编码的运行过程：依“左子概率小于右子”的原则，按算法的运行顺序写出每一轮构造的由有序二元树组成的森林；给出算法终止的条件；按照“左0右1”的原则给出这5个字符的Huffman编码。图2 3.写出用Hungarian算法求图2完备匹配的运行过程： 按算法的运行顺序写出每一轮所选择的点，写出从该点出发构造的可增广轨；按中所求的可增广轨求出的本轮所得匹配；给出算法终止的条件。（设初始匹配为，对算法中每条边都表示为，对顶点的遍历顺序为）图