课程名称︰离散数学 课程性质︰资讯系选修 课程教师︰陈健辉 开课学院：电机资讯学院 开课系所︰资讯系 考试日期（年月日）︰2012/06/18 考试时限（分钟）：100分钟 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : 1. How many edges at most are there in a bipartite graph with 20 vertices? (10%) 2. Why does a graph G=(V,E) have an even number of vertices whose degrees are odd? (10%) 3. Draw a graph of six vertices that has a Hamiltonian cycle, an Euler circuit, and the fewest edges. (10%) 4. Suppose that (u,v) is an edge of a graph G and it has the least cost among all edges that are incident to vertex v. Does every minimum spanning tree contain (u,v) (a) when all edges have distinct costs or (b) when multiple edges may have the same cost? Explain your answer. (10%) 5. Please provide a sufficient-and-necessary conditionfor an Euler trail, but not an Euler circuit, in a connected graph G=(V,E), where |V|>1. (10%) 6. Please draw a graph whose vertex connectivity and edge connectivity are not identical. (10%) 2 3 |V|-1 7. Given a graph G, how to determine 0/1 matrices B, B, B, ...,B so that for 1≦k≦|V|-1 and i≠j, B^(k) (i,j)=1 if and only if there exists an i-to-j walk of length ≦ k in G? (10%) 8. How to modify a maximum clique algorithm (i.e., an algorithm that can find a maximum clique of a graph) so that it can be used to find a minimum vertex cover of a graph? (10%) 9. Suppose that p1, p2, ..., p6 denote six people, where every two people are either familiar with or strange to each other. The following is an incomplete proof, in terms of graph, for the fact that at least three of p1, p2, ..., p6 can be found so that they are either familiar with or strange to one another. Construct an undirected G=(V,E), where V={p1,p2,...,p6} and (pi,pj)∈E if and only if pi and pj are familiar with each other. Two cases about an arbitrary vertex of G, say p1, are discussed below Case 1. There are three (or more) edges incident to p1. Without loss of generality, assume that p1 is adjacent to p2, p3, and p4. Then, either {p2,p3,p4} forms an independent set in G, or there is a clique of size 3 (e.g., {p1,p2,p3} if (p2,p3)∈E) in G. Case 2. There are at most two edges incident to p1. Please complete the discussion of Case 2. (10%) 10.Determine the maximum total flow and a minimum cut for the following transport network. (10%) c1 g ／︱＼20 ↗︱＼10 ／ ︱ ↘ ／15︱ ↘ 15↗ 15︱ b ↓20 m1 ／ ︱ ↗↑＼15︱ ↗︱＼25 ／ 20 ︱／10︱ ↘︱／15︱ ↘ a——→——c2 ︱15 h ↑10 z ＼ ↑＼15︱ ↗︱＼15︱ ↗ ＼ ︱ ↘︱／15︱ ↘︱／25 25↘ 15︱ d ↓10 m2 ＼ ︱ ↗ ＼15︱ ↗ ＼︱／10 ↘︱／5 c3 j → suhorng :图强耶w 06/18 18:25 ※ 编辑: danielu0601 来自: 140.112.30.138 (06/19 15:34)