課程名稱︰離散數學
課程性質︰資訊系選修
課程教師︰陳健輝
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰2013/06/19
考試時限（分鐘）：150
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Examination #3
(範圍: Graph Theory)
1. (是非題) For each of the following statements, determine whether it is
true or false. You are NOT required to explain your answer. (80 %)
(a) There exists a graph that contains 10 vertices and 48 edges.
(b) A graph is bipartite if and only if it has no cycle of odd length.
(c) There exists a graph whose total vertex degree is 27.
(d) G' = (V', E') is a subgraph of G = (V, E), if V'⊂ V and E'⊂ E.
￣ ￣
(e) There exists a 5-regular graph whose total vertex degree is 60.
(f) Two graphs are not isomorphic, if one has articulation points and the
other has no articulation point.
(g) An n-vertex connected graph contains at least n - 1 edges.
(h) Neither articulation point nor bridge is contained in a biconnected
graph.
(i) There is a graph whose vertex connectivity is greater than edge
connectivity.
(j) If the vertex connectivity of G is k, then removing any k vertices from G
will cause G disconnected
(k) Whether a connected graph G has a Hamiltonian path or not can be decided
by examining each vertex degree of G.
(l) Given a graph G = (V,E) and its adjacency matrix A, we can find matrices
C,C^2,C^3,…, C^(|V|-1), where C^k(i, j) gives the number of different
walks of length k from vertex i to vertex j in G for all 1 ≦ k ≦ |V|-1
and i≠j, by performing some matrix operations on A.
(m) A planar drawing of a connected planar graph with 15 vertices and 34
edges may have 20 or 21 or 22 regions.
(n) If G = (V,E) is not planar, then we have |E|> 3|V| - 6.
(o) Given a bipartite graph G = (R︵S, E) with |R| ≦ |S|, |W| ≦ |ADJ(W)|
for every W ⊂ R is a necessary, but not sufficient, condition for G
￣
having a complete matching (ADJ(W) was defined in the lecture notes).
(p) Given a graph G = (V, E) and a subset V' of V, V' is a maximum clique of
_ _
G if and only if V - V' is a minimum independent set of G , where G is
the complement of G.
Sol: (a) false. (b) true. (c) false. (d) false.
(e) true. (f) true. (g) true. (h) true.
(i) false. (j) false. (k) false. (l) true.
(m) false. (n) false. (o) false. (p) false.
2. The following is an incomplete proof for the correctness of Kruskal’s MST
algorithm, where c(˙) represents the edge cost function of G and all edges
of G have distinct costs. Please provide the missing parts, i.e., (1), (2),
(3), (4) and (5). (10%)
Clearly, the output of Kruskal’s algorithm is a spanning tree of G, and
we only need to show below that the spanning tree generated by Kruskal's
algorithm has minimum cost.
Suppose that G has n vertices, and define
T : the spanning tree of G generated by Kruskal’s algorithm;
T* : an MST of G;
e_1, e_2, …, e_{n-1} : the edges of T;
e*_1, e*_2, …, e*_{n-1} : the edges of T
Assume e_1 = e*_1, e_2 = e*_2, …, e_{k-1} = e*_{k-1}, and ek ≠ e*k,
where 1 ≦ k ≦ n-1. We have c(ek) __(1)__ c(e*k), as a consequence of
Kruskal’s algorithm.After inserting __(2)__ into T*, a cycle is formed.
An edge, denoted by e*, that is not in __(3)__ can be found in this cycle,
and we have c(e*) > c(__(2)__).
If __(4)__ is replaced with __(2)__ in __(5)__, then a spanning tree with
smaller cost than __(5)__ results, a contradiction
Sol: (1) <. (2) e_k. (3) T. (4) e*. (5) T*.
3. Answer ONE (not both) of the following two problems. (10%)
(3.1) Suppose that G is a connected graph, T is a depth-first spanning tree
of G, and v is a non-root vertex of T. Please provide a sufficient-and
-necessary condition for v to be an articulation point of G, in terms
of L() and DFN(), as defined in the lecture notes.
(3.2) Please provide a sufficient-and-necessary condition for F = c(S), in
_ _
terms of f(), c(), E(S ; S), and E(S ; S), as defined in the lecture
notes.
Sol: (3.1) There exists a child u of v with L(u) ≧ DFN(v).
_
(3.2) f(e) = c(e) for each e ∈ E(S ; S) and f(e) = 0 for each
_
e ∈ E(S ; S).
4. Prove that G = (V,E) is connected, if d_i + d_j ≧ |V| - 1 for all v_i ,v_j
∈ V and vi≠vj , where d_i denotes the degree of v_i and |V| ≧ 2. (10%)
Sol: Refer to the lecture notes.
5. Find the maximum flow and minimum cut for the following transport network.
(10%)
c1 g
／︱＼20 ↗︱＼10
／ ︱ ↘ ／15︱ ↘
15↗ 15︱ b ↓20 m1
／ ︱ ↗↑＼15︱ ↗︱＼20
／ 20 ︱／10︱ ↘︱／15︱ ↘
a——→——c2 ︱15 h ↑10 z
＼ ↑＼15︱ ↗︱＼15︱ ↗
＼ ︱ ↘︱／15︱ ↘︱／25
25↘ 15︱ d ↓10 m2
＼ ︱ ↗ ＼15︱ ↗
＼︱／10 ↘︱／5
c3 j
Sol: The maximum flow is 40 and {(m1,z), (h, m2), (j, m2), (m2, m1)} is
the minimum cut.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.195
※ 編輯: benny9072004 來自: 140.112.4.195 (06/28 19:27)