推 suhorng :Conspiracy!! 04/29 20:33
→ duckingod :....囧！？ 04/29 20:38
推 DarkAkira :推 04/29 21:28
課程名稱︰圖論二
課程性質︰數學系所選修
課程教師︰張鎮華
開課學院：理學院
開課系所︰數學系所
考試日期（年月日）︰2012年 4月19日
考試時限（分鐘）：p.m 6:00 ～ 寫完為止
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Midterm Exam for Graph Theory II (2012-04-19)
(25%)
1. (a) Prove that interval graphs are chordal graphs.
(b) Give infinitely many chordal graphs that are not interal graphs.
(c) Prove that a graph G=(V,E) is an interval graph if and only if its
vertex set can be ordered into v_1, v_2, ..., v_n such that for any
i<j<k, if v_i v_k ∈ E then v_i v_j ∈ E.
(d) Prove that a graph G=(V,E) is an interval graph if and only if its
vertex set can be ordered into v_1, v_2, ..., v_n such that for any
i<j<k, if v_i v_j, v_i v_k ∈ E then v_j v_k ∈ E.
(e) Prove that chordal graphs are perfect.
(25%)
2. A graph is called split if its vertex set can be partitioned into a clique
and a stable set. _
(a) Prove that if G is split, then G and G are chordal.
_
(b) Prove that if G and G are chordal, then G contains no induced
subgraphs in {C_4,2K_2,C_5}.
(c) Prove that if G contains no induced subgraphs in {C_4,2K_2,C_5}, then
G is a split graph.
(e) Let d_1≧d_2≧...≧d_n be the degree sequence of a simple graph G, and
m is the largest value of k such that d_k≧k-1. Prove that G is
m n
split if and only if Σd_i = m(m-1) +Σ d_i.
i=1 i=m+1
(10%)
3. For a Graph G=(V,E), let Ｉ_G = {I is a subset of E: I is a stable set
of G}
(a) Find infintely many graphs G=(V,E) such that (E,Ｉ_G) is not a matroid.
(b) Determine all graphs G=(V,E) for which (E,Ｉ_G) are matroids.
(10%)
4. For a Graph G=(V,E), let Ｍ_G = {M is a subset of E: M is a matching of G}
(a) Find infintely many graphs G=(V,E) such that (E, Ｍ_G) is not a
matroid.
(b) Determine all graphs G=(V,E) for which (E, Ｍ_G) are matroids.
(10%)
5. For integers n≧k≧0, let Ｉ_n,k = {X is a subset of [n]: |X|≦k}.
(a) Prove that U(n,k)=([n],Ｉ_n,k) is a matroid. Such a matroid is called
a uniform matroid.
(b) Determine the dependent sets, the circuits, the bases and the rank
function of the uniform matroid U(n,k).
(c) Determine all uniform matroids U(n,k) which are graphical matroids.
(10%)
6. For a partition E_1, E_2, ..., E_k of E, let Ｉ = {X is a subset of E :
|X∪E_i|≦1 for 1≦i≦k}.
(a) Prove that (E,Ｉ) is a matroid. Such a matroid is called a partition
matroid.
(b) Determine the dependent sets, the circuits, the bases and the rank
function of a partition matroid.
(c) Determine all partition matroids which are graphical matroids.
(10%)
7. (a) Determine the dual of the uniform matroid U(n,k).
(b) Determine the restriction of the uniform matroid U(n,k) on the subset
[m] of [n] where m≦n.
(c) Determine the contraction of the uniform matroid U(n,k) on the subset
[m] of [n] where m≦n.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.20.219
※ 編輯: duckingod 來自: 114.44.20.219 (04/29 19:35)