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

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

2、是平面圖答 _ 是 _; 是否可 1 1- - 因子分解答 _ 是 _. 5 5 下圖 g g 的點色數(shù) = ) (g c _, 邊色數(shù) = ¢ ) (g c _5 5 _ 。 圖 圖 g g 二單項選擇( ( 每題 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 下

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

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

5、k k 另一方面： m= n 1 1 +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 的一個奇圈，不妨設(shè) v v 1 1 x, v 5v 4v 3v 2v 11v 6234568107496 圖 g 則：v v m m

6、 x, 這樣推出 v v 1 1 與 與 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 中存在頂點 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 n

7、52£ , , 把該式代入 (2) 得： m30, 與題設(shè)沖突。 九( (8 8 分 ) 證明：每個沒有割邊的 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 g i i 中，另一個端點在 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) 式，åÎ- =) () ( 2 )