离散数学课本习题

《离散数学课本习题》由会员分享，可在线阅读，更多相关《离散数学课本习题（17页珍藏版）》请在装配图网上搜索。

1、习题1.11、 用列举法给出下列集合：a) 小于5的非负整数的集合；b) 10到20之间的素数的集合；c) 不超过65的12之正整数倍数的集合。2、 用命题法给出下列集合：a) 不超过100的自然数的集合；b) Ev和Od；c) 10的整倍数的集合。3、 用归纳定义法给出下列集合：a) 允许有前0的十进制无符号整数的集合；b) 不允许有前0的十进制无符号整数的集合；c) 允许有前0和后0的有有限小数部分的十进制无符号实数的集合；d) 不允许有前0的十进制无符号偶数的集合；e) Ev和Od；f) 集合0，1，4，9，16，25，。4、 确定下列集合中哪些是相等的：A=x|x为偶数且x2为奇数B=

2、x|有yI使x=2yC=1，2，3D=0，2，-2，5，-3，4，-4E=2x|xIF=3，3，2，1，2G=x|有xI且x3-6x2-7x-6=05、 确定下列关系中哪些是正确的，并简单说明理由。a) b) c) d) e) a, ba, b, c,a, b, cf) a, ba, b, c,a, b, cg) a, ba, b,a, bh) a, ba, b,a, b6、 设A、B和C为集合。证明或用反例推翻以下的各个命题：a) 若AB且BC，则AC。b) 若AB且BC，则AC。c) 若AB且BC，则AC。d) 若AB且BC，则AC。7、 若A、B为集合，则AB与AB能同时成立吗？请证明你

3、的结论。8、 列举出下列集合中每个集合的所有子集：a) 1，2，3b) 1，2，3c) 1，2，3d) e) , f) 1，2，2，1，1，2，1，1，2g) ，2，29、 给出下列集合的幂集：a) a，bb) 1，c) x, y, zd) ，a,ae) ()10、设 (A)= (B)。证明A=B。习题1.21. 设U=1,2,3,4,5,A=1,4,B=1,2,5,C=2,4。试求下列集合：a) A B；b) (A B) C；c) (A B)；d) A B；e) (A B) C；f) A (B C)；g) (A B) C；h) (A B) (B C)2. 设A=n|nI+且n10；e) n|

4、n为正偶数且n10，或n为奇数且n9。3. 证明：a) 如果AB且CD，则ACBD且ACBD；b) A(B-A)=;c) A(B-A)=AB;d) A (B C)= (A B) (A C)；e) A (B C)= (A B) (A C)；f) A (A B) = A B；g) A-(B-C)=(A-B)(AC)。4. 证明a) A=B当且仅当AB=；b) AB= BA；c) (AB)C= A(B C)；d) A(B C)=(AB)(AC)；e) (B C) A=(BA)(CA)。5. 判断一下结论是否成立，如果或成立，就给予证明，如果不成立，就用文氏图加以说明。a) 若ACBC且ACBC，则A

5、B；b) 若AB=AC且AB=AC，则B=C；c) 若AB=AC，则B=C;d) 若AB=AC，则B=C;e) AB=AC，则B=C;f) 若ABC，则AB或AC；g) 若BCA，则BA或CA。6. 给出下列各式成立的充分必要条件，并加以证明。a) (A-B)(A-C)=A;b) (A-B)(A-C)=;c) (A-B)(A-C)=A;d) (A-B)(A-C)= A;e) (A-B)(A-C)=A;f) (A-B)(A-C)= ;g) AB=AB;h) A-B=B; i) A-B=B-A;j) AB=A；k) (A)(B)=(AB);7. 设A，B为任意两个集合，证明：a) (A)(B)(A

6、B);b) (A)(B)=(AB)。8. 试求出和，其中为：a) ；b) ，；c) a,b,a,b。9. 设且，且，。 证明10. 设且，试求和11. 设且。试求和。12. 设， ，我们称和分别为集合序列的上极限和下极限，证明：a) 为由一切属于无限多个的元素组成的集合；b) 为由一切属于“几乎所有”的的元素组成的集合。习题1.31、 用归纳法证明：a)；b)2+22+23+2n=2n+1-2；c)2n=2n；d)3|n3+2n;e)123+234+n(n+1)(n+2) =f)任意三个相邻整数的立方和能被9整除；g)11n+2+122n+1是133的倍数；h)若nI+则。2、设a0，a1，a

