課程名稱︰圖論一
課程性質︰數學系選修
課程教師︰張鎮華
開課學院：理學院
開課系所︰數學系
考試日期︰2011年11月10日
考試時限：240分鐘，早上6:00-10:00
是否需發放獎勵金：是
試題 :
Midterm Exam for Graph Theory I (2011-11-10)
1. (25%) Suppose c:c1≧c2≧...≧cm and d:d1≧d2≧...≧dn are two sequences of
non-negative integers. We call that c and d are bipartite graphic(respectively,
bipartite multi-graphic) if ther is a bipartite graph (respectively, bipartite
multi-graph) G=(X,Y,E), where X={x1,x2,...,xm} and Y={y1,y2,...,yn}, such that
deg_G (xi) = ci for xi∈X and deg_G (yj) for yjx∈Y.
(a) Prove that c and d are bipartite multi-graphic if and only if Σci = Σdj
(b) Prove that c and d are bipartite graphic if and only if c' and d' are
bipartite grapgic, where c' is c2,c3,...c,m and d' is d1 - 1,d2 -1,...,
d_(c1) -1 , d_(c1 +1) ,...,dn
2. (25%) Suppose the mn cells of an m-by-n chessboard B_(m,n) are coordinated
by (i,j) for 1≦i≦m and 1≦j≦n. Denote B_(m,n) (i,j)
(resp., B_(m,n) (i,j;i',j')) the partial chessboard obtained from B_(m,n)
by omitting the cell (i,j) (resp., cells (i,j) and (i',j')).
(a) For mn odd, determine all (i,j) for which B_(m,n) (i,j) can be partitioned
into 1-by-2 and 2-by-1 rectangles. Justify your answer.
(b) For mn even, determine all (i,j;i'j') for which B_(m,n) (i,j;i',j') can be
partitioned into 1-by-2 and 2-by-1 rectangles. Justify your answer.
3. (25%) (a) Prove that a graph is a tree if and only if for any two vertices
in the graph there is exactly one path between them.
(b) A weighted graph is a graph G=(V,E) in which every edge e has a positiv
-e real weight w(e). The w-distance d_w (x,y) from a vetex x to another ver
-tex y is the minimum weight sum [Σw(e),where e∈P], where P runs over all
path P from x to y.
The w-eccentricity of a vertex x is e_w (x) =max [d_w (x,y)], where y∈V.
The w-radius of G is rad_w (G) = min[e_x (x)], where x∈V.
A w-center is a vertex x with e_w (x) = rad_w (G).
Prove that in a weighted tree T, either there is exactly one w-center or
else there are exactly two w-centers which are adjacent.
4. (25%) A fractional perfect matching of a graph G=(V,E) is a function
f:E→R^+, the set of all non-negative reals, such that [Σf(e)=1,x∈e]
for any vertex x. It is clear that a fractional perfect matching f correspo
-nds to a perfect matching if and only if it is integer valued, or equivale
-ntly f is a 0-1 function. We use F(f) to denote the number of edges e for
which 0<f(e)<1.
(a) Prove that P_M (G):={f : f is a fractional perfect matching of G} is a conv
-ex set, i.e., f,g∈P_M (G) amd 0≦λ≦1 imply λf+(1-λ)g∈P_M (G).
(b) Notice that P_M (G) may be empty. If G=(X,Y,E) is a bipartite graph with
non-empty P_M (G), prove that |X|=|Y|.
(c) For any n≧3, give a non-bipartite graph G_n of n vertices for which
P_M (G_n) is not empty. Justify your answer.
(d) Prove that if f is a fractional perfect matching of a bipartite graph G
with F(f)>0, then there are fractional perfect matchings g and h with
F(g) < F(f) and F(h) < F(f) and 0<λ<1 such that f=λg+(1-λ)h.
(Hint: find a cycle all of whose edges are of non-integral weights.)
(e) An extremal point of a convex set C ⊂＝ R^m is point x∈C such that there
exist no distint y,z∈C and 0<λ<1 with x=λy+(1-λ)z.
Prove that a 0-1 fractional perfect matching is an extremal point of P_M(G)
. Give examples to show that the converse is not necessarily true, and just
-ify your answer. However, if G is bipartite, prove that all extremal point
-s of P_M (G) are 0-1 valued.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.252.31