課程名稱︰離散數學 課程性質︰資工系選修 課程教師︰陳健輝 開課學院：電資 開課系所︰資工系 考試日期（年月日）︰2018/06/28 考試時限（分鐘）：2hr 試題 : Examination #3 (範圍: Graph Theory) 1. Given a graph G=(V,E), is it true that G'=(V',E'), where V'⊆V and E'⊆E, is always a subgraph of G? Explain your answer. (10%) 2. Consider the following graph (Figure 11.7) and find (a) a walk of length 4 from b to d that is not a trail and (b) a circuit of length 8 from b to b that is not a cycle. (10%) Figure 11.7 b ------ e ----- f ／| |＼ | a | | ＼ | ＼| | ＼ | c ------ d g 3. How many different Hamiltonian cycles are there in K_5? (10%) 4. Please draw a graph of 6 vertices and 9 edges which has two maximum independent sets of size 3. (10%) 5. Please draw a graph with vertex connectivity 2 and edge connectivity 3. (10%) 6. Consider the following transport network N. Find the augmenting path over which the total flow of N can increase. Also find the minimum cut of N. (10%) N: b ->- j ->- k ↗ ↙ a ----->---- d ----->-------- z ↘ ↑ ↗ g -->---- h ->-- m ->- n <edge>: capacity, current flow <a,b>: 4,0 <a,g>: 3,2 <b,j>: 6,0 <g,h>: 6,2 <j,k>: 5,0 <h,d>: 4,2 <k,d>: 4,0 <h,m>: 4,0 <a,d>: 3,3 <m,n>: 8,0 <d,z>: 5,5 <n,z>: 7,0 7. Let G=(V,E) be a connected non-tree planner gragh and |E|>2. Then, |E|≦3|V|-6 can be verified as follows, where r is the number of regions partitioned by a planner drawing of G. r≦|E|/(3/2) => |V|-|E|+2|E|/3≧2 => |E|≦3|V|-6 Explain why the first two inequalities hold. (10%) 8. The following is a correctness proof for Kruskal's MST algorithm, with the assumption that all edge costs are distinct. Let T be the spanning tree of G generated by Kruskal's algorithm and T* be an MST of G. Suppose the T contains e1, e2, ..., e(n-1) and T* contains e*1, e*2, ..., e*(n-1), both in increasing order of costs, where n is the number of vertices. Assume e1=e*1, e2=e*2, ..., e(k-1)=e*(k-1), ek≠e*k, where c(ek)<c(e*k). By inserting ek into T*, a cycle is formed, where an edge (denoted by e*) not in T with c(e*)>c(ek) can be found. If e* is replaced with ek in T*, then a spanning tree with smaller cost than T* results, a contradiction. Explain why (a) c(ek)<c(e*k) and (b) c(e*)>c(ek). (10%) 9. Consider a transport network N=(V,E). Let F be a total flow of N and c(S) be the capacity of a cut induced by S, where S⊂V contains The source node. Prove that if F=c(S), then F is maximum and c(S) is minimum. (10%) 10.Consider a graph G=(V,E), where V={v1, v2, ..., vn} and n≧2. Let di be the degree of vi. Prove that if di+dj≧n-1 for every (vi,vj) not in E and vi≠vj, then G is connected. (10%) = 碎念：剛考完期中沒事做，突然想到該把上學期還沒打的題目拿來發 我相信這版上還是有些人和我一樣不是為了P幣，只是飲水思源回來讓後人乘個涼 希望站方趕快把拖很久的獎勵金問題處理好，不要忘本還浪費了這些112人的美意。 -- --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.214.108 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1541923378.A.D46.html ※ 編輯: isaswa (140.112.214.108), 11/11/2018 17:18:53 ※ 編輯: isaswa (140.112.214.108), 12/08/2018 17:28:14