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

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