课程名称︰ 图论一
课程性质︰ 数学系所选修
课程教师︰ 张镇华
开课学院︰ 理学院
开课系所︰ 数学系所
考试日期（年月日）︰ 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).