7、2，为由自然数组成的严格单调递增序列。证明：若nN，则nan。3、斐波那契(Fibonacci)数列定义为F0=0F1=1Fn+1=Fn+Fn-1，nI+证明：若nI+，则。4、设n, mI+且nm。假定有n个直立的大头针，甲、乙两人轮流把这些直立的大头针扳倒。规定每人每次可扳倒1至根，且扳倒最后一根直立的大头针者为获胜者。试证明：如果甲先扳且(m+n)不能整除n，则甲总能获胜。5、证明以下的二重归纳原理的正确性：设i0, j0N。假定对任意自然数ii0及jj0，皆有一个命题P(i, j)满足：i) P(i0, j0)真；ii)对任意自然数ki0及lj0，若P(k, l)真，则P(k+1, l

8、)和P(k, l+1)皆真。则对任意自然数ii0及jj0，P(i, j)皆真。6、证明：若nN，则nn。7、证明：若n, mN，则n m当且仅当n m。8、证明：若n, mN，则n m当且仅当n+ m+。9、证明：若n, mN，则nm当且仅当有xN使m = n+ x+。10、证明：若nN，则不可能有mN使nmn+。习题1.41、 设A=0,1，B=1,2。试确定下列集合：a)A1Bb)A2Bc)(BA )2 2、证明或用反例推翻下列命题：a)(AB)(CD)= (AC)(BD) b)(AB)(CD)= (AC)(BD)c)(AB)(CD)= (AC)(BD) d)(AB)(C D)= (AC)

9、(BD) 3、如果BCA，则(AB) (CD)= (AC) (BD)。这个命题对吗？如果对，则给予证明；如果不对，则举出反例。f) 4、证明：若xC且yC，则 (C)。5、证明：a且b。6、把三元偶定义为 a , a, b , a, b, c 合适吗？说明理由。7、为了给出序偶的另一定义，选取两个不同集合A和B(例如取A=，B=)，并定义= a, A ,b, B。证明这个定义的合理性。第二章 二元关系习题2.11、 列出从A到B的关系R中的所有序偶。a)A=0, 1, 2，B=0, 2, 4，R=| x, y AB b)A=1, 2, 3, 4, 5，B=1, 2, 3，R=| x A, y

10、B且x =y22、设R1和R2都是从1, 2, 3, 4到 2, 3, 4的二元关系，并且R1=, R2=, 求R1R2, R1R2, domR1, domR2, ranR1, ranR2, dom(R1R2)和ran(R1R2)。3、设和都是从集合到集合的二元关系。证明dom(R1R2)= domR1domR2ran(R1R2) ranR1ranR24、用L和D分别表示集合1, 2, 3, 6上的普通的小于关系和整除关系，试列出L, D和LD中的所有序偶。5、给出满足下列要求的二元关系的实例：a)既是自反的，又是反自反的；b)既不是自反的，又不是反自反的；c)既是对称的，又是反对称的；d)既

11、不是对称的，又不是反对称的。6、试判断下面的论断正确与否。若正确，请加以证明；若不正确，请给出反例。设R和S都是集合A上的二元关系。若R和S都是自反的(反自反的，对称的，反对称的，或传递的)，则RS，RS，RS，RS也是自反的(反自反的，对称的，反对称的，或传递的)。7、描述R上的下列二元关系S的性质：a)S=|x, yR且x y 0；b)S=|x, yR，4整除|xy|且|xy|10；c)S=|x, yR，x2 =1且y 0；d)S=|x, yR，4 |x|1且| y|1。8、设n, mI+。若集合A恰有n个元素，则在A上能有多少个不同的m元关系？证明你的结论。9、设x和z都是由从集合A到集

