图论张先迪李正良课后习题答案 .doc

《图论张先迪李正良课后习题答案 .doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.证明：在n阶连通图中(1)至少有n-1条边；习题一作者---寒江独钓(2)如果边数大于n-1，则至少有一条闭迹；(3)如果恰有n-1条边，则至少有一个奇度点。证明:(1)若G中没有1度顶点，由握手定理：2md(v)2nmnmn1vV(G)若G中有1度顶点u，对G的顶点数作数学归纳。当n=2时，结论显然；设结论对n=k时成立。当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G的边数≥k.(2)考虑G中途径：W:v1v2Lvn1vn若W是路，则长为n-1;但由于G的边数大于n-1,因此，存在vi与vj,它们相异，但邻接。于ii1vvL是：vjvi为G中一闭途径

2、，于是也就存在闭迹。(3)若不然，G中顶点度数至少为2，于是由握手定理：2md(v)2nmnmn1vV(G)这与G中恰有n-1条边矛盾！2.(1)2??-1??2-1??-122(2)2??-2-1(3)2??-23.证明下面两图不同构。u1v1证明:u1的两个邻接点与v1的两个邻接点状况不同。所以，两图不同构。4.证明下面两图同构。5.v1v6v2v10v5v7v8v9v4v3(a)u1u2u10u7u6u5u8u3u4u9(b)证明:作映射f:vi?ui(i=1,2⋯.10)容易证明，对vivjE((a)),有f(vivj,),,ui,uj,,E,((b))(1i10,1j10)由图

3、的同构定义知，图(a)与(b)是同构的。3.指出4个顶点的非同构的所有简单图。分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。3.证明:1)充分性:当G是完全图时，每个顶点的度数都是n-1,共有n个顶点，总的度数为n(n-1)，??(??-1)因此总的边数是2=??(2).2)必要性:因为G是简单图,所以当G是完全图的时候每个顶点的度数才达到最大:n-1.若G不是完全图，则至少有一个顶点的度数小于n-1,这样的话，总的度数就要小于n(n-1)??，因此总的边数小于(2)，矛盾。所以G是完全图。2m8.Δ与δ是简单图G的最大度与最小度，求证：n证明：由握手定理有：

4、nd(v)2mnvV(G)所以有：2mn9.证明：设

5、V1

6、=?1?,

7、V2

8、=?2?,?1?中点的度数之和为??1,,??2中点的度数之和为??2,??的边数为m.有偶图的定义可知d1=??=d2.而d1=k?1?,d2=??2?.?所以?1?=?2?.10.证明：将每个人看成一个顶点，若其中有两个人是朋友，则将这两个人所代表的顶点连接起来，这样便得到了一个简单图。这个图中每个顶点的度数就是这个顶点所代表的人的朋友的数目。因为简单图中至少有两个顶点的度数相同，所以这些人中至少有两个人这这个人群中的朋友数目是相同的。12.证明：若δ≥2，则G中必然含有圈。证明：只就连通图证明即可！设W=

9、v1v2⋯..vk-1vk是G中的一条最长路。由于δ≥2，所以vk必然有相异于vk-1的邻接顶点。又W是G中最长路,所以，这样的邻接点必然是v1,v2,⋯.,kv-2中之一。设该点为vm，则vmvm+1⋯.vkvm为G中圈。13.证明:不妨设G是连通的（否则可考虑其某一个连通分支）.设L=??1??2⋯????-1????是G中最长的一条路。因为δ≥2,所以V(G)中还有δ-1个点与????相邻。因为L是最长的路,所以这些点在??1,??2,⋯,????-1中。又因为G是简单图，所以这些点不可能是????-1.设从??1开始????(1≤i≤k-1-δ)是这些点中第一个与????相邻的点,

10、则????????+1⋯????????是G中的一个圈，其长度至少为δ+1.12.G的围长是指G中最短圈的长；若G没有圈，则定义G的围长为无穷大。证明：（1）围长为4的k的正则图至少有2k个顶点，且恰有2k个顶点的这样的图（在同构意义下）只有一个。（2）围长为5的k正则图至少有k2+1个顶点。证明(1)设u,v是G中两相邻顶点，则S(u)S(v)=,否则，可推出G中的围长为3，与已知矛盾。因此，G中至少有2（k-1）+2个顶点，即有2k个顶点。把S(u)v，S(v)u连为完全偶图，则得到2k个顶点的围长为4的图，由作法知，这样的图是唯一的。(2)设G是围长为5的k正则图,任取u∈V(G)记

11、S??={??∈??(??):??(??,??)=?}?(??=0,1,2,⋯).则:①S1中不同的顶点不相邻;②?2?中每个顶点有且只有一条边与S1相连.(若①或②不成立,则G的围长不是5).这样的话G的顶点数至少为

12、?0?

13、+

14、??1

15、+

16、??2

17、=1+??+??(??-1)=??2+1.13.证明:(1)①G连通②G不连通由m≥n>n-1知,G中至少有一个闭迹,所以G中包含圈.设G的所有的连通分支为??1,??2