[試題] 102下 張鎮華 圖論一 期中考
課程名稱︰ 圖論一
課程性質︰ 數學系所選修
課程教師︰ 張鎮華
開課學院︰ 理學院
開課系所︰ 數學系所
考試日期（年月日）︰ 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://www.ptt.cc/bbs/NTU-Exam/M.1398499758.A.A40.html
※ 編輯: winston1907 (140.112.240.229), 04/26/2014 16:10:01
推
04/26 23:24, , 1F
04/26 23:24, 1F
推
04/27 09:22, , 2F
04/27 09:22, 2F
→
04/27 09:23, , 3F
04/27 09:23, 3F