09年圖論試題

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

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

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

4、-12-4-1x=2*17解得，x=6所以四.(10分)證明：若圖g的每個頂點的度數(shù)為偶數(shù)，則g沒有割邊。證明：若不然，假設(shè)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分)設(shè)g是一個邊賦權(quán)完全圖。如何求出g的最優(yōu)哈密爾頓圈的權(quán)值的一個下界？為什么？解：參考教材p88六(10分)求證：偶圖g存在完美匹配的充要條件是對任意的，有證明：參考教材p101七.(10分) 求證：若g是連通平面圖，且所有頂點度數(shù)不小于3，則g

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

6、、羚羊和斑馬；豪豬喜歡吃鼩鼱和兔子；而其余的則喜歡吃蟲子、蚯蚓、草或其它植物。公司將飼養(yǎng)這些動物，希望它們能自由活動但不能相互捕食。求這些動物的一個分組，使得需要的圍欄數(shù)最少。(要求用圖論方法求解)解：建立圖論模型，狒(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