是怎么回事-暖色头像

组合数学及其图论
1、一个图G是指一个有序三元组（V（G），E（G），

G
），其中

G
是：
________________ .
关联函数
2、
是有40个点的简单图且
。
39
3、只有一个顶点所构成的图称为：________________
平凡图
4、如果H是G的子图，其中V（H）=V（G）和E（G）=E（H）至少有一个不成立，
就 称H是G的：_____________.
真子图
5、设G是p阶简单图，则__________________等号成立当且仅当G是完全图。
q(G)

p(p-1)2
6、如果一条途径的_________与___________相同，就称这条途径为闭途径。
起点 终点
7、如果对图G=（V，E）的任何两个顶点u与v，G中存在一条（u-v） 路，则称
G是___________否则称为是______________
连通图、 非连通图
8、设G是P阶连通图，则__________________.
q(G)

p-1
9、若二分图

10、若G是2-边连通图，则G有强连通的________________.
定向图
11、边数最少的连通图是 。
有Hamilton回路，则 与 满足 。
中任两个点之间有且只有1条路，则

16 页 第 1 页

共

树
12、没有回路的连通图称为_______________.
树
13、
的图是 图或 图。
平凡图，不连通图
14、树T的每一个非悬挂点都是T的 __________.
割点
15、二分图 中若

与 满足 ，则 必有完美对集。
16、给定一个图G，如果图G的一个生成子图T是一棵树，则称T是G的一个
_______________.
生成树
17、设G是无环图，e是G的一 条边，则

(G)=___________________________.

（G－e）+

(G·e)
，等号成立当且仅当 是 图。
18、
是 阶简单图，则
，完全图 2、
19、___________________________的生成树称为最优生成树。
连通赋权图中具有最小权
20、
中无
的一个对集
可扩路
是最大对集的充要条件是 。
21、一个有向图D，如果略去每条弧的方向 时所得无向图是一棵树，就称D为
_____________________.
有向树
22、经过G的每条边的迹称为G的Euler迹，如果这条迹是闭的，则称这条闭迹
为G的 ________________.
Euler环游
23、

是简单图且 ，则 。

16 页 第 2 页

共

24、若 是 -正则图，则

。
25、简单图 满足 ，则 是 图。
不连通图， 平凡图
26、
2
27、树 恰有两个悬挂点，则

28、
连通
有生成树的充要条件是 。
30
29、若
1
30、
，
31、若 是 的一个对集，则 ，等号成立当且仅当是 对集。
阶图 是连通图，则 。
是有31个点的连通图且 中每条边都是割边，则 。
。
的图 是 图或 图。
完美对集
32、每位上的数字互异且非零的两位数共有____________个。
72
33、现在有10双不同的鞋。为了保证能够有一双鞋被选出，至少要从这20只鞋
中取出__ __________只鞋。
11
23
34、
(x
1x
2
x
3
x
4
x
5
)
7
展开式中
x
1
x
3
x
4
x
5
的系数为____________。
420
35、序列 1, c, c
2
, „, c
n
, „的生成函数是_______________。
f(x)
1
|cx|1
;
1cx
36、数值函数f和g的卷积f *g的通项f *g (r) = 。

16 页 第 3 页

共


f (i)g(ri)
i0
r
r0
.
37、叙述下列概念：发点，收点，中间点。
参考要点：D包含两个特定的顶点x和y，x设 有向连通图D=（V，A）满足：仅
有出弧而没有入弧，称为发点；y仅有入弧而没有出弧，称为收点； D中其余顶
点既有出弧有入弧，称为中间点。
38、在一次围棋擂台赛中，双方各出n名选手。规则是双方先各自排定一个次

序 ，设甲方排定的次序是
1
，
2,
，
x
x
x
n
，

y
n
。乙方排定的次序为
y
1
，< br>y
2
，
x
1
与
y
1
先比赛，胜的一 位与对方下一位选手比赛。按这种方法直到有一方的
最后一位选手出场并输给对方，比赛结束。问最多进 行几场比赛可定胜负（假定
比赛无平局）。
参考要点：建立一个有向图D=（V，A），V= {
1
如果
x,x
2
,

,x
n
, y
1
,y
2
,,y
n
}，
x
i
与
y
i
之间连一条弧，其方向从胜者指向负者。则D的每一条弧对应
一场比赛 ，D中弧的数目就是这次比赛的次数。根据规则，每一名选手至多输
一场，所以D中每个顶点的入度至多 为1，但
x
n
,y
n
必有一个入度为1，另一个
为0。

