電子科技大學(xué)研究生試題《圖論及其應(yīng)用》參考答案

1、電子科技大學(xué)研究生試題圖論及其應(yīng)用參考答案 電子科技大學(xué)研究生試題 圖論及其應(yīng)用( ( 參考答案) ) 考試時(shí)間：0 120 分鐘 一填空題( ( 每題 3 3 分，共 8 18 分) ) 1 1 4 4 個(gè)頂點(diǎn)的不同構(gòu)的簡單圖共有 _11_ 個(gè)； 2 2 設(shè)無向圖 g g 中有 2 12 條邊，已知 g g 中 中 3 3 度頂點(diǎn)有 6 6 個(gè)，其余頂點(diǎn)的度數(shù)均小于 3 3 。則 g g中頂點(diǎn)數(shù)至少有 _9 9 _ 個(gè)； 3 3 設(shè) n n 階無向圖是由 k(k2) 棵樹構(gòu)成的森林，則圖 g g 的邊數(shù) m= _n- - k_; 4 4 下圖 g g 是否是平面圖答 _ 是 _; 是否可 1

2、 1- - 因子分解答 _ 是 _. 5 5 下圖 g g 的點(diǎn)色數(shù) = ) (g c _, 邊色數(shù) = ¢ ) (g c _5 5 _ 。 圖 圖 g g 二單項(xiàng)選擇( ( 每題 3 3 分，共 1 21 分) ) 1 1 下面給出的序列中，是某簡單圖的度序列的是 ( a ) (a) (11123); (b) (233445); (c) (23445); (d) (1333). 2 2 已知圖 g g 如圖所示，則它的同構(gòu)圖是（ d d ） 3 3 下列圖中，是歐拉圖的是（ d d ） 4 4 下列圖中，不是哈密爾頓圖的是（b b ） 5 5 下列圖中，是可平面圖的圖的是（b b

3、） 6 6 下列圖中，不是偶圖的是（ b ） 7 7 下列圖中，存在完美匹配的圖是（ b ） 三作圖( (6 6 分) ) 1 1 畫出一個(gè)有歐拉閉跡和哈密爾頓圈的圖； 2 2 畫出一個(gè)有歐拉閉跡但沒有哈密爾頓圈的圖； 3 3 畫出一個(gè)沒有歐拉閉跡但有哈密爾頓圈的圖； 解： 四0 (10 分) ) 求下圖的最小生成樹，并求其最小生成樹的權(quán)值之和。 a b c d 1 2 3 a b c d 解：由克魯斯克爾算法的其一最小生成樹如下圖： 權(quán)和為： 20. . 五( (8 8 分) ) 求下圖 g g 的色多項(xiàng)式 p p k k (g). 解：用公式 ) ( ) ( ) ( e g p g p e

4、 g pk k k· + = - ，可得 g g 的色多項(xiàng)式： ) 3 )( 2 ( ) 1 ( ) ( ) ( 3 ) ( ) (23 4 5- - - = + + = k k k k k k k g p k 。 六0 (10 分 ) 一棵樹有 n n 2 2 個(gè)頂點(diǎn)的度數(shù)為 2 2 ，n n 3 3 個(gè)頂點(diǎn)的度數(shù)為 3 3 ，n n k k 個(gè)頂點(diǎn)的度數(shù)為k k ，而其余頂點(diǎn)的度數(shù)為 1 1 ，求 1 1 度頂點(diǎn)的個(gè)數(shù)。 解：設(shè)該樹有 n n 1 1 個(gè) 個(gè) 1 1 度頂點(diǎn)，樹的邊數(shù)為 m. 一方面： 2m=n 1 1 +2n 2 2 +kn k k 另一方面： m= n 1 1

5、 +n 2 2 +n k k - -1 1 由上面兩式可得：n n 1 1 =n 2 2 +2n 3 3 +(k- - 1)n k k 七證明：( (8 8 分) ) 設(shè) g g 是具有二分類 (x,y) 的偶圖，證明g (1)g 不含奇圈；（2 2 ）若| | x | | | | y | | ，則 g g 是非哈密爾頓圖。 證明： (1) 若不然，設(shè) c=v 1 1 v v 2 2 v m m v v 1 1 為 為 g g 的一個(gè)奇圈，不妨設(shè) v v 1 1 x, v 5v 4v 3v 2v 11v 6234568107496 圖 g 則：v v m m x, 這樣推出 v v 1 1 與

6、 與 v v m m 鄰接，與 g g 是偶圖矛盾。 (2) 若 | | x | | | | y | | ，設(shè)| | x | | | y | | ，則 (g- - y)y,由 由 h h 圖的必要條件，g g 為非哈密爾頓圖。 八（8 8 分）設(shè) g g 是邊數(shù) m m 小于 0 30 的簡單連通平面圖，證明g :g 中存在頂點(diǎn) v v ，使 d(v)4. 證明：若不然，則對任意的 vv(g),有 有 d(v)5 5 ，這樣，一方面有： 2 2 m=d(v)5n (1) 另一方面，g g 為簡單連通平面圖，有： m3n- - 6 (2) 由 (1), m n52£ , , 把該式代入

7、 (2) 得： m30, 與題設(shè)矛盾。 九( (8 8 分 ) 證明：每個(gè)沒有割邊的 3 3 正則圖都有完美匹配。 證明：設(shè) g g 是沒有割邊的 3 3 正則圖，s s 是 是 v v 的真子集，用 g g 1 1 , g 2 2 ,g n n 表示 g g- -s s 的奇分支，并設(shè) m m i i 是一個(gè)頂點(diǎn)在 g g i i 中，另一個(gè)端點(diǎn)在 s s 中的那些邊的條數(shù)。由于 g g 是 是 3 3 正則圖，所以 , ) ( 3 ) () (ig v vg v v d =åÎ 1 1 in (1) 且 s v ds v3 ) ( =åÎ （2 2 ） 由 (1) 式，åÎ- =)