課程名稱︰離散數學 課程性質︰選修 課程教師︰陳健輝 開課學院：電機資訊學院 開課系所︰資工系 考試日期（年月日）︰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