A

(d
D
(x
i
)d
D
(y
i
))2n1
，即至多2n-1场比赛可定胜负。 i1
n
39、用一些圆面覆盖平面上取定的2n个点。试证：若每个圆面至少覆盖n+1 个
点，则任两个点能由平面上的一条折线所连接，而这条折线整个地被某些
圆面所覆盖。
参考答案：构造图G=（V，E）如下：V就取平面上给定的2n 个点，两个不同的
顶点如果 含在同一个圆面上，就在这两个顶点之间连上一条边（边也含在这个平
面上）。所得图是一个简单图，而 且每个顶点的度至少是n，即

16 页 第 4 页

共


(G)n


2n

，由推论，G是连通 图，所以G中任两点之间有一条路连接。

2

由G的构造，这条路被若干 个圆面覆盖。
40、在二元正则树T中，它的分支点数和树叶数t满足：r=t-1。
参考 答案：因为正则二元树T的弧数为r+t-1，顶点度数的总和为2+3（r-1）+t。
由顶点度数与 边数的关系，有2（r+t-1）=2+3（r-1）+t得r=t-1。
41、某编辑部收到由n个 人所寄的一些问题的解，他们发现每个人寄来四个不同
问题的解，每个问题的解恰好由两个人同时给出。 问他们共收到几个不同问题的
解。
参考答案：首先建立图G=（V，E），G的n个顶点代表 n个人。两个不同的顶点
v
i
和
v
j
之间连接的边数等于这 两个点所对应的两个人同时给出相同问题解的
个数。由条件，G的每一条边对应一个问题的解，每个顶点 的度为4。因而共收
到q（G）=2n个不同问题的解。
42、有十七位学者，每一位都给其 余的人写一封信，信的内容是讨论3个论文题
目中的任一个，而且2个人相互通信所讨论的是同1个题目 。证明至少有三位学
者，他们之间通信所讨论的是同一个论文题目。
参考答案：做一个完全子 图
K
17
，它的17个顶点代表17位学者，把其中的边
K
17。由定理
3色完全图
染成3种颜色：如果两个学者讨论的是第i个题目，就将连接相应的2 个顶点的
边染上第i种颜色（i=1，2，3）。这样就得到3色完全图
r
3
3(r
2
1)23(r(3,3)1)217
。因此，这个
K
17
中有一个同色三角形。这个同色三角形所对应的3位学者之间通信所讨论
的是同一 个论文题目。
43、证明
K
3,3
和
K
5
是非平面图。

16 页 第 5 页

共

参考答案：
K
3,3
含有6个顶点，9条边，但最短回路长度为4，不满足
g2g
q( G)p
，因此不是平面图。
K
5
有5个顶点，10条边，不
g 2g2
满足
q(G)3p(G)6
，故不是平面图。
44、在一次象 棋擂台赛中,双方各出n名选手.比赛的规则是双方各自排定一个次
序,设甲方排定的次序为x
1,
x
2
,„, x
n
,乙方排定的次序为y
1
,y
2
,„,y
n .
x
1
与y
1
先
比赛,胜的一位与对方输的下一位选手比赛.按这种方 法进行比赛,直到有一方的
最后一位选手出场比赛并且输给对方,比赛就结束,问最多进行几场比赛可定 胜
负(假定比赛不出现平局)?
参考要点：建立一个有向图D=(V,A),V={ x
1,
x
2
,„, x
n
, y
1
,y
2
,„,y
n
},如果x
i
与
y
i
进行过一场比赛,就在x
i
与y
i
之间连一条 弧.其方向从胜者指向负者,则D的每
一条弧对应一场比赛,D中弧的数目就是这次比赛的次数.根据比 赛的规则,每一
名选手至多输一场,故D中每个顶点的入度至多为1,但x
n
与y
n
必有一个入度为
1,另一个为0.因此
|A|


(d
D
(x
i
)d
D
(y
i
))2n1

i1
n
即至多进行2n-1场比赛就可以确定胜负。
45、平面上有n条 线段,n≥3,其中任意3条都有公共端点.证明这n条线段有一
个公共端点。
参考要点：设 G是连通图,则G中任意两个不同的顶点
v
i
与
v
j
之间有 一条路连接.
(l)
若记这条路的长度为
l
,显然
lp1
.则
r
ij
a
ij
1
.而对于任意的
i(1 ip)
,
因G连通,且
p(G)3
,则有
(2)
r
ii
a
ii
d
G
(v
i
)0
,所以R(G)中没有零元素.
设
v
i
与
v
j
是G中的任意两个不同的顶点.因为
(2)(p1)
r
ij
a
ij
a
ij
a
ij
0

