1、電子科技大學圖論及其應用 09年研究生試卷答案 by xjia version1.0 2013年6月19日學號姓名學院密封線以內答題無效電子科技大學研究生試卷（考試時間：至，共_2_小時）課程名稱圖論及其應用教師學時60 學分教學方式講授考核日期_2009_年_月_日成績考核方式：（學生填寫）一填空題(每題2分，共20分)1n(n-1)4取整數若自補圖g的頂點數是10，則g的邊數=_12_；2若圖，則它們的積圖的頂點數=n1n2;邊數=n1m2+n2m1；3具有m條邊的簡單圖的子圖個數為2m；4設g=kn,n,則其最大特征值為_n_; 5. 設g是n階的完全l等部圖，則其邊數m(g)=n(n-

2、1)2;13265236.1+2+2+3下圖g1中最小生成樹的權值為_8_;7. 6階度極大非哈密爾頓圖族是c1,6, c2,6,c3,6;g18. k9的2因子分解的數目是_4_；9. n（n3）階極大外平面圖內部面個數為_n-2；3階以上的極大平面圖的邊數m和頂點數n的關系為_m=3n-6;g210.邊色數三個推論見教材p150。點色數采用著色算法。下圖g2的點色數為_3_;邊色數為_4_。二單項選擇(每題3分，共12分)1下面給出的序列中，不是某圖的圖序列的是( d )(a) (11123); (b) (22222); (c) (3333); (d) (1333).2. 下列有向圖中是強

3、連通圖的是( a )3.關于n方體qn(n3)，下面說法不正確的是( d )(a) qn是正則圖； (b) qn是偶圖；(c) qn存在完美匹配；(d) qn是歐拉圖。4教材p145習題26前提g是連通圖.關于平面圖g和其幾何對偶圖g*的關系，下列說法中不正確的是( c )(a)平面圖g的面數等于其對偶圖的頂點數；(b)平面圖g的邊數等于其對偶圖的邊數；(c)平面圖,其中表示g的對偶圖；(d)平面圖的對偶圖是連通平面圖。三. (10分)設根樹t有17條邊，12片樹葉，4個4度內點，1個3度內點，求t的樹根的度數。解：m=n-1，則n=18；設樹根的度數為x，得等式12*1+4*4+1*3+18

4、-12-4-1x=2*17解得，x=6所以四.(10分)證明：若圖g的每個頂點的度數為偶數，則g沒有割邊。證明：若不然，假設g中割邊uv，從而在g-uv中不存在從u到v的路。因為圖g中du=2, dv=2,g-e中du=1, dv=1，進而v與v1是連通的，又 dv1=dv2=dvk=2，所以必定存在路vv1v2vku使得uv連通。矛盾。所以五(10分)設g是一個邊賦權完全圖。如何求出g的最優哈密爾頓圈的權值的一個下界？為什么？解：參考教材p88六(10分)求證：偶圖g存在完美匹配的充要條件是對任意的，有證明：參考教材p101七.(10分) 求證：若g是連通平面圖，且所有頂點度數不小于3，則g

5、至少有一個面 ，使得。證明：設def(f)>6，則由2m=fdegf6又n-m+=k+1k=1=2-n+mm3，于是的2m3n-6。另一方面，又(g)3得，2m3n>3n-6。這樣導出矛盾，所以原證明得證。八.(10分)一家公司計劃建造一個動物園，他們打算飼養下面這些動物：狒狒(b)、狐貍(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、獅子(l)、豪豬(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑馬(z)。根據經驗，動物的飲食習慣為：狒狒喜歡吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱；狐貍喜歡吃山羊、豪豬、兔子和鼩鼱；土狼喜歡吃山羊、非洲大羚羊、羚羊和斑馬；獅子喜歡吃山羊、非洲大羚羊

6、、羚羊和斑馬；豪豬喜歡吃鼩鼱和兔子；而其余的則喜歡吃蟲子、蚯蚓、草或其它植物。公司將飼養這些動物，希望它們能自由活動但不能相互捕食。求這些動物的一個分組，使得需要的圍欄數最少。(要求用圖論方法求解)解：建立圖論模型，狒(b)、狐貍(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、獅子(l)、豪豬(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑馬(z)。b->f, h, l, p, z; f->b, h, k, l, w, z;h->b, f, l, p, r, s; l->b, f, h, p, r, s;p->b, g, h, k, l, w, z; 略九(8分)求下圖g的色多項式pk(g).解：該圖的補圖g如下圖所示： h2 h1它有兩個分支，對于hk1,x=x+x