[試題] 106-2 陳健輝 離散數學 期末考

[isaswa (漆黒丸)]

課程名稱︰離散數學
課程性質︰資工系選修
課程教師︰陳健輝
開課學院：電資
開課系所︰資工系
考試日期（年月日）︰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人的美意。

--
→ npn1992: 我是比較喜歡上神通啦，一直上阿武熊就要給戒指了
推 o07608: npn1992: 我是比較喜歡上神通
→ npn1992: 等等，打出去發現用詞怪怪的
→ o07608: 請問npn1992是不是過慾了
→ skalt: npn1992: 一直上阿武熊就要給戒指了   (一直上是該給戒指)
→ npn1992: 拜託不要弄簽名檔QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.214.108
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1541923378.A.D46.html
※ 編輯: isaswa (140.112.214.108), 11/11/2018 17:18:53
推 rod24574575 : 已收資訊系精華區！
※ 編輯: isaswa (140.112.214.108), 12/08/2018 17:28:14