(l)(1)
存在
1lp1< br>,
a
ij
0(a
ij
a
ij
)
,则在G中有一条长为
l
的途径连接
v
i
与
v
j< br>.因

16 页 第 6 页

共

而从< br>v
i
与
v
j
有一条路,故G是连通图。
46、证明任意六个人中有三个人互相认识，或有三个人互不认识。.
证：构图 如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个
或
。若 中有任意两
人互相认识。则对于图中任意一个点
。不妨设 及它的3个邻点为
个点，不妨设为 ，相邻，则 对应的3个人互相认识；否则，
任意两个点不邻，即它们对应的3个人互不认识。
47、给定图 ：

1、给出图 的一个生成树；
2、给出图 的点连通度；
3、给出图 的最大对集；
4、给出图 的一个最长回路；
5、给出图 的直径和半径。


答案
1、




2、3
3、
第 7 页

共

16 页
中

4、
5、2 ，2

48、试给出一个算法,求连通赋权图中最大权的生成树.
算法：
1)在 中选取边 ，使 尽可能的大；
，则在 中选取边 ，2)若已经选定边
使满足以下两条：
I. 不含回路；
II. 在满足Ⅰ的前提下，使
3）当2)不能继续执行时，停止。
49、设是连通简单图，证明
仍是连通图。
证： 是连通简单图，设其最大度点为
保距生成树，则
为
即
50、对下图
，则
连通。
，求一个最优生成树。
中存在
尽可能的大。
个顶点，使得
。设 是 关于 的
，故 中至少有
连通，是
个悬挂点，不妨设
的生成子图，


答案

16 页 第 8 页

共

51、证明任意六个人中有三个人互相认识，或有三个人互不认识。.
证：构图 如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个
或
。若 中有任意两
中
人互相认识。则对于图中任意一个点
。不妨设
个点，不妨设为
及它的3个邻点为
，相邻，则 对应的3个人互相认识；否则，
任意两个点不邻，即它们对应的3个人互不认识。
52、给定图

问：1、作图
2、给出图
3、给出图
4、给出图
5、作出图

的一个最长回路 ；
的一个生成树；
的点连通度；
的最大对集；
的闭包。
答案

16 页 第 9 页

共

1、


2、


3、 3
4、
5、


53、试证明：如果无环图G的任意两顶点都被唯一的路相连，则G是树。
参考答案：
证明：由于G中任意两顶点都被唯一的路相连，故G连通。
若G含有圈C，则C上的两点，在G中存在两条路相连，这与题设的“唯
一”矛盾。故G中不含圈。
由树的定义知道：G是树。
54、有n张纸牌，每张纸牌的正反两面都写上1，2，......n的某一个数。
第 10 页

共 16 页

证明：如果每个数字都恰好出现两次，那 么这些纸牌一定可以这样摊开，使朝上
的面中1，2，3„„n都出现。
参考答案：
证明：作一二分图G=（X，Y；E），其中X={1，2，„„„n},Y={y
1

y
2
„„.
y
n
}表示这张牌。i与yj之间连接的边 数等于数i在纸牌yj出现的次
数，这样得到的图G是一个2正则二分图。则G中存在一个完美对集，设 为M={1y
i
1

2y
i
2
„„.n
y
i
n
}则只要把纸牌y
i
1
中的1朝上，y
i2
中的2朝下，y
i
n
中的n朝上，
这样摊开的纸牌就能使朝上 的面中1，2，3„„..n都出现。

55、证明边长为2的正方形内任意5个点必有两点，其距离不超过
2
。
< br>证：构造抽屉如图，将5个点放在4个边长为1小正方形内，由抽屉原理，必
有一个小正方形内至 少有两个点，这两个点的距离就小于或等于
2
。



0r3

2
56、
设数值函数a
r


r
,求前向差a.

25r4
< br>0r3

2
解：
设数值函数a
r

< br>r
,求前向差a.


25r4
a
r
2200r2

a
3
2
4
523
1

16< br>a
r
2
(r1)
52
r
52< br>r1
a{0,0,0,3

r4

1
, 2
5
,2
6
,...,2
r1
,...}< br>
16
57、设数值函数f = {1,2,2
2
,2
3
,...}，g = {1,3,3
2
,3
3
,...}，求3f-5g的生成
函数。

