课程名称︰图论二 课程性质︰数学系所选修 课程教师︰张镇华 开课学院：理学院 开课系所︰数学系所 考试日期（年月日）︰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)