[試題] 100下 陳健輝 離散數學 第三次期中考
課程名稱︰離散數學
課程性質︰資訊系選修
課程教師︰陳健輝
開課學院：電機資訊學院
開課系所︰資訊系
考試日期（年月日）︰2012/06/18
考試時限（分鐘）：100分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
1. How many edges at most are there in a bipartite graph with 20 vertices?
(10%)
2. Why does a graph G=(V,E) have an even number of vertices whose degrees are
odd? (10%)
3. Draw a graph of six vertices that has a Hamiltonian cycle, an Euler circuit,
and the fewest edges. (10%)
4. Suppose that (u,v) is an edge of a graph G and it has the least cost among
all edges that are incident to vertex v. Does every minimum spanning tree
contain (u,v) (a) when all edges have distinct costs or (b) when multiple
edges may have the same cost? Explain your answer. (10%)
5. Please provide a sufficient-and-necessary conditionfor an Euler trail, but
not an Euler circuit, in a connected graph G=(V,E), where |V|>1. (10%)
6. Please draw a graph whose vertex connectivity and edge connectivity are not
identical. (10%)
2 3 |V|-1
7. Given a graph G, how to determine 0/1 matrices B, B, B, ...,B so that for
1≦k≦|V|-1 and i≠j, B^(k) (i,j)=1 if and only if there exists an i-to-j
walk of length ≦ k in G? (10%)
8. How to modify a maximum clique algorithm (i.e., an algorithm that can find
a maximum clique of a graph) so that it can be used to find a minimum
vertex cover of a graph? (10%)
9. Suppose that p1, p2, ..., p6 denote six people, where every two people are
either familiar with or strange to each other. The following is an
incomplete proof, in terms of graph, for the fact that at least three of
p1, p2, ..., p6 can be found so that they are either familiar with or
strange to one another.
Construct an undirected G=(V,E), where V={p1,p2,...,p6} and (pi,pj)∈E if
and only if pi and pj are familiar with each other.
Two cases about an arbitrary vertex of G, say p1, are discussed below
Case 1. There are three (or more) edges incident to p1.
Without loss of generality, assume that p1 is adjacent to p2, p3, and p4.
Then, either {p2,p3,p4} forms an independent set in G, or there is a
clique of size 3 (e.g., {p1,p2,p3} if (p2,p3)∈E) in G.
Case 2. There are at most two edges incident to p1.
Please complete the discussion of Case 2. (10%)
10.Determine the maximum total flow and a minimum cut for the following
transport 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
→ suhorng :圖強耶w 06/18 18:25
推
06/18 19:31, , 1F
06/18 19:31, 1F
→
06/18 20:33, , 2F
06/18 20:33, 2F
※ 編輯: danielu0601 來自: 140.112.30.138 (06/19 15:34)
→
06/19 15:49, , 3F
06/19 15:49, 3F
→
06/19 20:29, , 4F
06/19 20:29, 4F