12、合B的二元关系构成的集类，并且z 。证明a)dom(x)=domR|Rx； b)ran(x)=ranR|Rx；c)dom(z)domR|Rz；d)ran(z)ranR|Rz；10、设R为集合上的一个二元关系。如果R是反自反的和传递的，则R一定是反对称的。11、设R为集合上的一个二元关系，若令fldR=domRranR则fldR=(R)。12、若R为集合上的一个二元关系，则也是(R)上的二元关系。习题 2.21. 设集合A=1,2,3,4,5,6上的二元关系R为R=,试画出R的关系图GR，求出R的关系矩阵MR,并指出R所具有的性质。2. 对图给出的集合A=1,2,3上的十二个二元关系的关系图，写

13、出相应的关系矩阵，并指出各个关系所具有的性质。3. 对习题2.1种第4题所给的二元关系L,D和LD，画出它们的关系图，并写出它们的关系矩阵。4. 设A为恰有n个元素的有限集。a) 共有多少个A上的不相同的自反关系？a) 共有多少个A上的不相同的反自反关系？b) 共有多少个A上的不相同的对称关系？c) 共有多少个A上的不相同的反对称关系？d) 共有多少个A上的不相同的既是对称又反对称的关系？习题2.31. 设R为非空有限集A上的二元关系。如果R是反对称的，则RR-1的关系矩阵MRR-1中最多能有多少个元素为1？2. 设R为集合A上的二元关系，则RR-1为A上包含R的最小对称关系，RR-1为A上的

14、包含在R中的最大对称关系。3. 设IA为集合A上的恒等关系，即IA=|xA。则对A上的任意二元关系R，A上的二元关系IARR-1必是自反的和对称的。4. 设R为任意的二元关系。证明a) domR-1=ranR;b) ranR-1=domR。习题2.41、 设集合a, b, c, d上的二元关系R1和R2为R1=,；R2=,。试求R2oR1，R1o R2，及。3、若R为任意集合上的空关系或全关系，则R2=R。4、举出使R1o(R2R3) (R1oR2)(R1oR3), (R2R3)o R4 (R2oR4)(R3oR4)成立的二元关系R1，R2，R3和R4的实例。5、设R1和R2都是集合A上的二元

15、关系。证明或用反例推翻以下的论断：a)如果R1和R2都是自反的，则R1oR2也是自反的；b)如果R1和R2都是反自反的，则R1oR2也是反自反的；c)如果R1和R2都是对称的，则R1oR2也是对称的；d)如果R1和R2都是传递的，则R1oR2也是传递的；6、设A=0，1，2，3上的二元关系R1和R2为R1=| j=i+1或j =i/2；R2=|i=j+2；试求，及。8、设R为集合A上的二元关系，s，tN，st且Rs=Rt。证明a)若kN，则Rs+k=Rt+k；b)若k, iN，则Rs+kp+i=Rs+ i；c)若kN，则RkR0,R1,Rt-1。其中p=t-s。9、设IA为集合A上的恒等关系，

16、R为A上的任意二元关系。证明a)R是自反的，当且仅当IAR；b)R是反自反的，当且仅当RIA=；c)R是对称的，当且仅当R =R-1；d)R是反对称的，当且仅当R R-1= IA；e)R是传递的，当且仅当RoRIA。10、如果集合A上的二元关系R既是自反的，又是传递的，则R2=R。11、设R1为从集合A到集合B的二元关系，R2为从集合B到集合C的二元关系。试求dom(R1oR2)和ran(R1oR2)。12、设R为从集合A到集合B的二元关系，且对每个XA，皆令R (X)= yB|有xX使x，yR。若X1A且X2A，则有i)R (X1X2)= R (X1)R (X2)；ii)R (X1X2) R

