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

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

2、、邊連通度、最小度之間的關(guān)系為 ；10. 對下列圖，試填下表（是類圖的打 ，否則打 ）。 能一筆畫的圖Hamilton圖偶圖可平面圖二、單項選擇(每題2分，共10分)1下面命題正確的是 ( B ) 對于序列，下列說法正確的是：(A) 是簡單圖的度序列；(B) 是非簡單圖的度序列; (C) 不是任意圖的度序列;(D) 是圖的唯一度序列.2對于有向圖，下列說法不正確的是 ( D )(A) 有向圖中任意一頂點只能處于的某一個強連通分支中；(B) 有向圖中頂點可能處于的不同的單向分支中; (C) 強連通圖中的所有頂點必然處于強連通圖的某一有向回路中;(D) 有向連通圖中頂點間的單向連通關(guān)系是等價關(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)于平面圖，下列說法錯誤的是( B )(A) 簡單連通平面圖中至少有一個度數(shù)不超過5的頂點；(B) 極大外平面圖的內(nèi)部面是三角形，外部面也是三角形；(C) 存在一種方法，總可以把平面圖的任意一個內(nèi)部面轉(zhuǎn)化為外部面；(D) 平面圖的對偶圖也是平面

4、圖。三、 (10分) 設(shè)與其補圖的邊數(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色多項式； (2). 求出的點色數(shù) ；(3). 給出一種使用種顏色的著色方法。解：(1)、圖G的補圖為：(2分).1分對于：，所以，其伴隨多項式為：.1分 所以：1分 于是色多項式= 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)、由于，所以，點色數(shù)=3；.2分(3)、點著色：(1分)六、(10分) 5個人被邀請參加橋牌比賽。橋牌比賽規(guī)則是每一場比賽由兩個2人組進行對決。要求每個2人組都要與其它2人組（W,Z ÏX,Y）進行對決。若每個人都要與其他任意一個人組成一個2人組，且每個組在同一天不能有多余一次的比賽，則最少安排多少天比賽（每一天可以有多場比賽）？請給出相應的一個時間安排表。(用圖論方法求解)解：

6、(1)、建模：5個人能夠組成10個2人組：AB, AC, AD, AE, BD, BC, BE, CD , CE, DE。 以每個2人組作為頂點，因要求每個2人組都與其它2人組比賽，所以，得到比賽狀態(tài)圖如下： 4分(2)、最少安排多少天比賽轉(zhuǎn)化為求狀態(tài)圖的邊色數(shù)。因為彼得森圖不可1因子分解，于是可推出，又可用4種色對其正常邊著色(見下圖)，所以：。所以：。 2分111222122333444(3)、安排時間表：第一天：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分 ) 由于在考試中獲得好成績，6名學生將獲得下列書籍的獎勵，分別是：代數(shù)學(a)，微積分(c)，微分方程(d)，幾何學(g)，數(shù)學史(h)，規(guī)劃學(p)，拓撲學(t)。每門科目只有1本書，而每名學生對書的喜好是：A：d, h, t ；B： h, t ；C：d, h ；D：d, t ；E：a, c, d ； F:：c, d, p, g 。每名學生是否都可以得到他喜歡的書？為什么？(用圖論方法求解)解：由題意,得模型圖：(4分)問題轉(zhuǎn)化為是否存在飽和A,B,C,D,E,F的匹配存在。 2分取頂點子集合，因，所以由霍爾定理知：不存在飽和A,B,C,D,E,F的匹配。故每名學生不能都得到他喜歡的書。 4分八、(10分) 若為偶數(shù)，且單圖G