課程名稱︰ 圖論一 課程性質︰ 數學系所選修 課程教師︰ 張鎮華 開課學院︰ 理學院 開課系所︰ 數學系所 考試日期（年月日）︰ 103年4月18日 考試時限（分鐘）︰ 6:00 AM ~ 10:00 AM 是否需發放獎勵金︰ 是 （如未明確表示，則不予發放） 試題 : 註：因下標打不出來，故用底線代替。 Midterm Exam for Graph Theory I 1. Suppose G = (V, E) is a connected graph. (a) Prove that G has a closed walk using all edges. Notice that an edge can possibly be used more than once. (b) Prove that we can further require that the closed walk found in (a) uses every edge at most twice. (c) For the case when G has exactly 2 odd vertices, describe a method (or an algorithm) to find a closed walk using all edges in G such that the length of the walk is minimum. You need to prove why the walk found is of minimum length. (d) Do the same as in (c) for a general connected graph G. If you can not do the general case, do at least for the case when G has exactly 4 odd vertices. (e) Do the same as in (d) for an edge-weighted graph G. In this cases, every length, find a closed walk whose total edge weights is minimum. 2. Suppose G = (V, E) is a multi-graph with vertex set V = {v_1, v_2, …, v_n} and edge set E = {e_1, e_2 …, e_m}. Let D = {V, E'} be an orientation of G, where e'_i = (v_i_1, v_i_2) corresponds to e_i. The incidence matrix of G is the n*m matrix I_G = [a_i,j] , where a_i,j = 1 if v_i is incident to e_j and a_i,j = 0 otherwise. The incidence matrix of D is the n*m matrix I_D = [b_i,j], where b_j1,j = 1, b_j2,j = -1 and b_i, j = 0 for all other terms. (a) Prove that for any (n-1)*(n-1) submatrix B of I_D, det B = ±1 if and only if the n-1 edges corresponding to the columns of B form a spanning tree of G. (b) Prove that for every square submatrix S of I_D, det S ∈ {0, 1, -1} (c) In (b), determine conditions for det S = αfor every α∈ {0, 1, -1} in terms of the edges corresponding to the columns of S. (d) The statement in (b) is not necessarily true if S is a square submatrix of I_G, as can be seen by the example K_3. Determine all possible values of det S for a square submatrix S of I_G. For each possible value α,determine condition for det S = αin terms of the edges corresponding the columns of S. (e) Say at least one class of graphs G for which det S ∈ {0, 1, -1} for every square submatrix S of I_G. Justify your answer. 3. For a positive integer n, the n-grid is the graph G_n = (V_n, E_n) where V_n = {(i, j): 1≦i≦n,1≦j≦n} and E_n = {{(i,j),(i',j')}: |i-i'|+|j-j'| = 1} We store the neighbors of a vertex in the dictionary order. In other words, for two neighbors (i,j) and (i',j') of some vertex, one get (i,j) before (i',j') if and only if i < i' or i = i' but j < j'. In the following algorithm. S is either a stack or a queue. In case when S is a stack, get(S) means getting the top element of S and put(v) means putting v into S as the new top element. In case when S is a queue, get(S) means getting the first element of S and put(v) means putting v into S as the new last element. initially S contains vertex (1,1) of G_n as the only element; mark(1,1); k := 0; while (S is not empty) k := k+1; v_k := get(S); for (all un-marked neighbors u of v_k in G_n) do mark u and put(u); end while; (a) For n = 10, determine k and the sequence (v_1, v_2, ..., v_k) when S is a stack. Notice that when n = 2 the sequence is (1,1), (2,1), (2,2), (1,2). (b) For n = 10, determine k and the sequence (v_1, v_2, ..., v_k) when S is a queue. Notice that when n = 2 the sequence is (1,1), (1,2), (2,1), (2,2). For the case when the size s of S is limited, put(v) may function in a strange way. We consider two possible ways. In type-1 way, when the top/last element is at position s, put(v) just simply do nothing. In type-2 way, when the top/last element is at position s, put(v) just simply put v into position s. (c) For n = 10, determine k and the sequence (v_1, v_2, ..., v_k) when S is a stack with a limited size s = 5 and the type-1 put is used. Notice that when n = 2 and s = 1 the sequence is (1,1), (1,2), (2,2). (d) For n = 10, determine k and the sequence (v_1, v_2, ..., v_k) when S is a queue with a limited size s = 10 and the type-1 put is used. Notice that when n = 2 and s = 2 the sequence is (1,1), (1,2). (e) For n = 10, determine k and the sequence (v_1, v_2, ..., v_k) when S is a stack with a limited size s = 5 and the type-2 put is used. Notice that when n = 2 and s = 1 the sequence is (1,1), (2,1), (2,2). --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.240.229 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1398499758.A.A40.html ※ 編輯: winston1907 (140.112.240.229), 04/26/2014 16:10:01