17、 (X1)R (X2)；iii)R (X1X2)R (X1)R (X2)；13、设R1为从集合A到集合B的二元关系，R2为从集合B到集合C的二元关系。若XA，则(R1oR2) (X)= R2(R1 (X)。习题2.52、设R1和R2都是集合A上的二元关系，试证明：a)r(R1R2)=r(R1)r(R2)；b)s(R1R2)=s(R1)s(R2)；c)t(R1R2)t(R1)t(R2)。4、设R1和R2都是集合A上的二元关系，试证明：a)r(R1R2)=r(R1)r(R2)；b)s(R1R2)s(R1)s(R2)；c)t(R1R2)t(R1)t(R2)。并分别给出使s(R1)s(R2)s(R1R

18、2)和t(R1)t(R2)t(R1R2)不成立的R1和R2的具体实例。6、给出一个二元关系R使 st(R)ts (R)。7、设R为集合A上的二元关系，试证明：a)RoR*= R+= R*oR；b)(R+)+= R+；c)(R*)*= R*；习题2.61、设R1和R2都是集合A上的相容关系。证明或用反例推翻下列命题：a)R1R2是A上的相容关系；b)R1R2是A上的相容关系；c)R1R2是A上的相容关系；d)R1R2是A上的相容关系；e)R1oR2是A上的相容关系；f)是A上的相容关系；3、如果A为恰含n个元素的有限集，则A上有多少个不同的相容关系？习题2.71、试判断下列I上的二元关系是不是I

19、上的等价关系，并说明理由。a)| i, jI且ij 0；b) | i, jI且ij0且i与j不同时为0；c) | i, jI且i0 ；d) | i, jI且ij0 ；e) | i, jI且i| j ；f) | i, jI且有xI使10xij10(x +1)；g) | i, jI且| ij |10 ；h) | i, jI且有x, yI使10xi10(x+1)及10 yj10(y +1)；i) | i, jI且有xI使10x i 10(x +1)；2、 有人说：“如果集合A上的二元关系R是对称的和传递的，则R必是自反的”。并给出了如下的证明：如果R，则由R是对称的可知R，从而由R是传递的得到R和R

20、。因此R是自反的。请你想一想，他的看法和证明对吗？为什么？3、 设集合A上的二元关系R是自反的。证明R为等价关系的充要条件是：若,R,则R.4、 如果集合A上的二元关系R满足：若,R，则R。就称R为循环的。试证明集合A上的二元关系R为A上的等价关系，当且仅当R是自反的和循环的。5、 设R1和R2都是集合A上的等价关系。试判断下列A上的二元关系是不是A上的等价关系，为什么？a) A2R1；b) R1R2；c) ；d) r(R1R2)；e) R2oR1；f) R1R2；g) t(R1R2) ；h) t(R1R2) ；6、设1和2都是集合A的划分。试判断下列集类是不是A的划分，为什么？a)12；b)

21、12；c)12；d)(1(21) ) 1；7、如果R1和R2都是集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2。8、设1和2都是集合A的划分，若对每个S11，皆有S22使S1S2，就称1和2的加细，记为12且12，就称1为2的真加细，并记为12。设R1和R2都是集合A上的等价关系，证明：a) R1R2当且仅当A/R1A/R2。b) R1R2当且仅当A/R1A/R2。9、设A和B都是非空集，A1,A2,An为A的划分。试证明 A1B,A2B,AnB并不总是集合AB的划分。10、若R为集合A上的等价关系，则称n(A/R)为R的秩。如果i,jI+且集合A上的等价关系R1与R2的秩分别为i

22、和j，则R1R2也A上的等价关系且maxi,jn(A/( R1R2)ij。11、设A为恰含n个元素的非空有限集，则有多少个不同的A上的等价关系？其中秩为2的又有多少？12、如果n,mI+，则I/n为/ Im的加细当且仅当m|n。习题2.82、画出下列集合上的整除关系的哈斯图。a)1,2,3,4,6,8,12,24；b)i|iI且1i14；c)i|iI且5i20；3、设R为集合A上的二元关系且SA，证明或用反例推翻下述断言：a)若R是A上的半序，则R|s是S上的半序；b)若R是A上的拟序，则R|s是S上的拟序；c)若R是A上的全序，则R|s是S上的全序；d)若R是A上的良序，则R|s是S上的良序

23、；4、设R是集合A上的二元关系。证明：a)若R是A上的半序，当且仅当RR-1=IA且R=R*；b)若R是A上的拟序，当且仅当RR-1=且R=R+； 5、证明：a)半序关系的逆关系仍然是半序关系；b)全序关系的逆关系仍然是全序关系；c)良序关系的逆关系未必是良序关系；7、举出满足下列条件的半序结构的实例。a)为全序结构，且A的某些非空子集无最小元。b)不是全序结构，且A的某些非空子集无最大元。c)A的某些非空子集有下确界，但无最小元。d)A的某些非空子集有上界，但无上确定界。8、设为半序结构。证明A的每个非空有限子集都至少有一个极小元和极大元。9、设为全序结构。证明A的每个非空有限子集都有一个最

