→ andy74139 :已收錄至資訊系精華區!! 06/22 00:11
推 wctaiwan :也太快 圖也太精美 06/22 00:13
→ s864372002 :沒有送分題喔QQ。 06/22 19:31
推 bemyself :這次超簡單的 06/22 23:21
課程名稱︰離散數學
課程性質︰選修
課程教師︰陳健輝
開課學院：電機資訊學院
開課系所︰資工系
考試日期（年月日）︰2011/6/21
考試時限（分鐘）：2小時
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Examination #3
(範圍: Graph Theory)
1. Please draw the following graphs.
(a) a planar K(4,2). (6%)
(b) a 6-vertex strongly connected digraph with the fewest arcs. (6%)
(c) a graph whose vertex connectivity and edge connectivity are not equal.
(6%)
(d) a graph with the fewest edges that has a Hamiltonian path, but not an
Euler trail. (6%)
(e) a graph of five vertices with the most edges whose minimum vertex cover
has three vertices. (6%)
2. Does a simple graph always have an even number of odd-degree vertices?
Explain your answer. (10%)
3. For the following graph, determine a circuit, but not a cycle, from vertex
b to vertex b. (10%)
b-----e-----f
/| | ＼ \
/ | | ＼ \
a | | ＼ \
\ | | g
\| |
c-----d
4. Given a graph G=(V, E), how to determine matrices C, C^2, ..., C^|V| so
that for 1≦k≦|V|-1, C^k (i, j) represents the number of different i-to-j
walks of length k in G? (10%)
5. Determine whether or not the following two graphs are isomorphic. Explain
your answer. (10%)
a s
/|\ / \
/ | \ / \
/ b \ / t \
/ / \ \ / / \ \
c d e f u v w--x
\ \ / / \ \ / /
\ g / \ y /
\ | / \ | /
\|/ \|/
h z
6. Suppose that G=(V, E) is a connected graph. Give a sufficient and necessary
condition for an edge (i, j) in E to be a bridge, in terms of DFN(i) and
L(i). (10%)
7. Suppose that G=(V, E) is a planar graph with k connected component and r is
the number of regions in any planar drawing of G. Prove |V|-|E|+r = k+1.
(10%)
8. Suppose that f is a flow of N=(V, E) and P is an augmenting a-to-z path.
Define △p and f+ as follows:
△p = min{ min{ c(e) - f(e) | e is a forward edge },
min{ f(e) | e is a backward edge } };
f+(e) = f(e) + △p, if e is a forward edge;
f(e) - △p, if e is a backward edge;
f(e), if e is not an edge of P.
Prove that f+ is also a flow of N and the total flow of f+ is greater than
the total flow of f by △p. (10%)
9. Find the maximum total flow and a minimum cut for the following transporta-
tion network. (10%)
c1 g
↗↑＼20 ↗︱＼10
／ ︱ ↘ ／15︱ ↘
15／ 15︱ b ︱20 m1
／ ︱ ↗↑＼15︱ ↗↑＼25
／ 20 ︱／10︱ ↘↓／15︱ ↘
a————→c2 ︱15 h ︱10 z
＼ ↑＼15︱ ↗︱＼15︱ ↗
＼ ︱ ↘︱／15︱ ↘︱／25
25＼ 15︱ d ︱10 m2
＼ ︱ ↗ ＼15︱ ↗
↘︱／10 ↘↓／5
c3 j
10. Suppose that G is a weighted graph whose edge costs are all distinct. Then,
is it possible for G to have two or more distinct minimum spanning trees
(MSTs)? Explain your answer. (10%)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.226.181