文章目录

• 第八章 树
• • 2
  • 3
  • 4
  • 5
  • 6
  • 8
  • 10
• 第九章
• • 4
  • 6
  • 8
  • 11
• 第十章
• • 2
  • 4
  • 5
  • 6
  • 7
• 第十一章
• • 1
  • 4
  • 5
  • 7
  • 11
  • 16
• 第十二章
• • 1
  • 3
  • 13
  • 17

第八章 树

2

(2)

设有k片树叶

2∗m=2∗4+3∗3+k2*m=2*4+3*3+k2∗m=2∗4+3∗3+k

n=2+3+kn=2+3+kn=2+3+k

m=n−1m=n-1m=n−1

联立解得k=9

T中有9片树叶

3

有三颗非同构的生成树

4

(1)

c --abc

e–abed

f–dgf

h–abhgd

(2)

T的树枝a,b,d,g,对应的基本割集系统为{a,c,e,h},{b,c,e,h},{d,e,h,f},{g,f,h}

5

6

(1)

((a+b∗c)∗d−e)/(f+g)+h∗i∗j((a+b*c)*d-e)/(f+g)+h*i*j((a+b∗c)∗d−e)/(f+g)+h∗i∗j

(2)

+/−∗+a∗bcde+fg∗∗hij+/-*+a*bcde+fg**hij+/−∗+a∗bcde+fg∗∗hij

(3)

abc∗+d∗e−fg+/hi∗j∗+abc*+d*e-fg+/hi*j*+abc∗+d∗e−fg+/hi∗j∗+

8

简单图：不含环和平行边

不一定是树。未保证连通

10

在树中，仅有分支点和树叶点

故

i+t=ni+t=ni+t=n

又因边数m为i∗ri*ri∗r

m=n-1

i+t=i∗r+1↔t=i∗(r−1)+1i+t=i*r+1 \leftrightarrow t=i*(r-1)+1i+t=i∗r+1↔t=i∗(r−1)+1

第九章

4

（3）偶数个顶点，奇数条边

（4）奇数个顶点，偶数条边

6

（2）是欧拉图，而不是哈密顿图

（3）是哈密顿图，而不是欧拉图

8

11

A-D-C-B-A

第十章

2

deg(R1)=5

deg(R2)=3

deg(R0)=12

4

通过画图可知，无论怎样，两图都会有相交的边，故为非平面图

5

6

(1)点色数χ\chiχ

将原图标号，可得，1234为4阶圈，偶数阶，点色数为2。5与1,3不可同色，又1,3不同色，故色数+1。同理可知6,7。5,6,7不相邻，故可使用同一颜色着色。得出结论点色数χ\chiχ为3

(2)面色数χ′\chi'χ′

2与1,3相邻，与4不相邻，1,3不相邻。故1234的面色数为2。5与2相邻，与1,3不相邻。故可用于1,3同色的着色。6同理。故面色数为χ′\chi'χ′为2

7

实际为着色问题。要求有同时选修的课程，考试时间不同，也就是着色颜色不同。

1 2 3 5为4阶圈，偶数阶，点色数为2。4与1,3相邻，4与1,3颜色不同。1,3相邻，颜色不同。故点色数为3。至少需要3个

第十一章

1

(1)A53=5×4×3=60A_5^3=5\times4\times3=60A53​=5×4×3=60 种

(2)53=1255^3=12553=125 种

4

(1)

A1010A44×A33×A33=10!4!×3!×3!=4200{A_{10}^{10}\over{A_4^4\times A_3^3\times A_3^3}}={10!\over{4!\times3!\times3!}}=4200A44​×A33​×A33​A1010​​=4!×3!×3!10!​=4200 种

(2)

A77A33×A33=140{A_7^7\over{A_3^3\times A_3^3}}=140A33​×A33​A77​​=140 种

5

(1)

要求a之间不相邻，则将a之间的4个空 有顺序的插入{b c d e}即可。

A44=24A_4^4=24A44​=24 种

(2)

先将bcde排序，再往其中插入a。要求互不相邻，则内部的3个空一定得有a。多出的一个a插在bcde内部+外部共5个空其中一个即可

A44×C51=120A_4^4\times C_5^1=120A44​×C51​=120 种

7

盒子中容纳球可能的情况有：

(1)

2 2 0

$ {C_4^2\times C_2^2\times C_0^0\over A_2^2\times A_2^2 }\times A_3^3=9$ 种

(2)

2 1 1

$ {C_4^2\times C_2^1\times C_1^1\over {A_2^2}}\times A_3^3 =36$ 种

11

用全部情况减去5,6相邻

A97−A87A22=161280A_9^7-{A_8^7\over A_2^2}=161280A97​−A22​A87​​=161280 种

16

(1)不同的二元关系：

3元集的运算表共有9个位置，每个位置有3个值可选。故有39=196833^9=1968339=19683 个不同的二元关系

(2)自反的关系