24、大元和最小元。10、试判断下列定义在二维欧氏空间RR上的二元关系T是不是RR上的拟序，半序，全序和良序？RR的每个有下界的非空子集(关于拟序或半序T)是否与下确界？并给出证明。a)若x1, x2, y1, y2R，则T当且仅当x 1x2且y1y2；b)若x1, x2, y1, y2R，则T当且仅当x 1x 2；c)若x1, x2, y1, y2R，则T当且仅当x1x2或者x1=x2且y1y2；d)若x1, x2, y1, y2R，则T当且仅当x1x2。11、设R为集合S上的全序关系。证明R和R-1同时为S上的良序，当且仅当S为有限集。12、I+在上定义二元关系R如下：nRm当且仅当f(n) f

25、(m),或f(n)= f(m)且nm其中f(n)表示n的不同素因子的个数。证明为良序结构。13、设S为集合且l(S)。证明在半序结中有Supl=l；infl=l。14、设p为集合A的所有划分组成的集合，并在p上定义二元关系R如下：对任意的1,2p，则1R2当且仅当1为2的加细。证明R是上的半序。第三章习题3.11、下列关系中哪些是部分函数？对于不是部分函数的关系，说明不能构成部分函数的原因。a)| x, yN 且 x+ y10；b)| x, yR 且 y = x 2；c)| x, yR 且 y 2= x。2、下列集合能定义部分函数吗？如果能，试求出它们的定义域和值域。a)1,2,3,4,；b)

26、1,2,3,；c)1,2,1,；d)1,2,3,；3、设A为集合。若对任意s1,s2(A)皆令f (s1,s2)= s1s2，则f是从(A)(A)到(A)上的二元函数。5、设f为从X到Y的部分函数，试证明：a)若A，B(X)，则f AB fAfB，并举例说明不能用“=”代替其中的“”；b)若C，D(Y)，则f-1CD= f-1Cf -1D。6、设A=1,0,1，则定义函数f:A2I如下：写出f的全部序偶。a) 求出ranf。b) 写出f 0,12中的全部序偶。c) 有多少个和f具有相同的定义域和值域的函数g:A2I?7、设A和B为有限集，n(A)=m且n(B)=n。a)有多少个从A到B的1-1

27、函数？b)有多少个从A到B上的函数？8、“91”函数f:NN定义如下：试证明a) f(99)=91；b) f(x)=91，其中0x100。习题3.21、设f,g,h是从R到R的函数，对每个xR皆有f (x)= x+3,g(x)=2x +1,h(x)= x/2。试求gof, fog, fof, gog, foh, hog, hof, goh和fohog。2、设f,g,h都是从R到R的部分函数，对于x0,f(x)=1/ x。对于xR, g(x)= x 2。对x0,h(x)=。试求fof, hog, goh及它们的定义域和值域。3、对于下面的函数f，确定i)f是否为内射、满射和双射；ii)f的值域；

28、iii) f-1s。a) f:RRf(x)=2 xs=1b) f:NNNf(n)=s=c) f:NNf(n)=2n+1s=2,3d) f:INf(x)=|x|s=1,0e)f:0,10,1f(x)=2/x+1/4s=0,1/2f) f:0,Rf(x)=1/(1+ x)s=0,1,2g)f:a,b*a,b*f(x)= xas=e,b,bah)f:(0,1)(0,)f(x)=1/xs=(0,1)4、设nI+，f:AA。证明：如果f是内射(满射，双射)，则f n也是内射(满射，双射)。5、设f是从A到A的满射且fof= f，证明f= IA。6、设f是从X到Y的部分函数，g是从Y到Z的部分函数，ran