解：数值函数f = {1,2,22,23,...}和g = {1,3,32,33,...}的生成函数
第 11 页

共 16 页

F(x)12x2
2x
2
2
3
x
3
...1(2x)(2x)< br>2
(2x)
3
...

1
.(|2x|1)
12x
G(x)13x3
2
x
2
3
3< br>x
3
...1(3x)(3x)
2
(3x)
3...

1
.(|3x|1)
13x
所以3f5g的生成函数为
< br>35
3F(x)5G(x).
12x13x
58、设初始值h(0) = 0, h(1) = 1，h(2) = 2，求解递推关系
h(n) = h(n－1)+9h(n－2)－9h(n－3). (n = 3,4,...)
参考答案：
特征方程为：x- x- 9x+9 = 0
3 2
解得特征根为1, 3,-3.因此
h(n) = A1
n
+ B3
n
+ C(-3)
n
为一般解，由边界条件得

ABC0


A3B3C1


A9B9C2

解此线性方程组得唯一解
111

A-,B,C

4312
因此所求的解为
h(n)-
11
n
1
3(3)
n


4312
59、平面上给出25个点，其中没有任何3个点共线。这些点能确定多少 条直线？
多少个三角形？
解：由于没有3个点共线，所以每对点就确定一条直线，而直线的确 定与两个点
的次序无关，属组合问题，直线的总数为


25

25!
300


22!23!

每三个点确定一个三角形，因此所确定的三角形总数为
第 12 页

共 16 页


25

25!
2300


< br>3

3!22!
60、一个面包店有6种不同类型的面包，这些面包以每打12 个为单位向外出售。
这个面包店能装配成多少打不同的面包（不考虑面包的顺序）？如果在每打中每种类型的面包至少有一个，那么又能装配成多少打不同的面包？
解：假设面包店每种面包都有很多 （每种至少12个），由于每打中的面包与顺序
无关，故为组合问题，能装配成不同的面包的打数即为6 种类型的多重集（无
穷重数）的12-组合数，其值为


1261< br>
17

17






6188
种。

12

12

5

如果在 每打中每种类型的面包至少有一个，那么能装配成不同的面包的打
数可以看成为6种类型的多重集（无穷 重数）的6-组合数，其值为


661

11
 
11






462种。
6

6

5


n
n

n

n

61、试用生成函数求 下式之和：
1

2

3


n

.

1

2

3

n


n

i
解：设
F(x)


x(1x)
n

i0

i

n
两边求导再乘
x
得:

n

xF

(x)

i

x
i
n(1x)
n1
x

i0

i

n
令
x =
1

得:

n

n1
.
in2

i1

i

n
62．网络专业的学生选修C++ 的有38人，选修VB的有15人，选修DELPHI的
有20人，选修这三门课的同学总数为58人， 且其中只有3人同时选修这三门课，
试求同时选修两门课的同学有几人？
解：设A, B, C分别为选修C++, VB, DELPHI的同学的集合，则由
|ABC| = |A| + |B| + |C|  (|AB| + |AC| +|BC| ) + | ABC|
得
第 13 页

共 16 页

(|AB| + |AC| +|BC| )= |A| + |B| + |C| + | ABC|  |ABC|












= 38 + 15 + 20 + 3  58
= 18
同时选修两门课的同学有18人。
63、设简单图
G
中每个顶点的度至少是3，则< br>G
含有长为偶数的回路。
证明：设
Pv
0
v
1< br>v
t
是
G
的一条最长路，则
v
0
的所有邻 点全在
P
内，设
v
0
的邻
点为
v
i
1
,v
i
2
,,v
i
k
(1i
1< br>i
2
i
k
)
，其中
kd
G
(v
0
)3
，在
G
中取三个回路
C
1
v
0
v
1

v
i
2
v
0
C
2
v
0
v
1

v
i
k
v
0

C
3
 v
0
v
i
2
v
i
2
1

v
i
k
v
0
它们的长度分别为
i
2
1 ，i
k
1和i
k
i
2
2
。
这三个数 至少有一个是偶数。即
C
1
，C
2
，C
3
中至少有 一个是长为偶数的回路。
证毕。
64、树
T
的每一个非悬挂点都是
T
的割点。
证 明：设
T
是
p
阶树，即
d
T
(u)2
。 不难看出
Tu
含
p1
u
是
T
中一个非悬挂点，
个顶点，其边数为

