图论(张先迪-李正良)课后习题答案(第一章).pdf

《图论(张先迪-李正良)课后习题答案(第一章).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、。于vvLvvii1ji是：为G中一闭途径，于是也就存在闭迹。(3)若不然，G中顶点度数至少为2，于是由握手定理：2mdv()2nmnmn1vVG()这与G中恰有n-1条边矛盾！?1212.(1)2−?−?−122(2)2?−2−1(3)2?−23.证明下面两图不同构。uv11证明:u1的两个邻接点与v1的两个邻接点状况不同。所以，两图不同构。4.证明下面两图同构。v1v6v2v10v5v7v8v9v4v3(a)u1u6u5u2u8u10u3u4u7u9(b)证明:作映射f:vi↔ui(i=1,2….10)容易证明，对vivjE((a

3、)),有f(vivj,),,ui,uj,,E,((b))(1i10,1j10)由图的同构定义知，图(a)与(b)是同构的。5.指出4个顶点的非同构的所有简单图。分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。6.证明:1)充分性:当G是完全图时，每个顶点的度数都是n−1,共有n个顶点，总的度数为n(n−1)，?(?−1)?因此总的边数是=().222)必要性:因为G是简单图,所以当G是完全图的时候每个顶点的度数才达到最大:n−1.若G不是完全图，则至少有一个顶点的度数小于n−1,这样的话，总的度数就要小于?n(n−1)，因此总的边

4、数小于()，矛盾。所以G是完全图。22m8.Δ与δ是简单图G的最大度与最小度，求证：n证明：由握手定理有：ndv()2mnvVG()所以有：2mn9.证明：设

5、V1

6、=?1,

7、V2

8、=?2,?1中点的度数之和为?1,,?2中点的度数之和为?2,?的边数为m.有偶图的定义可知d1=?=d2.而d1=k?1,d2=??2.所以?1=?2.10.证明：将每个人看成一个顶点，若其中有两个人是朋友，则将这两个人所代表的顶点连接起来，这样便得到了一个简单图。这个图中每个顶点的度数就是这个顶点所代表的人的朋友的数目。因为简单图中至少有两个顶点的度数相

9、同，所以这些人中至少有两个人这这个人群中的朋友数目是相同的。12.证明：若δ≥2，则G中必然含有圈。证明：只就连通图证明即可！设W=v1v2…..vk-1vk是G中的一条最长路。由于δ≥2，所以vk必然有相异于vk-1的邻接顶点。又W是G中最长路,所以，这样的邻接点必然是v1,v2,….,vk-2中之一。设该点为vm，则vmvm+1….vkvm为G中圈。13.证明:不妨设G是连通的（否则可考虑其某一个连通分支）.设L=?1?2…??−1??是G中最长的一条路。因为δ≥2,所以V(G)中还有δ−1个点与??相邻。因为L是最长的路,所以这些点在?1,?2,…,??−1中

10、。又因为G是简单图，所以这些点不可能是??−1.设从?1开始??(1≤i≤k−1−δ)是这些点中第一个与??相邻的点,则????+1…????是G中的一个圈，其长度至少为δ+1.14.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

11、，S(v)u连为完全偶图，则得到2k个顶点的围长为4的图，由作法知，这样的图是唯一的。(2)设G是围长为5的k正则图,任取u∈V(G)记S?={?∈?(?):?(?,?)=?}(?=0,1,2,…).则:①S1中不同的顶点不相邻;②?2中每个顶点有且只有一条边与S1相连.(若①或②不成立,则G的围长不是5).这样的话G的顶点数至少为

12、?0

13、+

14、?1

15、+

16、?2

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