离散图论部分习题.pptVIP

**邻接关联有向图无向图n阶图底图平行边多重图连通图自回路（环）简单图一、掌握有关图的基本概念：01定理：设图G是具有n个顶点、m条边的无向图，其中点集V={v1，v2，…vn},则(握手定理)由该定理可得：推论:度数为奇数的顶点的个数必为偶数。二、掌握图中顶点的度数，握手定理及其推论02本章重点三、掌握有向完全图和无向完全图及推论推论1：n阶无向完全图Kn共有条边。推论2：n阶有向完全图，共有n(n-1)条边。四、掌握图的同构五、掌握补图及自补图六、掌握二部图及完全二部图七、掌握求二部图的最大匹配的方法八、掌握欧拉图及半欧拉图及其应用思考题：1.有9个人一起打乒乓球，已知他们每人至少与其中另外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)一个图是自补图,设顶点数为n,其边数为m,其对应的完全图的边数是多少?7.设无向简单连通图G有16条边,有3个4度顶点,4个3度顶点,其余顶点的度数都小于3,问G至少有多少个顶点,至多有多少个顶点?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，613.如图是二部图，求其最大匹配。a1a2a3a4b1b2b3b4b5V1V215.当n取何值时，完全图Kn是欧拉图？16.证明：对于任意一个无向连通图，必能从任意一点出发经过图中每边恰好两次再回到出发点。14.完全二部图Km,n=(V1,V2,E)共有多少条边?有9个人一起打乒乓球，已知他们每人至少与其中另外3个人各打过一场球，试证明至少有一人不止和3个人打过球.证明:用9个顶点vi表示9个人,顶点间的一条边表示这两人打过一场球,可构成一个无向图,若每个人仅和其余3个人各打过一场球，则d(vi)=3,而此时图G的奇数度点是9个,即奇数个,因此产生矛盾,于是至少有一人不止和3个人打过球.12思考题答案：若无向图G有12条边，G中有6个3度结点，其余结点度数均为2，问G中有多少个结点？解:设图中有x个结点,由握手定理可得:6×3+(x-6)×2=2×12于是x=9,所以G中有9个结点.设n阶图G中有m条边,每个顶点的度数不是k就是k+1,若G中有Nk个k度顶点,Nk+1个k+1度的顶点,试求出顶点个数Nk的表达式.解:由于Nk×k+(n-Nk)×(k+1)=2m于是:Nk=n(k+1)-2m.试画出4阶3条边的所有非同构的无向简单图判断下述每一对图是否同构:度数列不同不同构不同构入(出)度列不同度数列相同但不同构解:根据自补图的定义其对应的完全图的边数是2m.一个图是自补图,设顶点数为n,其边数为m,其对应的完全图的边数是多少?02017.设无向简单连通图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度点和