q(T)d
T
(u)p1 d
T
(u)
=
p(Tu)d
T
(u)p(Tu) 1
，
因而
Tu
不是树。显然
Tu
不含回路，所以< br>Tu
非连通，即
u
是
T
的割点。
证毕。
65、若连通图
G
恰好有
2k(k0)
个奇点，则在G
中存在
k
条边不交的迹
Q
1
,Q
2
,

,Q
k
，使得

E
(< br>G
)
E
(
Q
1
)

E
(
Q
2
)



E
(
Q
k
)
。
证明：设
G
的
2k
个奇点为
x1
,x
2
,

,x
k
,y
1
,y
2
,

,y
k
，在
G
中增加
k
条分别连接
x
i
与y
i
的新边
e
i,i1,2,,k
，所得图记为
G

，则
G
是一个Euler图。记
G

的一
条Euler环游为
C

，然后在
C

中删除新加的
k
条边
e
1
,e
2
,

,e
k
，就将
C

分成
k
段，
这
k
段即为
G
的
k< br>条边不交的迹。
第 14 页

共 16 页

证毕。
66、若
p
阶图
G
没有孤立顶点，则

0
(G)

0
(G)p

证明：设
I
是
G
的最大独立集，
K
是
G
的最小点覆盖，则
V(G )K
是
G
的独立
集，
V(G)I
是
G
的点覆盖，所以

p

0
(G)V(G)K
I
=

0
(G)


p 

0
(G)V(G)IK

0
(G)

因此

0
(G)

0
(G)p
< br>67．在一次聚会上有10位男士和10位女士。这10位女士能够有多少种方法选
择男舞伴开始 第一次跳舞？如果每个人必须换舞伴，那么第二次跳舞又有多少种
选择方法？
解：对于第一次 跳舞，可以对10位男士和10位女士并排排列，如果10位男士
不改变次序，10位女士一个全排列就 是一种配对方式，共存在10! = 3628800
可能的选择；
对于第二 次跳舞，每位女士必须选择一位不是第一次与她跳舞的男舞伴，
因此可能的选择方法数为移位排列数


D(10)10!(1
1111111111
)

1!2!3!4!5!6!7!8!9!10!
= 1334961.
即第二次跳舞有1334961种选择方法。
68．求解满足初始值
h
0
= 1,
h
1
= 2,
h
2
= 0的递推关系

h
n
2h
n1
h
n2
2h< br>n3
n3
.
解：这个递推关系的特征方程

x
3
2x
2
x20

的3个根为 1, 1, 2，递推关系的解为

h
n
c
1
1
n
c
2
(1)
n
c
3
2
n
c
1
c
2
(1)
n
c
3
2
n

利用初始条件得c
1
, c
2
, c
3
满足的方程组为
第 15 页

共 16 页


c
1
c
2
c
3
1


c
1
c
2
2c
3
2


cc4c0
3

12
21
解得c
1
2,c
2
,c
3

，因此递推关 系的解为
33

21
h
n
1(1)
n
2
n
.
33
69、证明题 任取11个整数，求证其中至少有两个数，它们的差是10的倍数。
证明：设这11个整数为a
1
, a
2
, „, a
11
,它们被10除之后其余数为0 ~ 9之
间的整数，将0 ~ 9当作抽屉，由抽屉原理可知，在这11个整数中必有两个
数，不妨设为a
i
, a
j
, 它们二者的余数相等，从而a
i
 a
j
=10 n (n为一个整
数)，即a
i
与a
j
的差是10的倍数。


作业题：
1. 用0
～
9这十个数码可以组成多少个没有重复数码的四位数？
2. 一教室有两排座 位，每排8个，今有14名学生，5人总坐在前排，4人总在
后排，问学生入座有几种方式？
3.如果没有相邻的两个数在同一个集合里，由 {1, 2, ... , 20}中的数可形成
三个数的集合有多少种？
4设S ={
a
,
b
,
c
,
d
,
e, f
}，求S的所有4－组合(按字典序排列)。
5. 在一次聚会中，6个人寄存帽子，如果散会时没有 任何一个人得到他自己的
帽子，问有几种交还方式？

6.试求多重集B = {3
a
, 4
b
, 5
c
} 的10—重复组合数。
7.证明：在任意选取的12个正整数中，至少存在两个数，它们的差能被11整除。
8. 解非齐次递推关系

a
n
8a
n1
15a
n2
4,n2



a
0
0,a
1
1
第 16 页

共 16 页