推 godgunman :寫不完 ... Orz 11/10 12:17
課程名稱︰圖論一
課程性質︰選修
課程教師︰張鎮華
開課學院：理學院
開課系所︰數學所
考試日期（年月日）︰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)