《离散图论部分习题.ppt》由会员分享，可在线阅读，更多相关《离散图论部分习题.ppt（22页珍藏版）》请在三一办公上搜索。
1、本章重点,一、掌握有关图的基本概念：邻接 关联 有向图 无向图 n阶图 底图 平行边 多重图 连通图 自回路（环）简单图,二、掌握图中顶点的度数，握手定理及其推论,定理：设图G是具有n个顶点、m条边的无向图，其中点集V=v1，v2，vn,则,(握手定理),由该定理可得：推论:度数为奇数的顶点的个数必为偶数。,三、掌握有向完全图和无向完全图及推论,推论1：n阶无向完全图Kn 共有 条边。,推论2：n阶有向完全图，共有n(n-1)条边。,四、掌握图的同构,五、掌握补图及自补图,六、掌握二部图及完全二部图,七、掌握求二部图的最大匹配的方法,八、掌握欧拉图及半欧拉图及其应用,思考题：,1.有9个人一起
2、打乒乓球，已知他们每人至少与其中另外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.判断下述每一对图是否同构?,(1),(2),(3),6.一个图是自补图,设顶点数为n,其边数为m,其对应的完全图的边数是多少?,7.设无向简单连通图G有16条边,有3个4度顶点,4个3度顶点,其余顶点的度数都小于3,问G至少有多少
3、个顶点,至多有多少个顶点?,8.设G1,G2,G3,G4均是4阶3条边的无向简单图，则它们之间至少有几个是同构的？,10.无向图G中有9个顶点,每个顶点的度数不是5就是6,证明:图G中至少有5个6度的顶点或至少有6个5度的顶点.,9.是否存在3个顶点和6个顶点的自补图？,11.设有向简单D的度数列为2，2，3，3，入度列为0，0，2，3，试求D的出度列。,12.下列各组数中不能构成无向图的的度数列的是（）（1）1，1，2，3，5（2）1，2，3，4，5（3）1，3，1，3，2（4）1，2，3，4，6,13.如图是二部图，求其最大匹配。,15.当n取何值时，完全图Kn是欧拉图？,16.证明：对于
4、任意一个无向连通图，必能从任意一点出发经过图中每边恰好两次再回到出发点。,14.完全二部图Km,n=(V1,V2,E)共有多少条边?,1.有9个人一起打乒乓球，已知他们每人至少与其中另外3个人各打过一场球，试证明至少有一人不止和3个人打过球.,证明:用9 个顶点vi表示9个人,顶点间的一条边表示这两人打过一场球,可构成一个无向图,若每个人仅和其余3个人各打过一场球，则d(vi)=3,而此时图G的奇数度点是9个,即奇数个,因此产生矛盾,于是至少有一人不止和3个人打过球.,思考题答案：,2.若无向图G有12条边，G中有6个3度结点，其余结点度数均为2，问G中有多少个结点？,解:设图中有x个结点,由
5、握手定理可得: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.,4.试画出4阶3条边的所有非同构的无向简单图5.判断下述每一对图是否同构:(1),度数列不同不同构,(2),不同构入(出)度列不同,(3),度数列相同但不同构,解:根据自补图的定义其对应的完全图的边数是2m.,6.一个图是自补图,设顶点数为n,其边数为m,其对应的完全图的边数是多少?,7.设无向简单连通图
6、G有16条边,有3个4度顶点,4个3度顶点,其余顶点的度数都小于3,问G至少有多少个顶点,至多有多少个顶点?,解:由题设可知,图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度点.,8.设G1,G2,G3,G4均是4阶3条边的无向简单图，则它们之间至少有几个是同构的？,解：4阶3条边非同构的无向简单图共有3个
7、，因此G1,G2,G3,G4中至少有2个是同构的。,解:由于顶点为n的无向完全图的边数为.,设G的自补图为G,则G与G的边数相等.,设它们的边数各为m,于是有m+m=,即m=n(n-1)/4,而m为正整数,所以要么n=4k或n=4k+1,所以不存在3个顶点和6个顶点的自补图.,9.是否存在3个顶点和6个顶点的自补图？,证明:由于度数为奇数的顶点必为偶数个,所以度数为5的顶点个数必为偶数,即可能为0、2、4、6、8.因为总数是9个顶点,所以6度的顶点个数分别为9、7、5、3、1,于是图G中至少有5个6度的顶点或至少有6个5度的顶点.,10.无向图G中有9个顶点,每个顶点的度数不是5就是6,证明:
8、图G中至少有5个6度的顶点或至少有6个5度的顶点.,11.设有向简单D的度数列为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.下列各组数中不能构成无向图的的度数列的是（）（1）1，1，2，3，5（2）1，2，3，4
9、，5（3）1，3，1，3，2（4）1，2，3，4，6,答案（2）,19,13.如图是二部图，求其最大匹配。,解：取二部图的一个初始匹配M=(a1,b5),(a3,b1),(a4,b3)。用(*)标记V1中所有M的非饱和点(只有一点a2)。,(*),将(a2)的邻接点b1、b3标记为(a2)。,从b1出发，把a3标记成(b1)，从b3出发把a4标记成(b3)。,(a2)(a2),(b1)(b3),从a3出发，把b4标记成(a3)，因为b4是非饱和点，说明已找到一条增长通路：a2b1a3b4。再用增长通路中不属于M的边代替属于M的边，于是得到对集。M=(a1,b5),(a2,b1),(a3,b4)
10、,(a4,b3)。,(a3),20,(*),(a2)(a2),(b1)(b3),从a3出发，把b4标记成(a3)，因为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就是所求的最大对集。,21,从 M=(a1,b5),(a2,b1),),(a3,b4),(a4,b3)开始，重复上述过程，直到找不出M的增长通路为止。由于V1中已没有M的非饱和点，所以M就是所求的最大对集。,22,14.完全二分图Km,n=(V1,V2,E)共有多少条边?,解:因为V1中每个顶点都与V2 中每个顶点邻接,所以V1 中每个顶点关联|V2|=n 条边;而V1 中有m个顶点,所以Km,n共有mn条边。,
