张清华图论课后题答案.docx

第1章 图论预备知识1.1 解：(1) p=,a,b,c,a,b,a,c,b,c,a,b,c(2) p=,a,b,c,a,b,c(3) p=,(4) p=,(5)p=,a,b,a,a,b,a,b,a,b,a,b,a,a,b,a,b,a,b,a,b,a,b,a,a,b,a,b,a,b1.2 解：(1) 真 (2) 假 (3)假 (4)假1.3 解：(1) 不成立，A=1 B=1,2 C=2 (2) 不成立，A=1 B=1,2 C=1,31.4 证明：设(x,y)(AB)X(CD) 说明xAB,yCD 由于 xA,yC 所以 (x,y) A X C 由于xB,yD 所以 (x,y) B X D 所以 (x,y) （A X C）（B X D） 反过来，如果（x,y）(A X C) （B X D） 由于 (x,y) （A X C）所以 xA,yC 由于 (x,y) （B X D）所以xB,yD 所以x(AB) y(CD) 所以 (x,y) (AB)X(CD) 所以(AB)X(CD)= (A X C) （B X D）1.5 解：Hasse图12249431025极大元9,24,10,7极小元3,2,5,7最大元24最小元21.6 解 (1)R=|x整除y468(2)关系图为：9102571(3)不存在最大元，最小元为21.7 解：(1)R=,(2) 略(3) IAR 故R是自反的。R R 但是R 故不满足传递性1.8 解：(1) 不成立 A=1 B=2 C=3 D=4 则左式=，, 右式=,(2) 不成立 A=1,3 B=1 C=2,4 D=2 则左式=右式=,(3) 不成立 A=1 B=2 C=3 D=4 则左式=, 右式=,(4) 成立 证明：设(A-B)X C x(A-B) yCxAxB yCA X CB X C(A X C)-(B XC) 故得 （A-B）X C=（A X C）-（B X C）1.9 略1.10略1.11 解：A为n个元素的优先级和，A上有2n2 个 不同的二元关系，理由为：设A，B为集合，AXB的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，称作A上的二元关系，若|A|=n，则|AXA|=n2，那么A上共有2n2个不同的二元关系。1.12略1.13 解：1)真.由于R1和R2和R2都是自反的,因而对任何,都有(x,x)R1,(x,x)R2.因此,对任何xA,都有(x,x)R1R2.所以R1R2是自反的。2)假.令A=a,b,R1=(a,b),R2=b,a.那么R1R2=(a,a),它就不是A上的反自反关系.3)假.令A=a,b,c,R1=(a,b),(b,a),R2=(b,c),(c,b).那末R1R2=(a,c),就不是A的对称关系.4)假.令A=a,b,c,d,R1=(a,c),(b,c),R2=(c,b),(d,a)易证R1,R2都是反对称关系.但是R1R2=(a,b),(b,a)就不是A上的反对称关系.5)假.令A=a,b,c,R1=(a,c),(b,a),(b,c),R2=(c,b),(a,c),(a,b),易证R1和R2都是传递关系,但R1R2=(a,b),(b,b),(b,c)就不是A上的传递关系.1.14 证明：由任意的a，存在一个b，使得R,由对称性所以R,由传递性R,所以R是等价关系。1.15 证明：xA，R,SRS，所以RS有自反性；x,yA,因为R,S是反对称的，RSRS(RS) (RS)(RR) (SS)x=yy=xx=y所以，RS有反对称性。x,y,zA,因为R,S是传递的，RSRSRSRSRRSSRSRS所以，RS有传递性。所以RS也是A上的偏序关系。1.16 解：r(R)=,s(R)=,t(R)=,1.17 (1)证明：对任意a,b,a+b=a+b,故得(a,b)R(a,b),关系R具有自反性;如果(a,b)R(c,d),则a+d=b+c,c+b=d+a,故得(c,d)R(a,b),关系R具有对称性;如果(a,b)R(c,d),(c,d)R(e,f),则a+d=b+c,c+f=d+e,故得a+f=b+e,(a,b)R(e,f),关系R具有传递性;于是关系R是等价关系.1.18 略1.19略1.20 解： (1) 单射(2) 满射(3) 既不是单射，也不是满射(4) 满射(5) 双射1.21 解：(1) O(n3)(2) O(n5)(3) O(n3n!)第2章 图2.1解：(1)a:出度为3、入度为1b:出度为2、入度为2c:出度为2、入度为3d:出度为2、入度为3e:出度为2、入度为2abcde(2)a:出度为3、入度为1b:出度为1、入度为2c:出度为3、入度为3d:出度为3、入度为2e:出度为0、入度为3abcde2.2解：构成无向图的度序列：(1)、(2)、(3)、(4)、(6)构成无向简单图的度序列：(2)、(3)、(4)2.3解：补图为：2.4解：设图G中结点数为n,则有3x4+3x(n-3)=2x12.求得n=7,即图G有7个结点.2.5 证明将习图2.2的两图顶点标号为如下的(a)与(b)图作映射f : f(vi)ui (1 i 10)容易证明，对vivjE(a),有f(vivj)=uiujE(b) (1 i 10, 1j 10 )由图的同构定义知，两个图是同构的。2.6解：同构对应关系：a8、b7、c4、d9、e5、f6、g1、h2、i10、j3.2.7证：设在一有向完全图G中，边数为n.则可知deg+vi=deg-vi=n.即所有结点的入度和等于所有节点的出度和，即所有结点的入度的平方和等于所有节点的出度的平方和。2.8解：(1)(2)2.9证明：用反证法。设无向图G只有两个奇点u,v，若u,v不连通，即它们之间没任何通路，则G至少有两个连通分支G1,G2，且u,v分别属于G1和G2，于是G1和G2中各有一个奇度结点，与握手定理矛盾，因此u,v必连通。2.10解：点割集为：v1，v3、v4、v6割点为：v4、v62.11解：强连通图：(a）单相连通图：（b）（c）（d）弱连通图：（a）（b）（c）（d）2.12证明:设v0v1vk为G中一条最长路，则v0的邻接顶点一定在该路上，否则，与假设矛盾。现取与v0相邻的脚标最大者，记为l，则ld,于是得圈v0v1v2vlv0,该圈长为l+1，显然不小于+1。2.13证明：证其逆否命题：e不是割边当且仅当e含在G的某个圈中。必要性：设e=xy不是割边。假定e位于G的某个连通分支G1中，则G1-e仍连通。故在G1_e中有(x,y)路P，P+e便构成G1中一个含有e的圈。充分性：设e含在G的某个圈C中，而C含于某连通分支G1中，则G1-e仍连通。故W(G-e)=W(G)，这说明e不是割边,证毕。2.14证明：用数学归纳法证明：（1）n=1时，G为平凡图，显然G连通。（2）n=2时，m12n-1n-2+1=1此时G为K2，当然连通。（3）假设当n=k（k2）时，m12n-1n-2+1结论成立。当n=k+1时，若此时每个结点度数为k，则结论显然成立，否则必存在一个结点v度数至多只有k-1度，即这个结点最多只有k-1条边和它相连。因为此时总的边数m12kk-1,则其它k个结点之间的边数m12kk-1-(k-1)=12k-1k-2。根据归纳假设，显然这k个结点之间是连通的，而根据上面我们知道，至少有一条边使v和其它结点相连，所以此时这个图是连通的,结论成立。2.15证明：（1）因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=uwv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路p,以此类推，可以找到一条和p每条边都不相同的p=vu,这样p和p就构成了一条回路。（2）因为G中任意两个结点都位于同一回路中，所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1=C2=uv1v2u,那么将回路中v1v2,用v1v2=e替换，就得到新的新的回路，并满足要求。如果C1C2，C1=uv1u,C2=uv2u,那么构成新的道路P=uv1uv2u,在其中将重复边剔出掉，得到新的回路C3，其中包含v1,v2结点，可以将回路中v1v2用v1v2=e替换，就得到新的新的回路，并满足要求。（3）对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据（2）存在回路C1=u1v1v2u1,C2=u2v1v2u2。那么可以形成新的闭道路P=u1v1v2u2v1v2u1,在其中将重复边剔出到，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中u1u2用u1u2=e1替换，就得到新的新的回路，包含e1,e2,满足要求。(4)因为任意两条边都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边。2.16解：(1)deg(v1)=2、deg(v2)=3(2)否 (3) 4(4)略2.17解：(1)A=0101001101010100(2)A2=0111020101110011A3=0212012202120201A4=0323041303230322V1到V4长度为1、2、3、4的路各有1、1、2、3条。2.18解：无向图G:v1v2v3v4v5可达矩阵P = 1111111111111111111111111 有可达矩阵可知改图为强连通图。2.19解：(1) 邻接矩阵A = 1200000100011010(2) G中长度为3的通路有23条，其中有7条为回路。(3) 图G为强连通图2.20解：邻接矩阵 A = 1201200000011010关联矩阵 M(G) = 211100110000001000112.21解：(1)当r=1时，没有长度大于等于1的圈。 当2rs时，有长度为4,6,2r的圈，它们都是偶圈，因而非同构的圈共有r-1种。 (2)至多有r个顶点彼此不相邻。 (3)至多有r条边彼此不相邻。 (4)k= r 2.22证明：反证法。若存在某个具有奇数个面，且每个面均有奇数条棱的多面体V，不妨设V有r(r为奇数)个面，设为R1,R2,Rr，S1,S2,Sr分别为它们的棱数，均为奇数。作无向图G如下：在V的每个面中放一个顶点vi，i=1,2,r, 且两个面Ri与Rj有公共面就连边。若存在这样的无向图G，则d(vi)均为奇数Si，由握手定理得i=1dvi=i=1Si=2m(m为边数)但因r,Si(i=1,2,n)均为奇数，上面等式不可能成立。故不存在这样的无向图G，从而也不存在满足要求的多面体。2.23解：设G是n阶m条边的自补图,即G为n阶m条边的简单图,且GG 。于是，G 的边数m=m，且m+m=2m=n(n-1)/2。于是n(n-1)=4m，因而n=4k，或n-1=4k，k为正整数。2.24证明：为偶数(n为奇数)。于是，若为奇数，必有dG(v)也为奇数。故与G中奇度顶点个数相等。2.25解:都可以实现，如下图(1)(2)2.26解：(1)错误、(2)正确、(3)正确2.27略2.28解：无向完全图Kn当n3且n为奇数时才是欧拉图。 当n3且n为偶数时存在欧拉路而不存在欧拉回路。2.29 略2.30 略2.31 略第3章 树与最短路径3.1该树的结点个数n=5，故边数m=n-1=4,因为，所以5个结点分配的度数为8，由于树是简单连通图，知，则该树的度数序列必是下列情况之一，(1)1，1，2，2，2(2)1，1，1，2，3(3)1，1，1，1，4这些度数序列对应的简单树为3.2该树的结点个数为，则边数，又因为，所以可知一棵树的结点个数之和为。3.3设有n个一度结点，则结点个数为=3+5+8+n，边数为=3+5+8+n-1,则.可得n=23.3.4设有n个一度结点，则：3.5反证法。假设没有结点度数大于等于3的结点，则只有度为1的结点3个和度为2的结点n个。边数：3+n-1，度数：3+2n.所以2（3+n-1）=3+2n。等式左边为偶数，右边为奇数，相互矛盾，假设不成立。所以至少有一个结点度数大于等于3.3.6设度为的结点个数为则则由于，故全为0.当时，只有两个度为1的结点，所以T是一条直线。当时，有两个度为1的结点，其他结点度数都为2，T仍为一条直线。综上T是一条直线。3.7=若为度数序列,则该树的结点个数为n，边数为n-1,所以：为G的面，为的结点，G的对偶图为，可得又因为为欧拉图所以为偶数，为偶数，所以G的每一个面都有偶数条边围城。=：G的面，为的结点，G的对偶图为，可得，又因为G的每一面均有偶数条边围城，所以为偶数，所以为偶数。故中所有结点的度是偶数，无奇度结点，所以为欧拉图。6.10证明：G有n个结点m条边，则。假设每一个面的度数大于等于5，则，整理得，这与题目给出的相矛盾，故假设不成立，即至少有一个面的度数小于5.6.11证明：假设G和都是平面图，则对图G可得（1）对图可得（2）；整理（1）式和（2）式得：，又因为，故，这与相矛盾，故假设不成立，即G和至少有一个是非平面图。6.12证明（1）由于G无割点所以G肯定无割边，且每两个面之间最多有一条公共边，所以是简单图，因此中至少有两个度相同的顶点，即G中至少有两个面相同的的度数。（2）设G中有k个度为5的面，又因为