图论试题中法

1、山东科技大学2008200820092009学年第一学期图论考试试卷A 卷）题号一二三四总得分评卷人审核人得分班级姓名学号一、填空题每空 2 分，共 30 分）1.条边的图中全部顶点的总次数是 100。2.100 个顶点的星的最大顶点次数是。3.个顶点的图的生成子树中有个顶点和 100 条边。4.Peterson 图是、否）Euler 图，是、否）Hamilton 图。5.目的每个顶点次数为，总共有条边，有种完美匹配，它的平面嵌入的厚度下界为。6.对一个括号序列进行检测，从左向右数到第 99 个括号时，记录了右括号个，因此得出结论为坏括号序列。7.100 个顶点的极大连通平面图中最多有条边，个

2、面。8.有向图回的底图囚是连通的，则区至少为一连通有向图；若存在一个以回的某个顶点 w 为根的外向树，则区为一连通有向图。b5E2RGbCAP二、画图题每题 5 分，共 15 分）1.画出所有不同构的 5 顶点树。2.画出 5 次正则完全图，证明它是否为 Euler 图。3.画出面数最多的 6 顶点连通二分平面图的平面嵌入，并指出它有几个面。三、应用题10 分）1.有回把钥匙和回把锁混在一起，确定知道每把锁都能有一把钥匙打开，锁匠想把它们一对对的分开， 那么有多少种分法是每对中的钥匙都无法打开锁的。plEanqFDPw给出求解上述问题的递归公式，并证明之；算出三时问题的解。四、算法题第 1、2

3、、3 每题 10 分，4 题 15 分，共 45 分）1.写出用 Kruskal 算法求图 1 生成子树的运行过程：按算法的运行顺序写出每一轮所选的边；写出对所选的边所进行的操作及其原因指出算法如何判断所选边是否符合生成树的条件）；给出算法终止的条件。设算法按照下标由小到大的顺序遍历所有边，且对每条边2.若有 5 字符出现的概率表为字符abcde出现概率0.20.160.130.280.23写出用 Huffman 算法求上表中 5 字符 Huffman 编码的运行过程： 依“左子概率小于右子”的原则， 按算法的运行顺序写出每一轮构造的由有序二元树组成的森林；给出算法终止的条件；按照“左 0 右

4、 1”的原则给出这 5 个字符的 Huffman 编码。3.写出用 Hungarian 算法求图 2 完备匹配的运行过程：按算法的运行顺序写出每一轮所选择的图 1点，写出从该点出发构造的可增广轨；按中所求的可增广轨求出的本轮所得匹配；给出算法终止的条件。设初始匹配为,对算法中每条边都表示为巴，对顶点的遍历顺序为一.）4,求图 3 的中国邮路问题，设可为邮局。写出求图 3 的“倍边”重边）的过程；写出用 FE 算法求 Euler 回路的过程；给出算法终止的条件，列出最后所得的中国邮路。设算法按照下标由小到大的顺序遍历所有顶点，且对每条边回，都有山。）个人收集整理资料，仅供交流学习，勿作商业用途山

5、东科技大学2008200820092009学年第一学期图论考试试卷B 卷）班级姓名学号题号一二三四总得分评卷人审核人得分一、填空题每空 2 分，共 30 分）1.100 个顶点的星中有条边。2.100 条边的图中全部顶点的总次数是。3.100 个顶点的图的生成子树中有个顶点和条边。4.Peterson 图是、否）Euler 图，是、否）Hamilton 图。5.m 的每个顶点次数为，总共有条边，它种完美匹配，它的平面嵌入的厚度下界为。6.对一个好括号序列进行检测，从左向右至少数到第个括号时，会记录下 50 个右括号。7.100 个面的极大连通平面图中最多有条边，个顶点。8.对有向图回，若存在一

6、个以习的某个顶点回为根的内向树，则区为一连通有向图；若存在一条有向 Hamilton 圈则回为一连通有向图。DXDiTa9E3d二、画图题每题 5 分，共 15 分）1.画出所有不同构的只含一个圈的 4 顶点单图。2.画出 3 次正则完全二分图，证明它是否为 Euler 图。3.画出面数最多的 5 顶点连通平面图的平面嵌入，并指出它有几个面。三、应用题10 分）个人收集整理资料，仅供交流学习，勿作商业用途1.某次会议主席台上有匀个座位，但会议组织者把入座名单搞丢了,于是他们又重新摆上名字，那么有多少种摆法是每个座位上的名字都错了。RTCrpUDGiT给出求解上述问题的递归公式，并证明之；给出三

7、时问题的解。四、算法题第 1、2、3 每题 10 分，4 题 15 分，共 45 分）1.写出用 Dijkstra 算法求图 1 中从 w 点出发的单源最短轨的运行过程：按算法的运行顺序写出每一轮备选顶点集的变化和备选顶点的前驱；写出每一轮求出的最短轨；给出算法终止的条件。设算法按照下标由小到大的顺序遍历所有顶点，且对每条边回，都有句。）2.若有 5 字符出现的概率表为字符abcde出现概率0.40.110.190.170.13写出用 Huffman 算法求上表中 5 字符 Huffman 编码的运行过程：依“左子概率小于右子”的原则，按算法的运行顺序写出每一轮构造的由有序二元树组成的森林；给出算法终止的条件；按照“左 0 右 1”的原则给出这 5 个字符的 Huffman 编码。3.写出用 Hungarian 算法求图 2 完备匹配的运行过程：|按算法的运行顺序写出每一轮所选择的XI点，写出从该点出发构造的可增广轨；按中所求的可增广轨求出的本轮所得匹配；给出算法终止的条件。图2设初始匹配为 W1,对算法中每条边都表示为回，对顶点的遍图 1历顺序为）个人收集整理资料，仅供交流学习,4,求图 3 的中国邮路问题，设因为邮局,写出求图 3 的“倍边”重边）