[試題] 102下 陳健輝 離散數學 期末考
課程名稱︰離散數學
課程性質︰資訊系選修
課程教師︰陳健輝
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰2014/06/20
考試時限（分鐘）：120
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Examination #3
(範圍: Graph Theory)
(滿分120，第13題是雪中送炭題)
(Unless specified explicitly, all graphs below are simple.)
1. Find the possibly maximal number of edges contained in (a) a bipartite
graph with 12 vertices and (b) a planar graph with 5 vertices. (5%, 5%)
2. Explain why the following two graphs are not isomorphic. (10%)
a s
/|\ / \
/ | \ / \
/ b \ / t \
/ / \ \ / / \ \
c d e f u v w--x
\ \ / / \ \ / /
\ g / \ y /
\ | / \ | /
\|/ \|/
h z
3. Give a method to determine whether a graph is bipartite or not. Your method
must be easily convertible into a program. (10%)
4. Please draw a graph whose vertex connectivity and edge connectivity are not
identical. (10%)
5. The following is a correctness proof for Kruskal's MST algorithm, where a
weighted graph G is concerned and all edge costs of G are distinct. Please
answer the following two questions: (a) why c(e_k) < c(e*_k)?
(b) why c(e*) > c(e_k)? (5%, 5%)
Let T be the spanning tree generated by Kruskal's algorithm, and T*
be an MST of G.
Suppose that T contains edges e_1, e_2, ... , e_n-1 and T* contains
edges e*_1 e*_2, ... , e*_n-1, both in increasing order of costs,
where n is the number of vertices in G.
Assume e_1 = e*_1, e_2 = e*_2, ..., e_k-1 = e*_k-1, e_k ≠ e*_k, where
1≦k≦n-1.
Then, we have c(e_k) < c(e*_k), where c(e_k) is the cost of e_k.
After inserting e_k into T*, a cycle is formed and an edge, say
e*, that is not in T can be found in this cycle, where c(e*) > c(e_k).
If e* is replaced with e_k in T*, then a spanning tree with smaller
cost than T* results, a contradiction.
6. How many different Hamiltonian cycles are there in K_n? (10%)
7. Given a digraph G, where there is a one arc between every two vertices of
G, prove that there exists a directed Hamiltonian path in G. (10%)
8. Let G=(V, E) be a connected planar graph and r be the number of regions
divided by any planar drawing of G. The following is a proof that
|E|≦ 3|V|-6 holds for |E|≧2 and r > 1. Please answer the following two
questions: (a) why r≦|E|/(3/2)? (b) why |V|-|E|+2|E|/3≧2? (5%, 5%)
r≦|E|/(3/2) = 2|E|/3
=> |V|-|E|+2|E|/3≧2
=> |E|≦3|V| - 6
9. Consider a transport network N=(V, E). Let F be a total flow of N and
c(S) be the capacity of the cut induced by S, where S ⊂V contains the
source node. Prove that F=c(S) if and only if F is maximum and c(S) is
minimum. (10%)
10. Consider the following transport network N. Find the augmenting paths over
which the total flow of N can increase. Also find the minimum cut of N.
(5%, 5%)
6,0 5,2
b------->j------->k
4,0 ↗ / 4,0
/ ↙
a---------------->d------------------>z
\ 3,3 ↑ 5,5 ↗
3,2 \ 4,2∣ / 7,0
↘ ∣ /
g----------->h------->m----->n
6,2 4,0 8,0
11. Is there a complete matching in the following bipartite graph G=(R∪S,
E)? Find any, if exists, or give your reason otherwise. (10%)
http://ppt.cc/xLJV 挑戰ANSI失敗QQ
12. Let G=(V, E) be an undirected graph. Define a relation R on V as follows:
a R b iff a=b or there is an a-to-b path in G. Clearly, R is an equivale-
nce relation. Suppose that G1, G2, ..., Gk are the subgraphs of G induced
by all equivalence classes of R.
Then, what are G1, G2, ..., Gk in graph terms? (10%)
13. 在電影"美麗人生"中，最後小男孩相信他從遊戲中勝出且贏得獎品。請回答獎品是
什麼? (10%)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.74.170
※ 文章網址: http://www.ptt.cc/bbs/NTU-Exam/M.1403272728.A.61A.html
※ 編輯: arbuztw (123.193.74.170), 06/20/2014 22:04:21
※ 編輯: arbuztw (123.193.74.170), 06/21/2014 10:28:55
→
06/21 11:52, , 1F
06/21 11:52, 1F
推
06/21 14:23, , 2F
06/21 14:23, 2F
→
06/21 14:40, , 3F
06/21 14:40, 3F