离散图论部分习题课ppt课件

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)开场，重复上述