课程名称︰离散数学 课程性质︰资工系选修 课程教师︰陈健辉 开课学院：电资 开课系所︰资工系 考试日期（年月日）︰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/cn.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