29、fdomg。证明dom(gof)=domf。7、设A=1,2,3。有多少个从A到A的满射f使f(1)=3?8、设A=1,2,n。有多少满足以下条件的从A到A的函数f:a)fof= fb)fof= IAc)fofof= IA9、设f:XY且g:YZa)若gof为满射，g为内射，则f为满射b)若gof为内射，f为满射，则g为内射习题3.32、设f是从X到Y的双射，证明(f-1)-1= f。3、设f,g,h都是从N到N的函数，其中f(x)=3x,g(x)=3x+1,h(x)=3x+2。a)找出它们的一个共同的左逆。b)找出f和g的一个共同左逆，使其不是h的左逆。4、设f:AB和g:BC。如果gof是

30、左可逆的，能否保证f和g也一定都是左可逆的？5、设f:AB且n(A)2。证明f是可逆的当且仅当f有唯一的左(右)逆。6、设A和B是有限集且1n(A)n(B)。问共有多少个从A到B的内射?习题3.42、用特征函数求下列各式成立的充分必要条件。a)(AB)(AC)=A；b)(AB)= ；c)(AB)= A；d)AB=AB。1、构造从集合A到集合B的双射。a)A=R,B=(0,)；b)A=(0,1),B=0,1)；c)A=0,1),B=(1/4,1/2；d)A=0,1,B=(0,1)。2、设n0且x1,x 2,xn是n个任意整数，证明存在k和i使1ikn且xi+xi+1+xk能被n整除。3、从小于2

31、01的正整数中任意选取101个，证明其中必有一个数能整除另一个数。4、证明在n+1个小于等于2n的不同正整数中必有两数互素，其中n1。5、设nI+，证明在能被n整除的正整数中必存在只由数字7和0组成的数。6、任给52个整数，证明其中必有两数之和能被100整除或两数之差能被100整除。7、某工人在夜校学习，他打算用37天准备考试，并决定复习60小时，每天至少用1小时，证明他必定在接连的一些天内恰好共复习了13小时。8、求下列集合的基数，并加以证明。a)*，其中=a;b)有理数集合Q；c)x|xQ且0x1。9、证明全体从N到N的严格单调递增函数组成的集合和基数大于。10、证明N的全体有限子集组成的

32、集合是可列的0。3、设a,b,g,d为基数，0ab且gd，证明a+gb+d，agbd且agbd。4、设A为集合，#(A)= a，证明#(A)=2a。5、设B= f| f:RR且f是连续的，证明#(A)=。6、证明=2。习题7.11. 画出图G=的图示，指出其中那些图是简单图。a) V=n1, n2, n3, n4, n5 E=e1,e2,e3,e4,e5,e6,e7y=, b) V=n1, n2, n3, n4, n5E= e1,e2,e3,e4,e5,e6,e7,e8,e9,e10y=, ,c) V=n1, n2, n3, n4, n5, n6, n7, n8E= e1,e2,e3,e4,e

33、5,e6,e7,e8,e9,e10,e11y=, ,2. 写出图抽象数学定义。3. 证明在n阶简单有向图中，完全有向图的边数最多，其边数为n(n-1)。4. 证明3度正则图必有偶数个结点。5. 在一次集会中，相互认识的人会彼此握手。试证明与奇数个人握手的人数是偶数。6. 证明图的两个图同构。7. 证明：在任意六个人中，若没有三个人彼此都认识，则必有三个人彼此都不认识。8. 证明图的两个图不同构。9. 图两个图是否同构？说明理由。10. 证明任何阶大于1的简单无向图必有两个结点的度相等。11. 设n阶无向图G有m条边，其中nk个结点的度为k，其余结点的度为k+1，证明nk=(k+1)n-2m。习

34、题7.21. 画出K4的所有不同构的子图，并说明其中哪些是生成子图，并找出互为补图的生成子图。2. 设G=是完全有向图。证明：对于V的任意非空子集V，GV是完全有向图。3. 画出图的两个图的交、并和环和。4. 设G是任意6阶简单无向图。证明G或者必有一个子图是3阶完全无向图。5. 我们称与其补图同构的简单无向图为自补图。证明每个自补图的阶能被4整除或被4除余数为1。6. 证明没有子图是3阶完全无向图的n阶简单无向图最多有n2/4条边。习题 7.31. 考虑图.a) 从A至F的路径有多少条？找出所有长度小于6的从A至F的路径。b) 找出从A至F的所有简单路径。c) 找出从A至F所有基本路径。d)

