課程名稱︰離散數學 課程性質︰系必修 課程教師︰陳健輝 開課學院：電資學院 開課系所︰資訊系 考試日期（年月日）︰2008/11/05 考試時限（分鐘）：120(有再延長約20分) 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : (Unless specified particularly, all graphs are simple and undirected.) 1. Is K(3,2) planar? Give your reason. (5%) 2. Give a 5 ×5 0/1 matrix that represents the reflexive transitive closure of G1. You can obtain the matrix directly by observation, not by matrix computation. (5%) G1 = (V1,E1), V1 = {1,2,3,4,5} E1 = {<1,2>,<1,3>,<2,3>,<2,4>,<3,5>} 3. Explain why there is no isomorphism between G2 and G3. (5%) G2 = (V2,E2) V2 = {1,2,3,4,5} E2 = {(1,2),(1,3),(2,4),(3,4),(4,5)} G3 = (V3,E3) V3 = {1,2,3,4,5} E3 = {(1,2),(1,3),(2,3),(2,4),(2,5)} 4. Consider G4 and answer the following questions. (a) What is the vertex connectivity? (5%) (b) Give an arbitrary maximum clique. (5%) (c) Explain why G4 is not bupartite. (5%) G4 = (V4,E4) V4 = {a,b,c,d,e,f,g,h,i,j,k,l} E4 = {(a,b),(a,e),(a,f),(b,c),(b,g),(b,k),(c,d),(c,h),(c,l),(d,e), (d,i),(e,k),(f,g),(f,j),(g,h),(g,k),(h,i),(h,l),(i,j),(j,l)} 5. Determine the maximum total flow and a minimum cut for G5. (10%) G5 = (V5,E5) V5 = {a,b,c,d,e,f,z} G5 = {<a,b>,<a,c>,<a,d>,<b,c>,<b,d>,<b,e>,<c,d>, <c,f>,<d,e>,<d,f>,<d,z>,<e,z>,<f,e>,<f,z>} c(<a,b>) = 3, c(<a,c>) = 9, c(<a,d>) = 6, c(<b,c>) = 2, c(<b,d>) = 9, c(<b,e>) = 1, c(<c,d>) = 8, c(<c,f>) = 7, c(<d,e>) = 5, c(<d,f>) = 5, c(<d,z>) = 5, c(<e,z>) = 8, c(<f,e>) = 1, c(<f,z>) = 3 6. The following is a correctness proof for executing the Kruskal's MST algorithm on a connected graph G = (V,E), where all edges of G have distinct costs. The output of the Kruskal's algorithm is a spanning tree of G. We let T denote the spanning tree generated by the Kruskal's algorithm and T* denote an MST of G. Suppose that T and T* contain edges e1, e2, ..., e(n-1) and e*1, e*2, ..., e*(n-1), respectively, both in increasing order of costs, where n = |V|. Assume e1 = e*1, e2 = e*2, ..., e(k-1) = e*(k-1), and ek ≠ e*k, where 1 ≦ k ≦ n-1. Then, c(ek) ＜ c(e*k). After inserting ek into T*, a cycle in G is formed, in which there is one edge, denoted by e*, that is not in T and c(e*) ＞ c(ek). Then, replacing e* with ek in T* results in a spanning tree with smaller cost than T*, a contradiction. (a) Explain why c(ek) ＜ c(e*k). (5%) (b) Explain why c(e*) ＞ c(ek). (5%) 7. Suppose that T is a depth-first spanning tree of a connected graph G = (V,E) and i is a non-root vertex of T. Explain why i is an articulation point of G if i has a child j with L(i) ≧ DFN(i). (5%) 8. Suppose that G = (V,E) is a graph with n ≧ 2 vertices. Let di be the degree of vi belongs to V. Assime that di + dj ≧ n － 1 for all vi, vj belong to V and vi ≠ vj. (a) Show that G is connected. (5%) (b) A Hamltonian path in G can be obtained by the following five steps. Step 1. Arbitrarily construct a path (v1,v2), (v2,v3), ..., (v(m'-1),vm'). Step 2. Extend tha path by repeatedly adding a new vertex v to the head (or tail) if (v,v2) belongs to E ((vm',v) belongs to E). Suppose that (v1,v2), (v2,v3), ..., (v(m-1),vm) results finally. Step 3. (When m ≦ n － 1) Construct a cycle on v1, v2, ..., vm. Step 4. Extend the cycle to a path of length greater than m－1. Step 5. Repeat Step 2 to Step 4 until a Hamiltonian path results. In Step 3, a desired cycle is immediate if (v1,vm) belongs to E, or (if(v1,vm) not belongs to E) it can be obtained by removing some edge (v(t-1),vt) with (v(t-1),vt) ,(v1,vt) belong to E, where 3 ≦ t ≦ m － 1 Please explain the existence of (v(t-1),vt) (5%) 9. Suppose that G = (R∪S,E) is a bipartite graph with |R| ≦ |S| and |W| ≦ |ADJ(W)| for every W contained by R. The following is an inductive proof for G having a complete matching. Induction basis. |R| = 1. induction hypothesis. G has a complete matching when |R| ≦ m － 1. Consider the situation of |R| = m below. Case 1. |W| ＜ |ADJ(W)| for every W contained to R, or |R| = |ADJ(R)| and |W| ＜ |ADJ(W)| for every W contained to R. Arbitrarily pick (x,y) belongs to E, where x belongs to R and y belongs to S. Let G' be the graph obtained by removing x,y from G. In G', |W'| ≦ |ADJ(W')| for every W' contained to R － {x}. => G' has a complete matching by induction hypothesis. => G has a complete matching. Case 2. |W| = |ADJ(W)| for some W contained to R. Let G+(G++) be the subgraph of G induced by W∪ADJ(W) ((R－W)∪(S－ADJ(W))). In G+, |W'| ≦ |ADJ(W')| for every W' contained to W. In G++, |W''| ≦ |ADJ(W'')| for every W'' contained to R － W. => G+ and G++ each have a complete matching by induction hypothesis. => G has a complete matching. (a) What is the situation that causes |W'| = |ADJ(W')| in G'? (5%) (b) How to obtain a complete matching of G from a complete matching of G'. (5%) (c) Explain why |W''| ≦ |ADJ(W'')| for every W'' contained to R － W in G++. (5%) (d) How to obtain a complete matching of G from a complete matching of G+ and a complete matching of G++. (5%) 10. Suppose that G = (V,E) is a connected planar graph with r ＞ 1 (r is the number of regions divided by any planar drawing of G). Show that |E| ≦ 3 ×|V| － 6, by the aid of |V| － |E| + r = 2. (5%) 11. Explain why F = Σ[(x,y) belongs to E(S;S bar), f(x,y)] － Σ[(y',x') belongs to E(S bar;S), f(y',x')] can be derived from F = (Σ[v belongs to V, f(v,z)] － Σ[v' belongs to V, f(z,v')]) + (Σ[r belongs to (S bar－{z}), {Σ[v belongs to V, f(v,r)] － Σ[v' belongs to V, f(r,v')]}]) in the proof of "Condervation of Flow". (10%) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.248.143 剛剛手殘不小心按到送出= = ※ 編輯: syuusyou 來自: 140.112.248.143 (11/06 00:25)