課程名稱︰離散數學
課程性質︰系必修
課程教師︰陳健輝
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰2010/01/13
考試時限（分鐘）：120
是否需發放獎勵金：是，thank you
（如未明確表示，則不予發放）
試題 :
(Unless specified particularly, all graphs are simple and undirected.)
1.Suppose G={V,E},where V={1,2,3,4,5,6,7} and E={(1,3),(1,4),(1,6),
(2,3),(2,5),(2,7),(3,7),(4,6),(4,7),(5,6)}.
(a) Is G a regular graph? (2%)
(b) Is G a complete graph? (2%)
(c) Is G a simple graph? (2%)
(d) Is G'=({1,2,4,5},{(1,4),(2,5),(5,6)}) a subgraph of G? (2%)
(e) Is the subgraph of G induced by {2,4,5,6,7} biconnected? (2%)
2.Suppose that G=(Vg,Eg) and H=(Vh,Eh) are two isomorphic graphs.Which of
the following statements are correct? (5%)
(a) |Vg|=|Vh| and |Eg|=|Eh|.
(b) If G has aHamiltonian path, then H has a Hamiltonian path.
(c) If G is not planar, then H is not planar.
(d) If G has a matching of size k, then H has a matching of size k.
(e) G and H have the same chromatic number.
3.Please give a necessary and sufficient condition for a graph G to be
bipartite. (5%)
4.Explain why every n-vertex strongly connected digraph contains at least n
arcs. (5%)
5.The following is a correctness proof of Kruskal's MST algorithm for the
restricted case where all edge costs are distinct. Please extend the proof
for the general case where two or more distinct edges are allowed to have
the same cost (10%)
↓
Let T be the spanning tree of G geberated by Krusakl's algorithm and T*
be the minimum spanning tree of G.
Suppose that T contains e1,e2,...,en-1 and T* contains e1*,e2*,...,en-1*,
both in increasing order of costs,where n is the number of vertices.
Assume e1=e1*,e2=e2*,...,en-1=en-1*, and ek≠ek*,where c(ek)<c(ek*).
when ek is inserted into T*, a cycle is formed, where there is one edge,
denoted by e*, that is not in T and c(e*)>c(ek).
Then, replacing e* with ek will result in a spanning tree with less cost than
T*, a contradiction.
6.Please draw a graph whose vertex connectivity and edge connectiveity are not
identical. (5%)
7.Suppose that i is a node og a connected graph G. Please suggest a sufficient
and necessary condition for i to be an articulation point of G, using the
notations DFN(i) and L(i), as defined in lecture notes. (5%)
8.Suppose that G=(V,E) is a directed graph and there is one arc <u,v> or <v,u>
between every two vertices u,v of G. Prove there is a directed Hamiltonian
path in G. (10%)
9.Suppose that A is a 0/1 matrix that represents the transitive closure of a
graph G. What does "A(i,j)=1"mean? What does "A(i,j)=0" mean? (5%)
10.Suppose that G=(V,E) is a connected planar graph.Prove that |E|≦3|V|-6 for
|E|≧2. (10%)
11.Suppose that G(R︶S,E) is a bipartite graph, where |R|<|S| is assumed.
Please suggest a sufficient and necessary condition fo G having a complete
matching. (5%)
12.For the following graph,how many maximal cliques of size 3 are there,and
what is the size of maximum independent sets? (5%)
。
╱ ＼
╱ ＼
。—————。
／∣＼ ／∣＼
／ ｜ ＼ ／ ｜ ＼
。 ｜ ╳ ｜ 。
＼ ｜ ／ ＼ ｜ ／
＼｜／ ＼∣／
。 。
＼ ／
＼ ／
。
13.The following is a proof for "Conservation of Flow" ,i.e.,
F=Σ f(x,y) -Σ f(y',x').
_ _
(x,y)∈E(S;S) (y',x')∈(S;S)
F=Σ f(v,z) -Σ f(z,v').
(x∈V) (v'∈V).
_
For any r∈S - {z},
+ -
Ψ (r)=Σ f(v,r) =Σf(r,v')=Ψ (r).
v∈V v'∈V
According to (1) and (2),
F=(Σ f(v,z)-Σ f(z,v') +
v∈V v'∈V
Σ (Σ f(v,r) -Σ f(r,v'), (3)
_
r∈S-{z} v∈V v'∈V
which can be rewritten as
F=Σ f(s,y) - Σ f(y',x'). (4)
_ _
(x,y)∈E (S;S) (y',x')∈(S;S)
Explain why (3) can be rewritten as (4) (10%)
14.Determine the maximum total flow and a minimum cut for the following
transport network. (10%)
ⓑ——６→ⓔ
↗ ↖ ↗↑╲
５ 3 2 1 11
╱ ╳ ｜ ＼
╱ ╱ ╲ ｜ ↘
ⓐ——６→ⓒ ⓕ—２—→ⓗ
＼ ↑ ╲ ↗ ↗
８ ４ ╳ 7
╲ ∣ 6 5 ／
╲｜╱ ＼ ／
ⓓ——5—→ⓖ
圖畫的有點醜
不過看的懂應該就好了
--
大家每天都要開開心心的過喔!!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.6.232