電子科大12年研究生圖論試卷

1、學(xué) 號(hào) 姓 名 學(xué) 院 密封線以內(nèi)答 題無效 電子科技大學(xué)研究生試卷 （考試時(shí)間： 至 ，共_2_小時(shí)）課程名稱 圖論及其應(yīng)用 教師 學(xué)時(shí) 60 學(xué)分 教學(xué)方式 講授 考核日期_2012_年_月_日 成績(jī) 考核方式： （學(xué)生填寫） 一、填空題（填表題每空1分，其余每題2分，共30分)1階正則圖G的邊數(shù)=；23個(gè)頂點(diǎn)的不同構(gòu)的簡(jiǎn)單圖共有個(gè)；3邊數(shù)為的簡(jiǎn)單圖的不同生成子圖的個(gè)數(shù)有個(gè)； 4. 圖與圖的積圖的邊數(shù)為；5. 在下圖中，點(diǎn)到點(diǎn)的最短路長(zhǎng)度為；6. 設(shè)簡(jiǎn)單圖的鄰接矩陣為，且，則圖的邊數(shù)為；7. 設(shè)是n階簡(jiǎn)單圖，且不含完全子圖，則其邊數(shù)一定不會(huì)超過；8的生成樹的棵數(shù)為; 9. 任意圖的點(diǎn)連通度

2、、邊連通度、最小度之間的關(guān)系為 ；10. 對(duì)下列圖，試填下表（是類圖的打 ，否則打 ）。 能一筆畫的圖Hamilton圖偶圖可平面圖二、單項(xiàng)選擇(每題2分，共10分)1下面命題正確的是 ( B ) 對(duì)于序列，下列說法正確的是：(A) 是簡(jiǎn)單圖的度序列；(B) 是非簡(jiǎn)單圖的度序列; (C) 不是任意圖的度序列;(D) 是圖的唯一度序列.2對(duì)于有向圖，下列說法不正確的是 ( D )(A) 有向圖中任意一頂點(diǎn)只能處于的某一個(gè)強(qiáng)連通分支中；(B) 有向圖中頂點(diǎn)可能處于的不同的單向分支中; (C) 強(qiáng)連通圖中的所有頂點(diǎn)必然處于強(qiáng)連通圖的某一有向回路中;(D) 有向連通圖中頂點(diǎn)間的單向連通關(guān)系是等價(jià)關(guān)系。

3、3.下列無向圖可能不是偶圖的是 ( D )(A) 非平凡的樹； (B) 無奇圈的非平凡圖；(C) 方體；注意：n方體是n正則二部圖。(D) 平面圖。4.下列說法中正確的是 ( C )(A) 連通3正則圖必存在完美匹配；(B) 有割邊的連通3正則圖一定不存在完美匹配；(C) 存在哈密爾頓圈的3正則圖必能1因子分解；(D) 所有完全圖都能作2因子分解。5. 關(guān)于平面圖，下列說法錯(cuò)誤的是( B )(A) 簡(jiǎn)單連通平面圖中至少有一個(gè)度數(shù)不超過5的頂點(diǎn)；(B) 極大外平面圖的內(nèi)部面是三角形，外部面也是三角形；(C) 存在一種方法，總可以把平面圖的任意一個(gè)內(nèi)部面轉(zhuǎn)化為外部面；(D) 平面圖的對(duì)偶圖也是平面

4、圖。三、 (10分) 設(shè)與其補(bǔ)圖的邊數(shù)分別為，求的階數(shù)。解：設(shè)的階數(shù)為。因4分所以：.2分得：.4分四、(10分) 求下圖的最小生成樹（不要求中間過程，只要求畫出最1 2 3v7v6v1v2v6V7小生成樹, 并給出T的權(quán)和）。2 44 3 5 1 66 5v4v3v4v5V7v6v5v4v3v2v1v4v6v76 54 3 5 1 62 41 2 3五、(10分) (1). 求下圖的k色多項(xiàng)式； (2). 求出的點(diǎn)色數(shù) ；(3). 給出一種使用種顏色的著色方法。解：(1)、圖G的補(bǔ)圖為：(2分).1分對(duì)于：，所以，其伴隨多項(xiàng)式為：.1分 所以：1分 于是色多項(xiàng)式= k (k-1) (k-2)

5、2+4(k-3) +(k-3) (k-4) = k(k-1)2 (k-2)2 2分解法2 2分 + = (k-1) 3分= (k-1) k(k-1) (k-2)2= k(k-1)2 (k-2)2 2分 (2)、由于，所以，點(diǎn)色數(shù)=3；.2分(3)、點(diǎn)著色：(1分)六、(10分) 5個(gè)人被邀請(qǐng)參加橋牌比賽。橋牌比賽規(guī)則是每一場(chǎng)比賽由兩個(gè)2人組進(jìn)行對(duì)決。要求每個(gè)2人組都要與其它2人組（W,Z ÏX,Y）進(jìn)行對(duì)決。若每個(gè)人都要與其他任意一個(gè)人組成一個(gè)2人組，且每個(gè)組在同一天不能有多余一次的比賽，則最少安排多少天比賽（每一天可以有多場(chǎng)比賽）？請(qǐng)給出相應(yīng)的一個(gè)時(shí)間安排表。(用圖論方法求解)解：

6、(1)、建模：5個(gè)人能夠組成10個(gè)2人組：AB, AC, AD, AE, BD, BC, BE, CD , CE, DE。 以每個(gè)2人組作為頂點(diǎn)，因要求每個(gè)2人組都與其它2人組比賽，所以，得到比賽狀態(tài)圖如下： 4分(2)、最少安排多少天比賽轉(zhuǎn)化為求狀態(tài)圖的邊色數(shù)。因?yàn)楸说蒙瓐D不可1因子分解，于是可推出，又可用4種色對(duì)其正常邊著色(見下圖)，所以：。所以：。 2分111222122333444(3)、安排時(shí)間表：第一天：AB-DE, AE-BC, AC-BE, AD-CE; 第二天：AB-CE, AC-DE, AE-BD, AD-BC, BE-CD ;第三天：AB-CD, BC-DE, BD-C

7、E;第四天：AC-BD, AD-BE, AE-CD。 4分七、(10分 ) 由于在考試中獲得好成績(jī)，6名學(xué)生將獲得下列書籍的獎(jiǎng)勵(lì)，分別是：代數(shù)學(xué)(a)，微積分(c)，微分方程(d)，幾何學(xué)(g)，數(shù)學(xué)史(h)，規(guī)劃學(xué)(p)，拓?fù)鋵W(xué)(t)。每門科目只有1本書，而每名學(xué)生對(duì)書的喜好是：A：d, h, t ；B： h, t ；C：d, h ；D：d, t ；E：a, c, d ； F:：c, d, p, g 。每名學(xué)生是否都可以得到他喜歡的書？為什么？(用圖論方法求解)解：由題意,得模型圖：(4分)問題轉(zhuǎn)化為是否存在飽和A,B,C,D,E,F的匹配存在。 2分取頂點(diǎn)子集合，因，所以由霍爾定理知：不存在飽和A,B,C,D,E,F的匹配。故每名學(xué)生不能都得到他喜歡的書。 4分八、(10分) 若為偶數(shù)，且單圖G