自反的关系，对角线的三个位置为=x=x=x 固定。其余6个位置，每个位置有3个值可选。故有36=7293^6=72936=729 个自反的二元关系

(3)对称的关系

转为三角矩阵，只需确定对角线+右上角即可。故有36=7293^6=72936=729 个对称的二元关系

(4)自反且对称的关系

转为三角矩阵，对角线的三个位置为=x=x=x 固定，只需确定右上角即可。故有33=273^3=2733=27 个自反且对称的二元关系

(5)反对称的关系

39−36=189543^9-3^6=1895439−36=18954 个反对称的二元关系

第十二章

1

(1)

该递推方程的特征方程是 x2−2x−2=0x^2-2x-2=0x2−2x−2=0 ，特征根是

x1=1−3,x2=1+3x_1=1-\sqrt3,x_2=1+\sqrt3x1​=1−3​,x2​=1+3​

通解为c1(1−3)n+c2(1+3)nc_1(1-\sqrt3)^n+c_2(1+\sqrt3)^nc1​(1−3​)n+c2​(1+3​)n

带入初值a0=1,a1=3a_0=1,a_1=3a0​=1,a1​=3
c1+c2=1c1(1−3)+c2(1+3)=3解得c1=−33,c2=33c_1+c_2=1\\ c_1(1-\sqrt3)+c_2(1+\sqrt3)=3\\ 解得c_1=-{\sqrt3\over 3},c_2={\sqrt3\over 3} c1​+c2​=1c1​(1−3​)+c2​(1+3​)=3解得c1​=−33​​,c2​=33​​
(3)

该方程的常系数线性齐次递推方程的特征方程是 x2−3x+2=0x^2-3x+2=0x2−3x+2=0 ，特征根是

x1=1,x2=2x_1=1,x_2=2x1​=1,x2​=2

齐次方程通解为c11n+c22nc_11^n+c_22^nc1​1n+c2​2n

设特解形式为

H∗(n)=q1nH*(n)=q_1nH∗(n)=q1​n ，其中q1q_1q1​ 为待定系数，带入原式
q1n−3q1(n−1)+2q1(n−2)=13q1−4q1=1解得q1=−1q_1n-3q_1(n-1)+2q_1(n-2)=1\\ 3q_1-4q_1=1\\ 解得q_1=-1 q1​n−3q1​(n−1)+2q1​(n−2)=13q1​−4q1​=1解得q1​=−1
因此通解为an=c1+c22n−na_n=c_1+c_22^n-nan​=c1​+c2​2n−n

带入初值得an=3×2n−n+1a_n=3\times2^n-n+1an​=3×2n−n+1

3

an=7an−1+8n−1−an−1a_n=7a_{n-1}+8^{n-1}-a_{n-1}an​=7an−1​+8n−1−an−1​,a1=7a_1=7a1​=7

齐次特征方程为

x2−6x=0x^2-6x=0x2−6x=0

特征根为0或6，0舍去

齐次通解为an=c1×6na_n=c_1\times6^nan​=c1​×6n

设特解形式为

H∗(n)=q18nH*(n)=q_18^nH∗(n)=q1​8n ，其中q1q_1q1​ 为待定系数，带入原式

q18n=6×8n−1+8n−1q_18^n=6\times8^{n-1}+8^{n-1}q1​8n=6×8n−1+8n−1,q1=78q_1={7\over 8}q1​=87​

因此通解为an=c16n+78n−1a_n=c_16^n+78^{n-1}an​=c1​6n+78n−1

带入初值,通解为an=6n+8n2a_n={6^n+8^n\over 2}an​=26n+8n​

13

原题可理解为x1+x2+x3+x4=6且xi不超过3的非负整数解的个数。

G(y) = (1+y+y2^22+y3^33)4^44 = (1+2y+3y2^22+4y3^33+3y4^44+2y5^55+y6^66)2^22 = 1+…+44y6^66+…

​ N = 44.

17

指数生成函数为

Ge(x) = (1+x+x22!{x^2} \over {2!}2!x2​+x33!{x^3} \over {3!}3!x3​)(1+x+x22!{x^2} \over {2!}2!x2​)(1+x+x22!{x^2} \over {2!}2!x2​+x33!{x^3} \over {3!}3!x3​+x44!{x^4} \over {4!}4!x4​+x55!{x^5} \over {5!}5!x5​)

化简得x4x^4x4 的系数是71*x44!{x^4} \over {4!}4!x4​ ，因此a4 = 71.

若为偶数，末位为2，对应的指数生成函数为

Ge(x) = (1+x+x22!{x^2} \over {2!}2!x2​+x33!{x^3} \over {3!}3!x3​)(1+x)(1+x+x22!{x^2} \over {2!}2!x2​+x33!{x^3} \over {3!}3!x3​+x44!{x^4} \over {4!}4!x4​+x55!{x^5} \over {5!}5!x5​)

化简得x3x^3x3的系数是20*x33!{x^3} \over {3!}3!x3​ ， 因此a3 = 20.