Question

计算机、图论高手进！！！！！急！！！！！！在线等！！！！！！！

一、填空题（每空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. 写出用Dijkstra算法求图1中从点出发的单源最短轨的运行过程：
① 按算法的运行顺序写出每一轮备选顶点集的变化和备选顶点的前驱；
② 写出每一轮求出的最短轨；
③ 给出算法终止的条件。
（设算法按照下标由小到大的顺序遍历所有顶点，且对每条边，都有。）
2. 若有5字符出现的概率表为
字符abcde出现概率0.40.110.190.170.13
写出用Huffman算法求上表中5字符Huffman编码的运行过程：
① 依“左子概率小于右子”的原则，按算法的运行顺序写出每一轮构造的由有序二元树组成的森林；
② 给出算法终止的条件；
③ 按照“左0右1”的原则给出这5个字符的Huffman编码。
3. 写出用Hungarian算法求图2完备匹配的运行过程：
① 按算法的运行顺序写出每一轮所选择的点，写出从该点出发构造的可增广轨；
② 按①中所求的可增广轨求出的本轮所得匹配；
③ 给出算法终止的条件。
（设初始匹配为，对算法中每条边都表示为，对顶点的遍历顺序为）
4. 求图3的中国邮路问题，设为邮局。
① 写出求图3的“倍边”（重边）的过程；
② 写出用FE算法求Euler回路的过程；
③ 给出算法终止的条件，列出最后所得的中国邮路。
（设算法按照下标由小到大的顺序遍历所有顶点，且对每条边，都有。）

Answer 1

1. 100个顶点的星中有 99 条边。
2. 100条边的图中全部顶点的总次数是 200 。
3. 100个顶点的图的生成子树中有 100 个顶点和 101 条边。
4. Peterson图 否 Euler图， 否 Hamilton图。
5. 的每个顶点次数为 ，总共有 条边，它 种完美匹配，它的平面嵌入的厚度下界为 。
6. 对一个好括号序列进行检测，从左向右至少数到第 个括号时，会记录下50个右括号。
7. 100个面的极大连通平面图中最多有 150 条边，52 个顶点。