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

习题一习题一 作者作者-寒江独钓寒江独钓 1.证明：在 n 阶连通图中 (1) 至少有 n-1 条边； (2) 如果边数大于 n-1，则至少有一条闭迹； (3) 如果恰有 n-1 条边，则至少有一个奇度点。 证明: (1) 若 G 中没有 1 度顶点，由握手定理： () 2( )21 v V G md vnmnmn 若 G 中有 1 度顶点 u，对 G 的顶点数作数学归纳。 当 n=2 时，结论显然；设结论对 n=k 时成立。 当 n=k+1 时，考虑 G-u,它仍然为连通图，所以，边数k-1.于是 G 的边数k. (2) 考虑 G 中途径： 121 : nn Wvvvv L 若 W 是路，则长为 n-1;但由于 G 的边数大于 n-1,因此，存在 vi与 vj,它们相异，但邻接。于 是： 1iiji vvvv L 为 G 中一闭途径，于是 也就存在闭迹。 (3) 若不然，G 中顶点度数至少为 2，于是由握手定理： () 2( )21 v V G md vnmnmn 这与 G 中恰有 n-1 条边矛盾！ 2.(1)2 1 2 2 1 2 1 (2)22 1 (3) 22 3.证明下面两图不同构。 证明:u1的两个邻接点与 v1的两个邻接点状况不同。所以， 两图不同构。 4.证明下面两图同构。 u1 v1 证明:作映射 f : vi ui (i=1,2.10) 容易证明，对vi v j E (a),有 f (v i vj,),ui,uj,E,(b) (1 i 10, 1j 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出 4 个顶点的非同构的所有简单图。 分析：四个顶点的简单图最少边数为 0，最多边数为 6，所以 可按边数进行枚举。 (a) v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 (b) 6.证明: 1)充分性:当G是完全图时，每个顶点的度数都是n 1,共有n个顶点，总的度数为n(n 1)， 因此总的边数是(1) 2 =( 2 ). 2)必要性:因为G是简单图,所以当G是完全图的时候每个顶点的度数才达到最大:n 1.若G不 是完全图，则至少有一个顶点的度数小于n 1,这样的话，总的度数就要小于 n(n 1)，因此总的边数小于 ( 2)，矛盾。所以G是完全图。 8. 与是简单图 G 的最大度与最小度，求证： 证明：由握手定理有： 所以有： 9.证明： 设|V1 | = 1,|V2 | = 2,1中点的度数之和为1,2中点的度数之和为2,的边数为 m.有偶 图的定义可知d1= = d2.而d1= k1,d2= 2.所以1= 2. 10.证明： 将每个人看成一个顶点，若其中有两个人是朋友，则将这两个人所代表的顶点连接起 来，这样便得到了一个简单图。这个图中每个顶点的度数就是这个顶点所代表的人的朋友 的数目。因为简单图中至少有两个顶点的度数相同，所以这些人中至少有两个人这这个人 群中的朋友数目是相同的。 12.证明：若2，则 G 中必然含有圈。 证明：只就连通图证明即可！ 设 W=v1v2.vk-1vk是 G 中的一条最长路。由于 2，所以 vk必然有相异于 vk-1的邻接顶点。 又 W 是 G 中最长路,所以，这样的邻接点必然是 v1,v2,.,vk-2中之一。设该点为 vm，则 vmvm+1.v kvm为 G 中圈。 13.证明: 不妨设G是连通的（否则可考虑其某一个连通分支）.设L = 121 是 G 中最长的一条路。因为 2,所以V(G)中还有 1 个点与相邻。因为L 2m n () ( )2 v V G nd vmn 2m n 是最长的路,所以这些点在1,2,1 中。又因为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，S(v) u连为完全偶图，则得到 2k 个顶点的围长为 4 的图，由作法知，这样的图是唯一的。 (2)设G是围长为 5 的 k 正则图,任取u V(G)记S= ():(,) = ( = 0,1,2,).则:S1中不同的顶点不相邻;2中每个顶点有且只有一条边与S1相 连.(若或不成立,则G的围长不是 5).这样的话G的顶点数至少为 | 0| + |1| + |2| = 1 + + ( 1) = 2+ 1. 15.证明: (1)G连通 由 m n n 1 知,G 中至少有一个闭迹,所以 G 中包含圈. G 不连通 设G的所有的连通分支为1,2,.的顶点数为,边数为,(i = 1,2,k) 则至少有一个0,使得0 0.由可知0中包含圈,所以 G 中包含圈. (2) 只就 m=n+4 证明就行了。 设 G 是满足 m=n+4，但不包含两个边不相交的圈的图族中顶点数最少的一个图。可以 证明 G 具有如下两个性质： 1) G 的围长 g5。事实上，若 G 的围长4，则在 G 中除去一个长度4 的圈 C1的一条 边，所得之图记为 G,显然，m(G) V(G)=V(G),由(1),G中存在圈 C2, 使 C1,C2的边不相 交这与假定矛盾； 2） (G)3。事实上，若 d(v0)=2,设 v0v1,v0v2E(G),作 G1=G-v0+v1v2;若 d(v0)1,则 G1为在 G 中除去 v0及其关联的边(d(v0)=0,任去 G 中一条边)所得之图。显然， m(G1)=V(G1)+4,G1仍然不含两个边不重的圈之图。但V(G1)V(G)，与假定矛盾。 由 2),n+4=m3n/2 n 8. 但另一方面，由 1),在 G 中存在一个圈 Cg，其上的顶点之间的 边，除 Cg 之外，再无其它边，以 S0表示 Cg 上的顶点集，故由 2),S0上每个顶点均有伸向 Cg 外的的边。记与 S0距离为 1 的顶点集为 S1，则 S0的每一个顶点有伸向 S1的边，反过 来，S1中的每个顶点仅有唯一的一边与 S0相连，不然在 G 中则含有长不大于 g/2+2 的圈， 这与 G 的围长为 g 相矛盾，故S0 S1,于是有：nS0+ S1g+g10,但这与 n8 矛盾。所 以，假定条件下的 G 不存在。 18.证明: 因为e只能属于G的某一个连通分支,所以只需考虑G是连通图的情况. 若G e仍然连通,则(G) = 1 = (G e) 2 = (G) + 1. 若G e不连通,则(G) = 1 2 = (G e) = (G) + 1. 19.证明: 设1是 G v 的任一个连通分支,则在 G 中 v 通过偶数条天与1相连,否则1 中有奇数个奇顶点.所以 v 至少通过两条边与1相连,因此 (G v) d(v)/2 20证明: (1)G不连通的时候,设 G中的两个连通分支1,G2。则在 中, 1中的每个顶点与G2 中的每个顶点都相邻，于是G的同一个连通分支中的顶点在 中的距离为 2 或 0，G中不同的连通分支中的顶点在 中的距离都为 1。所以d( ) 3.因此u不同时和1,2相邻，v也不能同时与1,2相邻。 所以在中,d(u,v) = 2. 结合可知d( ) 2.不妨假设 u 和 v1,v2vk邻接。 为了保证 u 到各点距离不超过 2,vk+1,.vn-2这些顶点的每一个必须和前面 v1,v2,vk中某点邻 接，这样，图中至少又有 n-2 条边。总共至少有 2n-4 条边。 22.证明: 因