課程名稱︰圖論一 課程性質︰數學系選修 課程教師︰張鎮華 開課學院：理學院 開課系所︰數學系 考試日期︰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