課程名稱︰圖論一 課程性質︰選修 課程教師︰張鎮華 開課學院：理學院 開課系所︰數學所 考試日期（年月日）︰2009/11/10 考試時限（分鐘）：140 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : 1. (25%) For positive integers n >= r, define the graph Gn,r = (Vn,r, En,r) with Vn,r = {a = a1a2...an : ai belongs to {0, 1} for 1 <= i <= n} and En,r = {ab : Σ(i=1 to n) |ai -bi| = r}. (a) Determine the degrees of all vertices of the graph Gn,r. (b) Determine the number of components of the graph Gn,r (c) Determine all n and r for which the graph Gn,r has an Eular tour. 2. (25%) (a) Prove that any tree of at least two vertices has at least two leaves. (b) Prove that if v is a leaf of a tree T thebn T-v is also a tree. (c) Prove that a tree of na vertices has exactly n-1 edges. (d) Prove that if T is a tree of k edges and G is a graph in which all vertices are of degree at least k then G has a subgraph isomorphic to T. 3. (25%) (a) Prove that a bipartite graph G = (X,Y,E) has a X-perfect matching if and only if |N(S)| >= S for any S belongs to X. (b) Prove that if M is an n*n matrices of non-negative integers in which each row or each column sum up to a fixed k, then M can be express as the sum of k permutation matrices. 4. (25%) (a) Prove that a graph G = (V,E) has a perfect matching if and only if o(G-S) <= |S| for any S belongs to V, where o(G-S) is the number of odd components of G-S. (b) Does the Petersen graph have two edge-disjoint perfect matchings? If there are such perfect matchings, find them; if there are no such perfect matchings, prove it. Recall that the Petersen graph is G=(V,E) with V = {a : a belongs to {1,2,3,4,5}, |a|=2} and E = {ab : a belongs to V, b belongs to V, a∩b = φ}. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.248.143 ※ 編輯: syuusyou 來自: 140.112.248.143 (11/10 10:39)