作者syuusyou (syuusyou)
看板NTU-Exam
标题[试题] 97上 陈健辉 离散数学 期中考
时间Thu Nov 6 00:16:34 2008
课程名称︰离散数学
课程性质︰系必修
课程教师︰陈健辉
开课学院:电资学院
开课系所︰资讯系
考试日期(年月日)︰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)