35、 求出从A至F的距离。e) 求出该图的直径。f) 找出该图的所有回路。2. 证明图中的基本路径必为简单路径。3. 考虑图a) 对于每个节点n，求R(n)。b) 找出所有强分支，单向分支，弱分支。4. 设n1, n2, n3是任意无向图（有向图）G的三个任意节点，以下三公式是否成立？如果成立给出证明，如果不成立举出反例。a) d(n1, n2) 0,并且等号成立当且仅当n1 = n2。b) d (n1, n2) = d (n2, n1)。c) d (n1, n2) + d (n2, n3) d (n1, n3)。5. 证明有向图的每个节点和每条边恰处于一个弱分支中。6. 有向图的每个节点（每条边

36、）是否恰处于一个强分支中？是否恰处于一个单向分支中？7. 证明无向图是连通的当且仅当G的直径是自然数。8. 证明同阶的回路必同构。9. 设图G=，其中V=1, 2, 3, 4, 5, 6, 7, 8，E=a, b, c, d, e, f, g, h, i, j, k, l, m, n, p，y=a,b,c,d,e,f ,g,h,i, j,k, l , m , n, p ,。判断G是否有有向回路。10. 设G是弱连通有向图。如果对于G的任意节点n皆有，则G恰有一条有向回路。试证明之。11. 证明有k个弱分支的n阶简单有向图至多有(n-k)(n-k+1)条边。12. 证明非连通简单无向图的补图必定

37、连通。13. 设G为n阶简单无向图，对于G的任意节点n，证明G是连通的。14. 证明：对于小于或等于n的任意正整数k，n阶连通无向图有k阶连通子图。15. 图给出了一个加权图，旁边的数字是该边的加权长度，求出从n1到n11的加权距离。习题 7.41. 确定图的六个图哪个是欧拉图，欧拉有向图，哈密顿图，哈密顿有向图，找出其中的一条欧拉闭路，所有的哈密顿回路和哈密顿有向回路（如果存在的话）。2. 如果G1和G2是可运算的欧拉有向图，则G1G2仍是欧拉有向图。这句话对吗？如果对，给出证明，如果不对，举出反例。3. 设n是大于2的奇数，证明n阶完全无向图有(n-1)/2个边不相交的哈密顿回路。4. 设

38、n 3，对于n阶简单无向图G的任意两个不同节点n和n，只要它们不邻接就有dG(n) + dG (n) n。试证明G是哈密顿图。5. 基础图是完全无向图的有向图有哈密顿路径，试证明之。6. 设G是非平凡的连通无向图，证明G是欧拉图当且仅当G是若干个边不相交的回路之并。7. 设G是非平凡的弱连通有向图，证明G是欧拉有向图，当且仅当G是若干个边不相交的有向回路之并。习题7.51. 写出图各图的邻接矩阵和关系矩阵，由邻接矩阵求出路径矩阵和距离矩阵，并确定图的直径。2. 如何由邻接矩阵判断图的连通性？3. 如何由邻接矩阵判断图是不是非循环图？4. 如何由邻接矩阵判断有向图是否有有向回路？习题7.61.

39、画出所有不同构的一、二、三、四、五、六阶树。2. 如何由无向图G的邻接矩阵确定G是不是树。3. 设n和n是树T的两个不同结点，从n至n的基本路径是T中最长的基本路径。证明dT(n)=dT (n)=1。4. 找出图的连通无向图的一个生成树，并求出它的圈秩和余圈秩。5. 证明或以反例反驳以下命题：任意连通无向图的任何一条边都是它的某个生成树的枝，并且也是另一个生成树的弦。6. 求图的最小生成树。7. 设计一个“破圈法”求最小生成树的算法。8. 证明任何二叉树有奇数个结点。9. 证明n阶二叉树有个叶，其高度h满足log2(n+1)-1 h 。10. 由有向图G的邻接矩阵如何确定G是不是有向树。11. 找出叶的权分别为2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41的最优叶加权二叉树，并求其叶加权路径长度。12. 找出图给出的有序森林对应的定位二元有序树，并求其前缀编码。