1、本章重點本章重點一、掌握有關圖的基本概念：一、掌握有關圖的基本概念：鄰接鄰接 關聯關聯 有向圖有向圖 無向圖無向圖 n階圖階圖 底圖底圖 平行邊平行邊 多重圖多重圖 連通圖連通圖 自回路環）自回路環） 簡單圖簡單圖 二、掌握圖中頂點的度數，握手定理及其推論二、掌握圖中頂點的度數，握手定理及其推論定理：設圖定理：設圖G是具有是具有n個頂點、個頂點、m條邊的無向圖，條邊的無向圖，其中點集其中點集V=v1， v2， vn , 那么那么 niimv12)deg(握手定理握手定理)由該定理可得：由該定理可得：推論推論: 度數為奇數的頂點的個數必為偶數。度數為奇數的頂點的個數必為偶數。三、掌握有向完全圖和

2、無向完全圖及推論三、掌握有向完全圖和無向完全圖及推論2) 1( nn推論推論1： n階無向完全圖階無向完全圖Kn 共有共有 條邊。條邊。推論推論2： n階有向完全圖，階有向完全圖， 共有共有n(n-1) 條邊。條邊。四、掌握圖的同構四、掌握圖的同構五、掌握補圖及自補圖五、掌握補圖及自補圖六、掌握二部圖及完全二部圖六、掌握二部圖及完全二部圖 七、掌握求二部圖的最大匹配的方法七、掌握求二部圖的最大匹配的方法 八、掌握歐拉圖及半歐拉圖及其應用八、掌握歐拉圖及半歐拉圖及其應用思考題：思考題：1. 有有9個人一起打乒乓球，已知他們每人至少與其中另外個人一起打乒乓球，已知他們每人至少與其中另外3個人各打過

3、一場球，試證明至少有一人不止和個人各打過一場球，試證明至少有一人不止和3個人個人打過球打過球.3. 設設n階圖階圖G中有中有m條邊條邊,每個頂點的度數不是每個頂點的度數不是k就是就是k+1, 若若G中有中有Nk個個k度頂點度頂點,Nk+1個個k+1度的頂點度的頂點,試求出頂點試求出頂點個數個數Nk的表達式的表達式.2. 若無向圖若無向圖G有有12條邊，條邊，G中有中有6個個3度結點，其余結點度數度結點，其余結點度數均為均為2，問，問G中有多少個結點？中有多少個結點？4. 試畫出試畫出4階階3條邊的所有非同構的無向簡單圖條邊的所有非同構的無向簡單圖.5. 判斷下述每一對圖是否同構判斷下述每一對圖

4、是否同構?(1)(2)(3)6. 一個圖是自補圖一個圖是自補圖,設頂點數為設頂點數為n,其邊數為其邊數為m,其對應的其對應的完全圖的邊數是多少完全圖的邊數是多少?7. 設無向簡單連通圖設無向簡單連通圖G有有16條邊條邊,有有3個個4度頂點度頂點,4個個3度頂度頂點點,其余頂點的度數都小于其余頂點的度數都小于3,問問G至少有多少個頂點至少有多少個頂點,至多至多有多少個頂點有多少個頂點?8. 設設G1,G2,G3,G4均是均是4階階3條邊的無向簡單圖，條邊的無向簡單圖，則它們之間至少有幾個是同構的？則它們之間至少有幾個是同構的？10. 無向圖無向圖G中有中有9個頂點個頂點,每個頂點的度數不是每個頂

5、點的度數不是5就是就是6,證明證明:圖圖G中至少有中至少有5個個6度的頂點或至少有度的頂點或至少有6個個5度的頂點度的頂點.9. 是否存在是否存在3個頂點和個頂點和6個頂點的自補圖？個頂點的自補圖？11. 11. 設有向簡單設有向簡單D D的度數列為的度數列為2 2，2 2，3 3，3 3，入度列為，入度列為0 0，0 0，2 2，3 3，試求，試求D D的出度列。的出度列。12.12.下列各組數中不能構成無向圖的的度數列的是（下列各組數中不能構成無向圖的的度數列的是（ ）（1 11 1，1 1，2 2，3 3，5 5 （2 21 1，2 2，3 3，4 4，5 5（3 31 1，3 3，1

6、1，3 3，2 2 （4 41 1，2 2，3 3，4 4，6 613. 如圖是二部圖，求其最大匹配。如圖是二部圖，求其最大匹配。a1 a2 a3 a4b1 b2 b3 b4 b5V1V215. 當當n取何值時，完全圖取何值時，完全圖Kn是歐拉圖？是歐拉圖？16. 證明：對于任意一個無向連通圖，必能從任意證明：對于任意一個無向連通圖，必能從任意一點出發經過圖中每邊恰好兩次再回到出發點。一點出發經過圖中每邊恰好兩次再回到出發點。14.14.完全二部圖完全二部圖Km, n=(V1,V2,E)Km, n=(V1,V2,E)共有多少條邊共有多少條邊? ?1. 有有9個人一起打乒乓球，已知他們每人至少與

7、其中另外個人一起打乒乓球，已知他們每人至少與其中另外3個人各打過一場球，試證明至少有一人不止和個人各打過一場球，試證明至少有一人不止和3個人個人打過球打過球.證明證明: 用用9 個頂點個頂點vi表示表示9個人個人,頂點間的一條邊表示這兩人打頂點間的一條邊表示這兩人打過一場球過一場球,可構成一個無向圖可構成一個無向圖,若每個人僅和其余若每個人僅和其余3個人各打過個人各打過一場球，則一場球，則d(vi) =3,而此時圖而此時圖G的奇數度點是的奇數度點是9個個,即奇數個即奇數個,因此產生矛盾因此產生矛盾,于是至少有一人不止和于是至少有一人不止和3個人打過球個人打過球.思考題答案：思考題答案：2.若無

8、向圖若無向圖G有有12條邊，條邊，G中有中有6個個3度結點，其余結點度數度結點，其余結點度數均為均為2，問，問G中有多少個結點？中有多少個結點？解解:設圖中有設圖中有x個結點個結點,由握手定理可得由握手定理可得:63+(x-6) 2=212于是于是 x=9, 所以所以G中有中有9個結點個結點.3. 設設n階圖階圖G中有中有m條邊條邊,每個頂點的度數不是每個頂點的度數不是k就是就是k+1,若若G中有中有Nk個個k度頂點度頂點,Nk+1個個k+1度的頂點度的頂點,試求出頂點試求出頂點個數個數Nk的表達式的表達式. 解解:由于由于Nkk+(n-Nk)(k+1)=2m于是于是:Nk=n(k+1)-2m

9、.度數列不同度數列不同不同構不同構不同構不同構入入(出出)度列不同度列不同(3)度數列相同度數列相同但不同構但不同構解解: 根據自補圖的定義其對應的完全圖的邊數是根據自補圖的定義其對應的完全圖的邊數是2m. 6. 一個圖是自補圖一個圖是自補圖,設頂點數為設頂點數為n,其邊數為其邊數為m,其對應的其對應的完全圖的邊數是多少完全圖的邊數是多少?7. 設無向簡單連通圖設無向簡單連通圖G有有16條邊條邊,有有3個個4度頂點度頂點,4個個3度頂度頂點點,其余頂點的度數都小于其余頂點的度數都小于3,問問G至少有多少個頂點至少有多少個頂點,至多至多有多少個頂點有多少個頂點?解解: 由題設可知由題設可知,圖圖

10、G中有中有16條邊條邊,所以圖所以圖G中各點的度數中各點的度數之和為之和為32.又由于圖又由于圖G中有中有3個個4度頂點和度頂點和4個個3度頂點度頂點,這這7個點的度數個點的度數之和為之和為24,而圖而圖G中其余點的度數小于中其余點的度數小于3,即圖即圖G中其余點的中其余點的度數只可能是度數只可能是2或或1(由于圖由于圖G是連通圖是連通圖,所以無零度點所以無零度點).由此可知由此可知,圖圖G中至少有中至少有11個頂點個頂點: 3個個4度點度點,4個個3度點和度點和4個個2度點度點; 至多有至多有15個頂點個頂點: 3個個4度點度點,4個個3度點和度點和8個個1度點度點.解：解： 4階階3條邊非

11、同構的無向簡單圖共有條邊非同構的無向簡單圖共有3個，因此個，因此G1,G2,G3,G4中至少有中至少有2個是同構的。個是同構的。解解: 由于頂點為由于頂點為n的無向完全圖的邊數為的無向完全圖的邊數為 . 2) 1( nn設設G的自補圖為的自補圖為G,則則G與與G的邊數相等的邊數相等.設它們的邊數各為設它們的邊數各為m,于是有于是有m+m=2) 1( nn即即m=n(n-1)/4, 而而m為正整數為正整數,所以要么所以要么n=4k或或n=4k+1,所以不存在所以不存在3個頂點和個頂點和6個頂點的自補圖個頂點的自補圖. 9. 是否存在是否存在3個頂點和個頂點和6個頂點的自補圖？個頂點的自補圖？ 證

12、明證明:由于度數為奇數的頂點必為偶數個由于度數為奇數的頂點必為偶數個,所以度數為所以度數為5的頂的頂點個數必為偶數點個數必為偶數,即可能為即可能為0、2、4、6、8.因為總數是因為總數是9個頂個頂點點,所以所以6度的頂點個數分別為度的頂點個數分別為9、7、5、3、1,于是圖于是圖G中至中至少有少有5個個6度的頂點或至少有度的頂點或至少有6個個5度的頂點度的頂點.10. 無向圖無向圖G中有中有9個頂點個頂點,每個頂點的度數不是每個頂點的度數不是5就是就是6,證明證明:圖圖G中至少有中至少有5個個6度的頂點或至少有度的頂點或至少有6個個5度的頂點度的頂點.11. 設有向簡單設有向簡單D的度數列為的

13、度數列為2，2，3，3，入度列為，入度列為0，0，2，3，試求，試求D的出度列。的出度列。解：設有向簡單圖解：設有向簡單圖D的度數列為的度數列為2，2，3，3， 對應的頂點分別為對應的頂點分別為v1,v2,v3,v4,由于由于d(v)=d+(v)+d-(v),所以所以d+(v1)= d(v1)-d-(v1)=2-0=2,d+(v2)= d(v2)-d-(v2)=2-0=2,d+(v3)= d(v3)-d-(v3)=3-2=1,d+(v4)= d(v4)-d-(v4)=3-3=0,于是于是D的出度列為的出度列為2，2，1，0。12.12.下列各組數中不能構成無向圖的的度數列的是（下列各組數中不能

14、構成無向圖的的度數列的是（ ）（1 11 1，1 1，2 2，3 3，5 5 （2 21 1，2 2，3 3，4 4，5 5（3 31 1，3 3，1 1，3 3，2 2 （4 41 1，2 2，3 3，4 4，6 6答案2）1913. 如圖是二部圖，求其最大匹配。如圖是二部圖，求其最大匹配。 解：取二部圖的一個初始匹配M= (a1,b5),(a3,b1),(a4,b3)。 用(*)標記V1中所有M的非飽和點(只有一點a2)。 a1 a2 a3 a4b1 b2 b3 b4 b5V1V2(*) 將將(a2)的鄰接點的鄰接點b1 、b3標記為標記為(a2)。 從從b1出發，把出發，把a3標記成標記

15、成(b1)，從，從b3出發把出發把a4標記成標記成(b3)。(a2) (a2)(b1) (b3) 從從a3出發，把出發，把b4標記成標記成(a3)，因為，因為b4是非飽和點，說明已找到是非飽和點，說明已找到一條增長通路：一條增長通路：a2b1a3b4。再用增長通路中不屬于。再用增長通路中不屬于M的邊代替屬于的邊代替屬于M的邊，于是得到對集。的邊，于是得到對集。 M=(a1,b5),(a2,b1),(a3,b4),(a4,b3)。 (a3)20a1 a2 a3 a4b1 b2 b3 b4 b5V1V2(*)(a2) (a2)(b1) (b3) 從從a3出發，把出發，把b4標記成標記成(a3)，因

16、為，因為b4是非飽和點，說明已找到是非飽和點，說明已找到一條增長通路：一條增長通路：a2b1a3b4。再用增長通路中不屬于。再用增長通路中不屬于M的邊代替屬于的邊代替屬于M的邊，于是得到對集。的邊，于是得到對集。 M= (a1,b5),(a2,b1), (a3,b4),(a4,b3)。 (a3)從從 M= (a1,b5),(a2,b1), (a3,b4),(a4,b3)開場，重復上述過程，開場，重復上述過程，直到找不出直到找不出M的增長通路為止。由于的增長通路為止。由于V1中已沒有中已沒有M的非飽和點，的非飽和點，所以所以M就是所求的最大對集。就是所求的最大對集。 21a1 a2 a3 a4b1 b2 b3 b4 b5從從 M = (a1,b5),(a2,b1), ),(a3,b4),(a4,b3)開場，重復上述