当前位置:首页 >> 数学 >>

图论与组合数学期末复习题含答案


哈尔滨医科大学生物信息科学与技术学院

组合数学部分
第 1 章 排列与组合
例 1: 1)、求小于 10000 的含 1 的正整数的个数; 2、)求小于 10000 的含 0 的正整数的个数; 解: 小于 10000 的不含 1 的正整数可看做 4 位数,但 0000 除外.故有 9×9×9×9-1=6560 1)、 个.含 1 的有:9999-6560=3439 个 2)、“含 0”和“含 1”不可直接套用。0019 含 1 但不含 0。在组合的习题中有许多类似的隐含 的规定,要特别留神。不含 0 的 1 位数有 9 个,2 位数有 9 个,3 位数有 9 个,4 位数有 9 个 不含 0 小于 10000 的正整数有 9 ? 9 ? 9 ? 9 ?
1 2 3 4

1

2

3

4

?9

?1 ? 7380 个含 0 小于 10000 的 ?9 ? 1?
5

?

正整数 9999-7380=2619 个。 例 2: 从[1,300]中取 3 个不同的数,使这 3 个数的和能被 3 整除,有多少种方案? 解:将[1,300]分成 3 类: A={i|i≡1(mod 3)}={1,4,7,…,298}, B={i|i≡2(mod 3)}={2,5,8,…,299}, C={i|i≡0(mod 3)}={3,6,9,…,300}. 要满足条件,有四种解法: 1)、3 个数同属于 A; 2)、3 个数同属于 B; 3)、3 个数同属于 C; 4)、A,B,C 各取一数;故共有 3C(100,3)+1003=485100+1000000=1485100。 例 3: (Cayley 定理:过 n 个有标志顶点的数的数目等于 n
n?2



1) 、写出右图所对应的序列; 2) 、写出序列 22314 所对应的序列; 解: 1) 、按照叶子节点从小到大的顺序依次去掉节点(包含与此叶子 节点相连接的线) ,而与这个去掉的叶子节点相邻的另外一个内点值则记入序列。如上图所 示,先去掉最小的叶子节点②,与其相邻的内点为⑤,然后去掉叶子节点③,与其相邻的内 点为①,直到只剩下两个节点相邻为止,则最终序列为 51155.。 2) 、首先依据给定序列写出(序列长度+2)个递增序列,即 1234567,再将给出序列按 从小到大顺序依次排列并插入递增序列得到: 112223344567。 我们再将给出序列 22314 写在 第一行,插入后的递增序列写在第二行。如下图第一行所示:

22314 ? ? ⑤?? ② ? ?1122233445 67 ? ?? ?? ? ? ? ? 314 ? ?11233447 ?

2314 ? ? ?1122334467 ?

? ⑥?? ② ? ?? ?? ? ?

? ②?? ③ ? 14 ? ③?? ① ? ?? ?? ? ? ?113447 ? ?? ?? ? ? ? ?
图论与组合数学复习笔记 第 1 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

? 4 ? ①?? ④ ? ?1447 ? ?? ?? ? ? ?

? ? ? ?。 并在第二行寻找第一个无重复的元素 5 并将它取出, ? 47 ? 我们每次去掉第一行第一个数, ? ?
将⑤与②连接起来,并在第二行去掉第一行的第一个元素②,剩下的序列为 1122334467, 依次执行下去。最终剩下的两个元素(47)连在一起。则形成了以下的树。

例 4: 圆排列问题:从 n 个字符中取 r 个不同的字符构成圆排列的个数为 (

P?n, r ? ) ?0 ? r ? n?。 r

5 对夫妇出席一宴会,围一圆桌坐下有多少种方案?要求每对夫妇相邻而坐,方案有多 少种? 解:1) 、此问便是考查圆排列的公式定义,由 Q?n, r ? ? 方式有 Q?10,10 ? ?

P?10,10 ? 10! ? ? 9! 种。 10 10

P?n, r ? ?0 ? r ? n? 可得,排列 r

2) 、同样,先将 5 个丈夫进行圆排列则有

5! ? 24 种,再将 5 个妻子插到丈夫的空隙之 5
5

中,每个妻子只有两种选择,要么在丈夫的左边,要么在右边。因此由 2 种插入的方法, 所以一共有 4!?2 种。有错误!
5

例 5: (允许重复的排列) 已知重集 S ? ?6a,5b,4c,3d ?,做重集 S 的全排列,问有多少中排列方案? 解: 设可重复 S ? ?n1 ? a1 , n2 ? a2 ,?, nk ? ak ?,其中, a1 , a2 ,?, ak 为 S 中 k 个不同元 素,则 S 的个数为 n ? n1 ? n2 ? ? ? nk ,S 的全排列为:

n! n1!n2 !? nk !
则据题意可得:方案数为

18! 。 6!?5!?4!?3!

列 6: (允许重复的组合) 试问 ? x ? y ? z ? 有多少项?
4

解:由于 ?x ? y ? z ? ? ?x ? y ? z ? ?x ? y ? z ? ?x ? y ? z ? ?x ? y ? z ? ,相当于从右边每
4

图论与组合数学复习笔记 第 2 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

个括号里取一个元素相乘,而元素可以对应相同(如 4 个括号我都取 x)或者不同。这就相 当于将 4 个无区别的球放进 3 个有区别的盒子,由于在 n 个不同元素中取 r 个进行组合,允 许重复,则组合数为 C ?n ? r ? 1, r ? 。 (或者说 r 个无区别的球放进 n 个有区别的盒子里,每 个盒子球数不限,则共有 C ?n ? r ? 1, r ? 种) 。问题等价于从 3 个元素中取 4 个做允许重复的 组合, ? ?

? 4 ? 3 ? 1? ? 6 ? 6! 30 ??? ?? ? ? 15 项。 ? ? ? ? 4 ? ? 4 ? 4!2! 2

例 6: (线性方程的整数解个数问题) 已知线性方程 x1 ? x2 ? ? ? xn ? b , n 和 b 都是整数, n ? 1 ,求此方程非负整数解的 个数?

? 解:方程的非负整数解 ? 1 , ? 2 ,?, ? n ? 对应一个将 b 个无区别的球放进 n 个有区别的盒
子 ?x1 , x2 ,?, xn ? 的情况, 允许一盒多球, 故原式可以等价转化为将将 1 到 n 的正整数取 b 个 作为允许重复的组合,其组合数为 ? ? 例 7: (不相邻的组合) 从 A ? ? ,2,3,4,5,6,7?中取三个元素做不相邻的组合,有多少种方式? 1

? n ? b ? 1? ? 个。 ? ? b ?

1 解:由于从 A ? ? ,2,?, n?中,取 r 个作不相邻的组合,其组合数为 c?n ? r ? 1, r ? ,因
此在此题中 n ? 7, r ? 3 ,组合数种类有 ? ?

? 7 ? 3 ? 1? ? 5 ? 5! 120 ??? ?? ? ? 10 种。 ? ? ? ? 3 ? ? 3 ? 3!2! 12

例 8: (全排列的三种生成算法) (1) 、已知 m ? 4000 , 6!? 4000 ? 7! ,求 m 对应的序列。 (2) 、利用字典序法求求 839746521 的下一个排列。 解 :( 1 )、 由 于 0 到 n!?1 中 的 任 何 整 数 m 都 可 以 唯 一 表 示 为

m ? an?1 ?n ? 1?!?an?2 ?n ? 2?!?? ? a2 ? 2!?a1 ?1! 其中 0 ? ai ? i , 1 ? i ? n ? 1 ,可以证明从 0 到

n!?1 的 n! 个整数与 ?an?1 , an?2 ,?, a2 , a1 ? 一一对应,我们要得到这些值就得每次除以与其相
对应的数值,就可以得到与 a i 相对应的余数值 ri 。因为 6!? 4000 ? 7! ,所以:

n1 ? 4000 ? a6 ? 6!?a5 ? 5!?a4 ? 4!?a3 ? 3!?a2 ? 2!?a1 ,

6! 5! 4! 3! ? n ? ? 4000 ? n2 ? ? 1 ? ? ? ? ? 2000 ? a6 ? 2 ? a5 ? 2 ? a4 ? 2 ? a3 ? 2 ? a2 , a1 ? 0 ? r1 , ?2? ? 2 ?

图论与组合数学复习笔记 第 3 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

6! 5! 4! ? n ? ? 2000 ? n3 ? ? 2 ? ? ? ? ? 666 ? a6 ? 3! ? a5 ? 3! ? a4 ? 3! ? a3 , a2 ? 2 ? r2 , ?3? ? 3 ? 6! 5! ? n ? ? 666 ? n4 ? ? 3 ? ? ? ? ? 166 ? a6 ? 4! ? a5 ? 4! ? a4 , a3 ? 2 ? r3 , ?4? ? 4 ? 6! ? n ? ?166 ? n5 ? ? 4 ? ? ? ? ? 33 ? a6 ? 5! ? a5 , a4 ? 1 ? r4 , ?5? ? 5 ? ? n ? ? 33 ? n6 ? ? 5 ? ? ? ? ? 5 ? a6 , a5 ? 3 ? r5 , ?6? ?6? ?n ? ?5? n7 ? ? 6 ? ? ? ? ? 0, a6 ? 5 ? r6 , 所以: 4000 ? 5 ? 6!?3 ? 5!?1? 4!?2 ? 3!?2 ? 2! 。 ? 6 ? ?6?
把 n-1 个元素的序列 ?an?1 , an?2 ,?, a2 , a1 ? 和 n 个元素的排列建立一一对应关系,从而 得到一种生成排列的算法——序数法。将 ?an?1 , an?2 ,?, a2 , a1 ? 与给出序列相对应,例如给 出 4213,那么对应 ?a3 , a2 , a1 ? ,由大到小的计算当前数值位置右边比此位置数值大的数值 的个数,例如最大的数为 4,4 这个数右边有 3 个数比它小,所以 a3 ? 3 ,同理,第二个大 的数为 3,在 3 这个数右边有 0 个比它小的数,所以 a2 ? 0 ,同理对应 2 这个数右边有一个 数比他小,所以 a1 ? 1 。综上所述,对应序列为 ?301? 。 同时,由 ?301? 也可以推出最大数 4 的右边有 3 个比它小的数,为: 第二个大的数 3 右边比他小的数的个数为 0, 因此, 为: 4 第三个大的数 2 右边比他小的数有 1 个,而 1 的位置也 可以确定了因此为 4 2 1 3 3 4

(2) 、字典序法首先从序列 ? p1 , p2 ,?, pn ?后向前找出第一组 pi ?1 ? pi ,记下此式 pi ?1 的值,然后有从后向前找第一个比 pi ?1 的值大的数 p k ,并将 pi ?1 和 p k 调换位置,然后再将 原来 pi ?1(现在 p k )位置以后的全部序列倒序即可以了。如题中所示的序列 839746521 中, 首先找出从右向左第一组 pi ?1 ? pi 的 pi ?1 ,此处为 4,然后找到 p k 为 5,将它们两调换得到 839756421,然后将 5 后面的数逆序得到 839751246。 例 9: (格路模型) 一场电影的票价是 50 元,排队买票的顾客中有 n 位是持有 50 元的钞票, m 位是持有
图论与组合数学复习笔记 第 4 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

100 元的钞票。售票处没有准备 50 元的零钱。试问有多少种排队的方法方法使得购票能顺 利进行,不出现超不出零钱的状况。假设每位顾客只限买一张票,而且 n ? m 。 解: 在格路模型中, ?0,0? ? ?m, n ? 的路径选择有 从

?m ? n ?! ? ? m ? n ? ? c?m ? n, m ? 种。 ? ?
m!n! ? m ? ? ?

因为这个问题可以看成是由 m 个向右和 n 个向上组成,就是一个可重复的全排列问题。当 然, 将这一模型推广以后就可以应用于此题了, 我们将问题简化就可以得到卖票者从没有钱 到把所有票都卖完,在这个期间他必须实现每次卖票成功(即有足够的零钱找给顾客) 。在 格路模型中,我们把 x 轴看成是 m 个 100 元,y 轴看成是 n 个 50 元, 最重要实现将这 m 个 100 元和 n 个 50 元收入囊中, 而且要满足不出现找不出 50 元钞票的情况。问题等价于从

?0,0?到 ?m, n? 的路径中,找出 y>x 且不穿越(但可以接触)
y=x 线上点的路径。 然而不允许接触的情况是从 ?0,1? 点出发到

?m, n? 的所有路径减去从 ?0,1?点出发经过

y=x 的路径,如右

图所示,由对称性以及 n ? m 可以知道,从 ?0,1? 出发经过 y=x 的路径等于由 ?1,0 ? 出发到达

?m, n? 的路径,因为由 ?1,0 ? 出发到达 ?m, n? 必须经过 y=x。所以,原问题可以转化为:路径
数 =

c?m ? n ? 1, m? ? c?m ? n ? 1, m ? 1?
=

=

?m ? n ? 1?! ? ?m ? n ? 1?! ?m ? 1?!n! m!?n ? 1?!

?m ? n ? 1?! ? 1 ? 1 ? ? ? ?m ? 1?!?n ? 1?! ? m n ?

=

?m ? n ? 1?! ? 1 ? 1 ? 。然而,此处是可以接触 y=x 的,因 ? ? ?m ? 1?!?n ? 1?! ? m n ?
此我们可以将纵坐标向下移动一个单位如右图所示: 即可以接触 y=x 但是不可以穿过 y=x-1。 此时相当于从 (0,0) 到 ?m, n ? 点减去从 (0,0) 经过 y=x-1 到 ?m, n ? 点的路径, 而这一路径与从

?1,?1?



?m, n?

























= C ?m ? n, m? ? C ?m ? n, m ? 1? = ?m ? n ?! 例 10: (若干等式及其组合意义) 分别解释下列组式子的组合意义。 1) C ?n, r ? ? C ?n, n ? r ? 即 ? ? ? ? 、 ? ? ?

n ? m ?1 。 m!?m ? n ?!

?n? ? n ? ?; ? ?r ? ?n ? r?

图论与组合数学复习笔记 第 5 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

2) C ?n, r ? ? C (n ? 1, r ) ? C (n ? 1, r ? 1) 即 ? ? ? ? 、 ? ? ?

? n ? ? n ? 1? ? n ? 1? ??? ?; ? ? ? ? r ? ? r ? ? r ?1?

3) C (n ? r ? 1, r ) ? C (n ? r , r ) ? C (n ? r ? 1, r ? 1) ? ? ? C (n ? 1,1) ? C (n,0) ; 、 4) C (n, l )C (l , r ) ? C (n, r )C (n ? r , l ? r ), (l ? r ) 即 ? ?? ? ? ? ?? 、 ? ?? ? ? ?? 5) C (m,0) ? C (m,1) ? C (m,2) ? ? ? C (m, m) ? 2 , m ? 0 ; 、
m

? n ?? l ? ? n ?? n ? r ? ?; ? ? l ?? r ? ? r ?? l ? r ?

6) C (n,0) ? C (n,1) ? C (n,2) ? ? ? C (n, n) ? 0 ; 、 7) ? 、? 解: 1) C ?n, r ? ? C ?n, n ? r ? 即 ? ? ? ? 、 ? ? ?

? m ? n ? ? m ?? n ? ? m ?? n ? ? m ?? n ? ? ? ? ?? ? ? ? ?? ? ? 0 ?? r ? ? 1 ?? r ? 1? ? ? ? ? r ?? 0 ? ; ? ? ?? ? ? r ? ? ?? ? ? ?? ? ? ?? ? ?n? ? n ? ? 这个式子可以被看作是格路模型的应用,从 ? ?r ? ?n ? r?

?0,0?到达 ?r , n ? r ? 在 n 个格子上面先走 r 个格子, 剩下再走 n ? r 个格子, 这个和先走 n ? r
个格子,再走 r 个格子是一样的。 2) C ?n, r ? ? C (n ? 1, r ) ? C (n ? 1, r ? 1) 即 ? ? ? ? 、 ? ? ?

? n ? ? n ? 1? ? n ? 1? ??? ? ,这个式子组合意 ? ? ? ? r ? ? r ? ? r ?1?

义之一便是格路模型中的意义,从 ?0,0 ? 到 ?r , n ? r ? 的路径数可以被看成是 ? ? ,从 ?0,0 ? 到 ? ?

?n? ?r ?

?n ? r ? 1, r ? 的路径数可以被看成是 ? ?

? n ? 1? ? ,从 ?0,0 ? 到 ?n ? r , r ? 1? 路径数可以被看成是 ? ? r ?

? n ? ? ? r ?1? 。 就 是 说 我 们 从 ?0,0 ? 出 发 都 是 必 须 先 经 过 ?n ? r ? 1, r ? 或 ?n ? r , r ? 1? 再 到 达 ? ? ?

?r , n ? r ?的。还有一种模型便是从含有 a1 的 n 个数中取出 r 个数有几种取法的问题,首先我
们将取得的数分为两类:一类是取得的数中含有 a1 ,一类是不含有 a1 ,因此,含有 a1 的有 。不含有 a1 的有 C(n ? 1, r ? 1) 种取法(先将 a1 取出,再从剩余的 n ? 1 个数中取 r ? 1 个)

C (n ? 1, r ) 种取法。因此 C ?n, r ? ? C (n ? 1, r ) ? C (n ? 1, r ? 1) 。
3) C (n ? r ? 1, r ) ? C (n ? r , r ) ? C (n ? r ? 1, r ? 1) ? ? ? C (n ? 1,1) ? C (n,0) ,运用上 、

图论与组合数学复习笔记 第 6 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

题中的模型即可。 4) C (n, l )C (l , r ) ? C (n, r )C (n ? r , l ? r ), (l ? r ) 即 ? ?? ? ? ? ?? 、 ? ?? ? ? ??

? n ?? l ? ? n ?? n ? r ? ? ,左边相当 ? ? l ?? r ? ? r ?? l ? r ?

于从 n 个小球中取出 l 个小球,再从 l 个小球中取出 r 个,右边相当于从 n 个小球中先取出 r 个小球,由于这里面有重复度为 ? ? 这样一组合就相等了 5 ) 、 C (m,0) ? C (m,1) ? C (m,2) ? ? ? C (m, m) ? 2 , m ? 0 , 二 项 式 模 型
m

?n ? r? ? ,它等于从剩下的 n ? r 个小球中取出 l ? r 个小球, ? ?l ? r ?

? ?x ? y ?m ? ? ?

m? m ? m? ? x ? ? ? ? ? y m 。等式右边为将 m 个无区别的球放入 2 个有区别的盒子, ? ? m? ?0 ? ? ?

左边表示其中一个盒子分别装有 0 个,1 个,·,m 个球的组合数纸盒。 ·· 6 ) C (n,0) ? C (n,1) ? C (n,2) ? ? ? C (n, n) ? 0 ; 二 项 式 定 理 , 当 y ? ?x 时 , 、

? ?x ? y ?n ? ? ?
7) ? 、?

n? n ?n? ? x ? ? ? ? ? y n =0。 ? ?n? ?0? ? ?

? m ? n ? ? m ?? n ? ? m ?? n ? ? m ?? n ? ? ? ? ?? ? ? ? ?? ? ? 0 ?? r ? ? 1 ?? r ? 1? ? ? ? ? r ?? 0 ? ,等式左边相当于在有 m 个红球 ? ? ?? ? ? r ? ? ?? ? ? ?? ? ? ?? ?

和 n 个蓝球混合后从中取出 r 个球,等式右边相当于在取得的 r 个球中有 0 个红球和 r 个蓝 球,一个红球和 r ? 1 个蓝球,·,r 个红球和 0 个蓝球。 ··

第 2 章 递推关系与母函数
例 1: (母函数与递推关系) 利用母函数法求解满足递推关系 ?

? Fn ? Fn ?1 ? Fn ? 2 ?n ? 2 ? 的 Fibonacci 序列的解。 ? F0 ? F1 ? 1
2

解:首先,我们根据题意设母函数为 G?x ? ? F0 ? F1 x ? F2 x ? ? ,则:由

x x x3 ?)
可得: G ( x) ? 令 G ( x) ?
2

: : :

F2 ? F1 ? F0 F3 ? F2 ? F1 F4 ? F3 ? F2 ?????

1 。 1? x ? x2
A 1? 1? 5 1? 5 x 1? x 2 2 ? B
,解得 A ? B ?

1 。 2

图论与组合数学复习笔记 第 7 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

? ? ? ? 1? 1 1 ? , 令 ? ? 1? 5 , ? ? 1? 5 , 则 ? 因 此 , G ( x) ? 2 ? 1? 5 2 2 1? 5 ? x 1? x? ?1? 2 2 ? ?
1? 1 1 ? 1 2 2 G ( x) ? ? ? 1 ? ?x ? 1 ? ? x ? ,由 1 ? ax ? 1 ? ax ? a x ? ? 可得, ? 2? ?

G ( x) ?

1 2 ? ?? ? ? ?x ? ? 2 ? ? 2 x 2 ? ? 。 2
因此,递推关系式为 Fn ?

?

1 1 ? ?x ? ? 2 x 2 ? ? ? 1 ? ?x ? ? 2 x 2 ? ? = 2

??

? ?

??

?

?

?

?n ??n
2
n

,由于 ? ?

1? 5 ? 1, ? n ? 0 , 2

1 ?1? 5 ? ? 所 以 , Fn ? ? 2? 2 ? ? ?

, 即

Fn 1? 5 ? ? 1.618 Fn ?1 2

? Fn ? 1.6 1Fn81 , ?

Fn ? Fn?1 ? Fn?2 ? 0.618 Fn?1 。
例 2: (Fibonacci 序列的若干不等式) (1) 、证明: F1 ? F2 ? ? ? Fn ? Fn? 2 ? 1; (2) 、证明: F1 ? F3 ? ? ? F2 n?1 ? F2 n ; (3) 、证明: F1 ? F2 ? ? ? Fn ? Fn Fn?1 ;
2 2 2

证: 、 (1) 由于序列为 Fibonacci 序列, 所以有:Fn ? Fn?1 ? Fn?2 , 因此: F1 ? F3 ? F2 ,

F2 ? F4 ? F3



·

·

·



Fn ? Fn?2 ? Fn?1









F1 ? F2 ? F3 ? F4 ? ? Fn ? Fn? 2 ? F2 ? Fn? 2 ? 1 。
(2) 、由于序列为 Fibonacci 序列,所以有: Fn ? Fn?1 ? Fn?2 ,因此: F1 ? F2 ? 1 ,

F3 ? F4 ? F2 ,F5 ? F6 ? F3 ,·, F2 n?1 ? F2 n ? F2 n?2 , ·· 所以有 F1 ? F3 ? ? ? F2 n?1 ? F2 n 。
( 3 ) 由 于 序 列 为 Fibonacci 序 列 , 所 以 有 : Fn ? Fn?1 ? Fn?2 , 因 此 : 、

F2 ? F2 F2 ? F2 ?F3 ? F1 ? ,F3 ? F3 F3 ? F3 ?F4 ? F2 ? ,·· Fn ? Fn Fn ? Fn ?Fn?1 ? Fn?1 ? ·,
2 2 2

即 F1 ? F2 ? ? ? Fn ? Fn Fn?1 。
2 2 2

例 3: (线性常系数齐次递推关系)
图论与组合数学复习笔记 第 8 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

(1) 、求解 Fibonacci 数列 ?

? Fn ? Fn?1 ? Fn? 2 (n ? 2) 的递推关系。 ? F1 ? F2 ? 1
的递推关系。

(2) 、求数列 ?

?a n ? ? a n ?1 ? 3a n ? 2 ? 5a n ?3 ? 2a n ? 4 ( n ? 4) ?a0 ? 1, a1 ? 0, a 2 ? 1, a3 ? 2
2

解: 、由原式可得特征方程为 x ? x ? 1 ? 0 ,特征根为 x1 ? (1) 所 以 , 由 定 理 可 得

1? 5 1? 5 , x2 ? , 2 2

Fn ? c1 x1 ? c2 x2
n

n

。 又 由 F1 ? F2 ? 1 可 得 ,

? 1? 5 1? 5 1 ? ? c2 ?1 ? F1 ? c1 ?c1 ? 5 2 2 ? ? 带入上述式子可得: ?? 2 2 ? ? F ? c ? 1 ? 5 ? ? c ? 1 ? 5 ? ? 1 ?c ? 1 ? ? ? ? 1? 2? ? 2 ? 5 ? 2 2 ? 2 ? ? ? ? ? ? ?

1 ?1? 5 ? 1 ?1? 5 ? ? ? ? ? ? 。 Fn ? 5? 2 ? 5? 2 ? ? ? ? ?
(2) 有原式可得特征方程为 x ? x ? 3x ? 5x ? 2 ? 0 , 、 特征根为 x1 ? x2 ? x3 ? ?1 ,
4 3 2
2 x4 ? 2 所 以 , 由 定 理 可 得 an ? ?c1 ? c2 n ? c3 n ?x1, 2,3 ? c4 x4 n n

n

n

。 由 初 值 条 件

a0 ? 1, a1 ? 0, a2 ? 1, a3 ? 2 可以得到:

42 ? ?c1 ? 52 ? ?c1 ? c4 ? 1 ?c ? ? 29 ? ? c ? c ? c ? 2c ? 0 ? 2 ? 1 2 3 52 4 ,故递推关系式为: ?? ? c1 ? 2c2 ? 4c3 ? 4c4 ? 1 7 ? ?c ? ?? c1 ? 3c2 ? 9c3 ? 8c4 ? 2 ? 3 52 ? ? 10 ?c4 ? 52 ?

an ?

42 ?? 1?n ? 29 n?? 1?n ? 7 n 2 ?? 1?n ? 10 ? 2 n 。 52 52 52 52

例 4: (线性常系数非齐次递推关系) (1) 、求 ?

?an ? an ?1 ? 6an ? 2 ? 5 * 4n ?a0 ? 5, a1 ? 3

的递推关系。

解: 、由题意可得,此题为线性非齐次递推关系的求解,我们可以将 a n 表示为齐次 (1) 部分的通解加上特解,即 a n ? a n ? a n ,其中 a n 为特解, a n 为通解。对于其次部分,其
* *

图论与组合数学复习笔记 第 9 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

特征多项式为 x ? x ? 6 ? 0 ,解得特征解为 ?
2
* n n

? x1 ? 3 * n n ,我们设 a n ? c1 x1 ? c2 x2 ,所以 x 2 ? ?2 ?

an ? c1 ?3? ? c2 ?? 2? ,又因为 an ? b1an?1 ? b2 an?2 ? ? ? bk an?k ? f ?n ?, n ? k ,则可以得
n 出 f ?n ? ? 5 * 4 ,我们设 an ? A0 n ? A1n
k

?

k ?1

? ? ? Ak ?1n1 ? Ak n m ? n ,那么由题意可得

?

a n ? A0 * 4 n ,将此式带入原式可得 A0 * 4 n ? A0 * 4 n?1 ? 6 * A0 * 4 n?2 ? 5 * 4 n ,则解此式可
得 A0 ?

40 40 n * n n 。由 a n ? a n ? a n 可得 an ? c1 ?3? ? c2 ?? 2? ? * 4 ,又由 a0 ? 5, a1 ? 3 可 3 3

40 67 ? ? ?c1 ? c2 ? 3 ? 5 ?c1 ? ? 5 67 n 76 40 ? ? n 以得到 ? 解得 ? ,所以 an ? ? 3 ? ?? 2? ? ? 4 n 。 5 15 3 ?3c ? 2c ? 40 * 4 ? 3 ?c ? 76 1 2 2 ? ? 3 15 ? ?
说 明 : 若 a n 为 an ? b1an?1 ? b2 an?2 ? ? ? bk an?k ? f ?n ? 的 一 个 特 解 , a n 为
*

an ? b1an?1 ? b2 an?2 ? ? ? bk an?k ? f ?n ? 的一个通解,则 an ? an ? an 原非齐次递推关系
' *

的通解。 有以下结论: ①、若 f ?n ? 为 n 的 k 次多项式,则 an ? A0 nk ? A1nk ?1 ? ? ? Ak ,其中 A0 , A1 ,?, Ak 为 待定系数;若导出的常系数线性齐次递推关系特征根为 1 的 m 重根,则

an ? ( A0 nk ? A1nk ?1 ? ? ? Ak )n m 。
②、若 f ?n ? 为 b?n ?? 的形式,若 ? 是导出的常系数线性齐次递推关系的 m 重特征根,
n

b ?n ? 为 n 的 p 次多项式,则 an ? ( A0 nk ? A1nk ?1 ? ? ? Ak )n m ? n 。
例 5: (指数型母函数问题) 对于序列 a0 , a1 , a2 ,? 定义 Ge ?x ? ? a0 ? 型母函数。几个具有代表性的指数型母函数:

a a1 a x ? 2 x 2 ? 3 x 3 ? ? 为序列 ?a j ? 的指数 1! 2! 3!

1 (1) 、序列 ? ,1,1,??的指数型母函数为:
Ge ?x ? ? 1 ?
? 1 1 1 xj x ? x 2 ? x3 ? ? ? ? ? ex 1! 2! 3! j ?0 j!

(2) 、序列 ?0!,1!,2!, ?? 的指数型母函数为:

1! 2! 3! 1 Ge ?x ? ? 0!? x ? x 2 ? x 3 ? ? ? 1 ? x ? x 2 ? ? ? 1! 2! 3! 1? x
图论与组合数学复习笔记 第 10 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

(3) 、序列 1, k , k , k ? 的指数型母函数为:

?

2

3

?

Ge ?x ? ? 1 ? kx ?

k2 2 k3 3 x ? x ? ? ? e kx 2! 3!

(4) 、序列 ? ,1? 3,1? 3 ? 5,1? 3 ? 5 ? 7,??的指数型母函数为: 1

?1 ? 2 x ?? 2
3

若有 8 个元素,其中设 a1 重复 3 次, a 2 重复 2 次, a 3 重复 3 次。从中取 r (r ? 8) 个组 合,其组合数为多少? 解:设 c r 的母函数为: Ge ? x ? ? ?1 ? ?

? ?

x x 2 x 3 ?? x x 2 ?? x x2 x3 ? ? ? ??1 ? ? ??1 ? ? ? ? 1! 2! 3! ?? 1! 2! ?? 1! 2! 3! ? ?? ?? ?

9 2 14 3 35 4 17 5 35 6 8 7 1 8 x ? x ? x ? x ? x ? x ? x 2 3 12 12 72 72 72 3 1 2 1 3 1 4 1 5 1 6 1 7 1 8 = 1 ? x ? 9 ? x ? 28 ? x ? 70 ? x ? 170 ? x ? 350 ? x ? 560 ? x ? 560 ? x 。 1! 2! 3! 4! 5! 6 7! 8! 对应当 r ? 1 时,即从中取一个进行排列,排列数为 3,当 r ? 4 时,即从中取 4 个进行排列,
= 1 ? 3x ? 排列数为 70。 例 6: (整数的拆分问题) 若有 1 克的砝码 3 枚,2 克的 4 枚,4 克的 2 枚,问能称出哪些重量?各有几种方案? 解:由题意可得,我们设 G?x ? ? 1 ? x ? x ? x 1 ? x ? x ? x ? x 1 ? x ? x
2 3 2 4 6 8 4

?

??

??

8

?,

其中第一项表示 1 克砝码 3 个,第二项表示 2 克砝码 2 个,第三项表示 4 克砝码 2 个。借出 这个多项式可得:

G ?x ? ? 1 ? x ? 2 x 3 ? 3x 4 ? 3x 5 ? 4 x 6 ? 4 x 7 ? 5 x 8 ? 5 x 9 ? 5 x10 ? 5 x11 ? 4 x12 ? 4 x13 ? 3x14 ? 3x15 ? 2 x16 ? 2 x17 ? x18 ? x19
那么比如能称出 11 克的方法就有 5 种,因为 5x 。 例 7: (Stirling 数问题)
11

n 个有区别的球放到 m 个无区别的盒子中,要求无一空盒,其不同的方案数用 S ?n, m? 表
示,称为第二类 Stirling 数。即 S ?n, m? 是将 n 个数拆分成非空的 m 个部分的方案数。Stirling 数具有以下几点性质: 1) S ?n,0? ? S ?0, n ? ? 0, ?n ? N ; 、 2) S ?n, k ? ? 0, 若n ? k ? 1 ; S ?n, k ? ? 0, 若k ? n ? 1 ; 、 3) S ?n,1? ? S ?n, n ? ? 1, n ? 1 ; 、

图论与组合数学复习笔记 第 11 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

4) S ?n,2? ? 2 、 5) S ?n,3? ? 、

n ?1

?1 ;

1 n?1 3 ? 1 ? 2 n?1 ; 2
?n? ?2?

?

?

6) S ?n, n ? 1? ? C ?n,2 ? ? ? ? ; 、 ? ? 7) S ?n, n ? 2 ? ? ? ? ? 3? ? ; 、 ? ? ? ? 8) S ?n, m? ? mS ?n ? 1, m? ? S ?n ? 1, m ? 1?, n ? 1, m ? 1; 、

?n? ?3 ?

?n? ?4?

S ?n, m ? ?
9) 、

? m? 1 ? n ? m? n n m ?1 ? m ? n ? ?m ? ? ??m ? 1? ? ? ??m ? 2? ? ? ? ?? 1? ? ?1? ?2? ? m ? 1?1 ? ? m! ? ? ? ? ? ? ? ? 1 m?1 k ? m? n ? ?? 1? ? k ??m ? k ? ? ? m! k ?0 ? ?

?

以上式子的证明都可以用 Stirling 数的定义来证明,详见教材 P ~ P 。 101 102

n 个球放到 m 个盒子里 ?n ? m? ,依球和盒子是否有区别?是否允许空盒?共有多少种
状态?其方案计数分别列于下表。 编号

n 个球

m 个盒子

是否空盒

方案个数



有区别

有区别

有空盒

mn



有区别

有区别

无空盒

m!S ?n, m?
S ?n,1? ? S ?n,2? ? ? ? S ?n, m ?, n ? m S ?n,1? ? S ?n,2? ? ? ? S ?n, n ?, n ? m



有区别

无区别

有空盒



有区别

无区别

无空盒

S ?n, m? C ?n ? m ? 1, n ? C ?n ? 1, m ? 1?



无区别

有区别

有空盒



无区别

有区别

无空盒

图论与组合数学复习笔记 第 12 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院



无区别

无区别

有空盒

G?x ? ?
G?x ? ?

1 n 的 x 项系数 ?1 ? x ? 1 ? x 2 ? 1 ? x m

?
?

? ?
? ?

?
?



无区别

无区别

无空盒

xm n 的 x 项系数 2 m ?1 ? x ? 1 ? x ? 1 ? x

解释:②、当我们认为盒子无区别的时候,由 Stirling 数的定义可得有 S ?n, m? 种组合。 然后,将 m 个盒子进行全排列,共有 m!种全排列,因此全部的排列数为 m!S ?n, m? 。 ③、 对于无区别盒子有空盒情况的全排列, 我们可以转化为无区别盒子无空盒的情况解 决。即将非空盒数分为 1 个非空、2 个非空、·、 m 个非空的各种情况的加和的情况。因为 ·· 盒子无区别,所以不用考虑空盒子的情况。 S ?n,1? 表示只有 1 个盒子非空, S ?n,2? 表示只 有 2 个盒子非空, S ?n, m? 表示只有 m 个盒子非空,当然,这是球数 n 大于盒子数量 m 的结 果, 当球数小于盒子数时, 由性质 2) 可以得到最大的情况就是 n 个盒子不为空, S ?n, n ? , 为 综上所述,方案数为 ?

?S ?n,1? ? S ?n,2 ? ? ? ? S ?n, m ?, n ? m 种。 ?S ?n,1? ? S ?n,2 ? ? ? ? S ?n, n ?, n ? m

④、由 Stirling 数的定义可得。 ⑤、这个模型可以转化为从 m 个元素中取 n 个元素(允许重复抽取)做允许重复的组 合,则可以得出组合数为 C ?n ? m ? 1, m? 。 ⑥、我们的目的就是要将 n 个球放入 m 个有区别的盒子。首先,我们将 n 个球排成一 列, 之间共有 n ? 1 个空隙, 1 然后我们用隔板法将这列小球分成 m 部分, 而要将球分成 m 部 分,我们只需要 m ? 1 块隔板就可以了,问题就转化为将 m ? 1 块隔板插入 n ? 1 个缝隙共有 多少种插法,由分析可得有 C ?n ? 1, m ? 1? 种插法。 ⑦、 此模型可以转化为整数拆分模型, 目的就是将 n 个无区别的球拆分成 1,2,3,?, m 等 数的和的问题,所以母函数 G?x ? ? 1 ? x ? x ? ? 1 ? x ? x ? ? ? 1 ? x ? x
2 2 4 m

?

??

? ?

2m

?? ,

?

转化后即得出 G ? x ? ?

1 n 的 x 项系数即为整数 n 的拆分。 ?1 ? x ? 1 ? x 2 ? 1 ? x m

?

? ?

?

⑧、此模型也可以转化为整数拆分模型,首先,我们从 n 个球中选取 m 个球放进盒子 里面,保证每个盒子里面有一个球,这只有一种方法。然后将剩下的 n ? m 个无区别的球拆 分 成 1,2,3,?, m 等 数 的 和 的 问 题 , 但 是 此 处 是 取 其 中 x
n?m

项的系数,所以母函数

G?x ? ? 1 ? x ? x 2 ? ? 1 ? x 2 ? x 4 ? ? ? 1 ? x m ? x 2 m ? ? ,当然,如果仍然想取 x n 项系

?

??

? ?

?

图论与组合数学复习笔记 第 13 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

数, 我们将上式转化后即得出 G ? x ? ?

xm n 的 x 项系数即为整数 n ? m 的 2 m ?1 ? x ? 1 ? x ? 1 ? x

?

? ?

?

拆分,再乘以从 n 个球中选取 m 个球放进盒子里的方法数 1。

第三章 容斥原理
例 1: (容斥原理的基本定义) (1) 、一个学校只有三门课程:数学、物理、化学。已知修这三门科的学生分别有 170、 130、120 人;同时修数学物理两门课的学生有 45 人;同时修数学、化学的 20 人;同时修 物理、化学的 22 人;同时修三门科的学生 3 人。问这学校有多少学生? (2) 、把 n 本不同的书放入 m 个有编号的箱子中去(n≥m),使得没有一个箱子为空。 共有多少种方法? 解: (1) 、设 M 为修数学这门学科的学生集合, F 为修物理学科学生的集合, C 为修 化 学 这 门 学 科 的 学 生 集 合 。 则 根 据 题 意 可 得 , M ? 170 , F ? 130 , C ? 120 ,

M ? F ? 45 , M ? C ? 20 , F ? C ? 22 , M ? F ? C ? 3 。则根据容斥原理的定义可
得在校生人数为: M ? F ? C ? M ? F ? C ? M ? F ? M ? C ? C ? F ? M ? F ? C =170+130+120-45-20-22+3=336。 (2) 、对应于 n 个小球放入 m 个盒子模型中的第②种。但是,此处我们用容斥原理来 解决。首先,对应于原题条件,我们用 S ? m 表示盒子允许为空的放球放法数,然后用 Ai
n

表示第 i 个盒子为空的情况,那么 A1 ? A2 ? ? ? Ai ? Ai ?1 ? ? ? Am 表示所有盒子都不为 空的情况,由容斥原理可得:

A1 ? A2 ? ? ? Ai ? Ai ?1 ? ? ? Am ? S ? ? Ai ? ? Ai ? A j ? ? ?
i ?1 i? j

m

? ? ?? 1?m A1 ? A2 ? ? ? Am ? ? ?? 1?i ? ??m ? i ?n ?i?
m

m

i ?0

? ?

例 2: (有限制条件的排列) 从(0,0)点到(10,5)点的路径中,求不能过 AB, CD, EF, 的路径数, GH 其中 A (2,2) B(3,2), , C(4,2),D(5,2) E(6,2),F(6,3) ,G(7,2),H(7,3) 。 解: 如右图所示, 从左往右依次是 AB 、CD 、

EF 、 GH ,由题意可得,我们要求得是从 0,0 到

?10,5? 的路径数,即可表示为: AB ? CD ? CD ? EF ,由容斥原理可以的出:
AB ? CD ? CD ? EF ? S ? ? AB ? CD ? EF ? GH ? ? AB ? CD ? AB ? EF ? AB ? GH ? CD ? EF ? CD ? GH ? EF ? GH ? AB ? CD ? EF ? AB ? CD ? GH ? AB ? EF ? GH ? CD ? EF ? GH ? AB ? CD ? EF ? GH
图论与组合数学复习笔记 第 14 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

根据格路模型可以知道,经过路径 AB 可以被认为先从 ?0,0 ? 到 A?2,2? 的路径数再乘上 从 B?3,2? 到 ?10,5? 的路径数,那么,由此可得: S ? C ?10 ? 5,5? 。

EF : C ?6 ? 2,2? ? C ?10 ? 6 ? 5 ? 3,5 ? 3?
CD ? EF : C ?6,2? ?1? C ?6,2? AB ? CD : C ?4,2? ?1? C ?8,3?

AB : C ?2 ? 2,2? ? C ?10 ? 3 ? 5 ? 2,5 ? 2?

GH : C ?7 ? 2,2? ? C ?10 ? 7 ? 5 ? 3,5 ? 3?
AB ? GH : C ?4,2? ?1? C ?5,2? EF ? GH : C ?8,2? ? 0 ? C ?5,2?

CD : C ?4 ? 2,2? ? C ?10 ? 5 ? 5 ? 2,5 ? 2?

AB ? EF : C ?4,2? ?1? C ?6,2?

CD ? GH : C ?6,2? ?1? C ?6,2?

CD ? EF ? GH : C ?6,2? ?1? 0 ? C ?5,2?


AB ? CD ? EF : C ?4,2? ?1?1? C ?6,2?

AB ? CD ? GH : C ?4,2? ?1?1? C ?5,2?

AB ? CD ? EF ? GH : C ?4,2? ?1?1? 0 ? C ?5,2?


AB ? CD ? CD ? EF =3003-720-840-420-360+336+90+60+900+150+0-80-60-0+0=2049,因
此,共有 2049 种路径(仅供参考) 。

第四章 鸽巢原理
例 1: (鸽巢原理的证明: m 只鸽子, n 个巢,则至少有一个巢不少于 ?

? m ? 1? ? 1 只鸽子) ? n ? ?

(1) 、证明:若把 n ? 1个物体放到 n(n ? 1) 个盒子中去,则至少有一个盒子放有至少 2 个物体。 (2) 、证明:若在一个集合 S 中存在 n ? 1 个不相同的元素,那么在 S 中至少可以找出
2

一组由 n ? 1个元素组成的或未单调递增或者单调递减的子序列。 证明: (1) 、用反证法证明。如果 n 个盒子中每个盒子至多放入一个物体,则放入 n 个盒子中 的物体总数至多为 n 个。这与假设有 n+1 个物体矛盾。从而定理得证。 (2) 、我们从集合 S 中选取一个元素 a i ,再向后找比 a i 大的元素,直到后面再也没有 比它前一个元素还大的元素为止,例如,有一个序列如下: 5,3,16,10,15,14,9,11,6,7 从中可以找出不同的单调递增序列,例如: {5,16};{5,10,15};{3,9,11};{3,6,7}·· · 或者是单调递减的序列,例如: {5,3};{16,10,9,6};{16,15,14,11,7}·· · 我们设 S 中每一个元素 a i 都有若干个单调递增的子序列,但其中有一个最多的子序列, 设这个子序列的元素个数为 li , i ? 1,2,? n ? 1 ,于是得到序列 l1 , l 2 ,?, l n2 ?1 ,当序列某一个
2

元素 lk ? n ? 1 ,则已经符合要求,否则,设序列中不存在超过 n 个元素的单调递增子序列,
图论与组合数学复习笔记 第 15 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

2 即: 0 ? li ? n, i ? 1,2,?, n ? 1 ,这就相当于把 n ? 1 个小球放到 n 个盒子中取,由于此处
2

? n 2 ? 1 ? 1? ? m ? 1? ?1 ? ? m ? n 2 ? 1 ,则共有 ? ? ? 1 ? n ? 1 种。 n ? n ? ? ? ?
例 2: (Ramsey 二染色定理) 设 a、b 为正整数,令 R(a,b)是保证 a 个人彼此认识或 b 个人彼此不认识的所需最少人 数,则称 R(a,b)为 Ramsey 数。R(3,3)=6;R(4,3)=9;R(3,4)=9;R(4,4)=18。 注:这些定理只给出了几个 Ramsey 数的上界,并不一定是最好的结果。 证明:6 个人中一定有 3 个人相互认识或相互不认识。 证明: 、这类问题其实就是 Ramsey 二染色 (1) 问题。如右图所示,在六个人中,对于某个人 A , 要么他与别人相互认识、要么互不相识,所以存在 这两种情况。我们将另外的五个人分为 Friend 和 Stranger 两个集合,那么: Friend=其余 5 个人与 A 互相认识的集合; Stranger=其余 5 个人与 A 不互相认识的的人; 依据鸽巢原理,在 Friend 集合或者 Stranger 集 合里至少有 3 个人,假设是在 Friend 集合里有 3 个 人分别是 B、C、D,那么依据鸽巢原理可得在这个 Friend=5 的集合中,至少有 ?

? Friend ? 1? ? ? 1 ? 3 个人相互认识或者不认识,如果 3 个人互 2 ? ?

相不认识,那么满足题意“至少有 3 个互不认识” ,否则其中两个人 B、C 相互认识,又因 为 A 与 Friend 集合里面的人互相认识,所以至少有 A、 C 相互认识。同理, B、 对于 Stranger 集合也是一样的。

图论部分
第五章 图的基本概念
例 1: (图的定义) 一个图 G 定义为一个偶对 ?V , E ? ,记作 G ? ?V , E ? ,其中: (1) V 是一个集合,其中的元素称为顶点; 、 (2) E 是无序集 V 到 V 中一个子集合,气元素称为边,其中的元素可在 E 中出现不 、 止一次。 二部图(二分图):设 V1 和 V2 是 G 的顶点子集 ,使

V1 ? V2 = V ?G ? , V1 ? V2 ? ? ,且 G 的每条边的一个端
点在 V1 中,另一个端点在 V2 中,则称 G 为二部图,记

G ? ?V1 ,V2 ; E ? 。

图论与组合数学复习笔记 第 16 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

完全二部图:如果 V1 中的顶点和 V2 中的每一个顶点都邻接,则称为完全二部图,记为 Kn,m。 补 图 : 设 G ? V , E 为 完 全 图 , G1 ? V , E1 , G2 ? V , E2 为 简 单 图 , 其 中

E1 ? E2 ? ? , E1 ? E2 ? E ,则称 G1 ,G2 相对于 G 互为补图,记 G1 ? G2 , G2 ? G1 。
生成子图:设图 G ? V , E ,一个满足 (1) V ?H ? ? V ?G ? ; 、 (2) E ?H ? ? E ?G ?; 、 的真子图,叫做 G 的生成子图(spaning graph) (条件:点同边少) 。 对于途径 ? ? ? 0 e1?1 ?? n?1en? n (其中 ? i 表示顶点, e i 表示两顶点之间相连的边) ,若 其中 e1e2 ?en 均不同,则称为链(chian) 。所有顶点 途径 点、边可相同 闭 链 边不同 回路(闭链) 圈

? 0?1 ?? n 均不相同(从而所有边都必然不相同)的路径 道路 点不同
称为道路(path) 。一条封闭的道路成为圈(cycle) 。

设 u, v 是图 G 中的两个顶点,若 G 中存在一条 ?u, v ? 道路,则称顶点 u 和 v 是连通的 (connected).如果图 G 中每一对不同的顶点 u, v 间都有一条 ?u, v ? 道路,则称图 G 是连通 的.若以 u ? v 表示顶点 u 与 v 是连通的, 那么这种顶点间的连通关系是一个等价的关系, 即: 1) u ? u (反身性) 、 ; 2) u ? v ,则 v ? u (对称性) 、 ; 3) u ? v, v ? w, 则 u ? w (传递性) 、 ; 每一个等价关系确定一个类,这些类称为 G 的连通分支或简称为分支 (compouent), 分支的个数记为 k ?G ? 。 环和(ring sum): G1 ? G2 在 G1 和 G2 的并中去掉 G1 和 G2 的交所得到的图,即

G1 ? G2 ? ?G1 ? G2 ? ? ?G1 ? G2 ? ? ?G1 ? G2 ? ? ?G2 ? G1 ? 环合运算满足交换律和结合律。

第六章 树
例 1: (破圈法和避圈法) 给定图 T,以下关于树的定义是等价的。 1)、无回路的连通图。 2)、无回路且 e ? v ? 1其中 e 是边数, e 是结点数。 3)、连通且 e ? v ? 1。 4)、无回路,但增加一条新边,得到一个且仅有一个回路。
图论与组合数学复习笔记 第 17 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

5)、连通,但删去任一边后便不连通。 6)、每一对结点之间有一条且仅有一条路。 如果图 G 中删去一条边后,图 G 的分支数增加,则称此边位 G 的割边(cut-edge)。如 果图中去掉一个顶点(同时去掉与该点关联的所有边)后图的分支数增加,则称该点为 G 的割点(cut-vertex)。 图 G 有生成树的充分必要条件是图 G 是连通的。 任何连通图 G 至少存在一棵生成树. 设 n 阶无向连通图 G 有 m 条边,则 m ? n ? 1 。 设 n 阶无向连通图 G 有 m 条边, T 是 G 的生成树, T ' 是 T 的余树,则 T ' 中有 m ? n ? 1 条边. (1) 、利用“破圈法”求出图的一个生成树。 (2) 、利用“避圈法”求出图的一个生成树。 解: 、所谓“破圈法”,就是先在图中找 (1) 出一个圈,然后再去掉圈中的一条边,使其破开, 如右图所示,先在图中找一个圈

?v1 , v2 , v3 , v1 ? ,

然后又将其中的 e3 去掉,在余下的图中,再取一 个新圈 ?v1 , v2 , v4 , v3 , v1 ? ,然后又将 e4 去掉,在余下的圈中,取新圈 ?v1 , v2 , v5 , v4 , v3 , v1 ? , 然后再在余下的圈 ?v3 , v4 , v5 , v3 ? 中去掉 e6 ,最后再将余下圈中的 e8 也去掉,此时剩余的图 中不含圈,那么这个生成树就生成出来了。 (2) 、所谓“避圈法”,就是避免在生成树的过程中产生圈,因此,我们以 v1 为起始 点开始找出与 v1 不构成圈的边,因此,接着取 e1 、 e2 、 e4 、 e7 ,这样再也找不出不能产生 圈的生成树了,因此,最终结果就是 e1 、 e2 、 e4 、 e7 。

第七章

欧拉图和哈密顿图

例 1: (环路) 环路(cir)是圈与圈的边不重并。圈是环路,圈是连通的,环路不一定连通。 闭链是环路。环路中每个顶点的度均为偶数。图 G 是连通环路当且仅当存在一条包含 G 的所有边的闭链。每个顶点的度为偶数的图 G 是环路。 环合: 例 2: (欧拉图) 顶点的度均为偶数的图称为欧拉图(Euler graph)。 (图中存在经过所有顶点、所有边的 闭路径,此图称为连通欧拉图。 ) 结论:1) 、闭链是欧拉图; 2) 、环路是欧拉图; 3) 、图 G 是连通欧拉图当且仅当存在一条包含 G 的所有边的闭链; 4) 、两个欧拉图的环和仍是欧拉图。 无向图 G 为欧拉图当且仅当 G 连通,并且所有顶点的度都是偶数。
图论与组合数学复习笔记 第 18 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

无向图 G 为欧拉路径(非欧拉图),当且仅当 G 连通,并且恰有两个顶点的度是奇数。 例 3: (哈密顿图) 图 G 称为哈密顿图(Hamilton graph) ,如果 G 上有一条经过所有顶点的回路(也称这 一回路为哈密顿回路或者哈密顿圈) 。 称无向图有哈密顿通路(非哈密顿图),如果 G 上有一条经过所有顶点的通路(非回路)。 设 G 是 n?? 3? 阶简单图, w 是有最小度的顶点,如果 deg?w? ? n 2 ,则 G 是哈密顿图。 设 u, v 是 n 阶图 G 中两个不邻接的顶点,如果 deg(u) ? deg(v) ? n ,则 G 是哈密顿图 的充要条件是 G ? uv 为哈密顿图。 设 G 为 一 n 阶 图 , 若 任 意 一 对 顶 点 u, v 满 足 : d e gu) ? d e gv() ? n , 而 且 边 (

(u, v) ? E ?G ? ,则将 (u, v) 加于图 G 上,得到 G ? ?u, v ? ,如此反复加边直到无边可加为止,

? 这样得到的图叫做图 G 的闭包,记作 G 。如下图所示

G

? G

图 G 称为可 2-着色(2-chromatic) ,如果可用两种颜色给 G 的所有顶点着色,使每个 顶点着一种颜色,而同一边的两个不同端点必须着不同颜色。设图 G 是可 2-着色的。如果 G 是哈密顿图,那么着两种颜色的顶点数目相等;如果 G 有哈密顿通路,那么着两种颜色的顶 点数目之差至多为一。

第八章 割集
例 1: (割集与断集) 我们定义连通图 G 的顶点数减 1 为图 G 的秩, 记作 R?G ? , R?G ? ? p ? 1 , 即 如果 G 有

k 个连通分支,则 R?G ? ? p ? k 。
设 S ? E (G) ,如果 ?

? R?G ? S ? ? p ? 2 ,则称边集 S 为图 G 的一个割集。 ?对?S ' ? S , R?G ? s '? ? p ? 1

割集是指一个边集 S,在 G 中去掉 S 的所有边后 G 变为具有两个分支的分离图,但是去 掉 S 中的部分边时图仍然是连通的,割集就是“割”掉的部分的边的集合。 图 G 中端点分别属于 V1 和 V1 的所有边的集合称为 G 的断集(broken set)。 E (V1 ?V2 ) 表示一个端点在 V1 中,另一个端点在 V2 中的所有边的集合。 设 T 是连通图 G 的一棵生成树,并且 e 是任一树枝,则:①、连枝集中不包含 G 的割
图论与组合数学复习笔记 第 19 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

集。②、 T ? e 包含 G 的一个唯一的割集。连通图 G 的一个割集至少包含生成的一个树枝。 例 2: (关联集) 设 v 是图 G 的一个顶点,与 v 关联的所有边的集合,称为顶点 v 的关联集,记作 S ?v ? 。 设 V1 ,V2 ,V3 ,V4 是图 G 的顶点集合的非空子集,其中任何两个的交均为空集,则:

E ?V1 ? V2 ?V3 ? V4 ? ? E ?V1 ?V3 ? ? E ?V1 ?V4 ? ? ?V2 ?V3 ? ? ?V2 ?V4 ?


V1



V2





G

顶 点





的 非 空





, 则

:

E V1 ? V1 ? E V2 ? V2 = E ?V11 ? V22 ? V12 ? V21 ? ? E V3 ? V3 。 其 中 , V11 ? V1 ? V2 ,

?

?

?

?

?

?

V12 ? V1 ? V2 , V21 ? V2 ? V1 , V22 ? V2 ? V1 , V3 ? V11 ? V22 。
图 G 的任一断集均可表示成若干个关联集的环和。 图 G 中任一顶点的关联集等于其余顶点关联集的环和。 例 3: (割集空间) 设 S 是图 G 的一个割集, 是一棵生成树, 如果 S 中恰好含有 T 的一树枝, 则称 S 为 G T 的关于生成树 T 的基本割集。 P ? 1 个基本割集称为图 G 的基本割集组。 每个基本割集只含有一个树枝, P ? 1 个基本割集称为图 G 关于生成树 T 的基本割集 这 组,记作 S f 。 图 G 的任一断集均可表示成若干基本割集的环和。 图 G 的所有断集和空图的集合 ? 作成向量空间 ?(G ) 的一个子空间,称为 G 的割集空 间。 结论:1) p 阶连通图 G 关于生成树 T 的基本割集组是 G 的割集空间的一组基底,割 、 集空间维数为 P ? 1 。 2) 、图 G 的全部断集的个数为 2
p?1

?1 ,空集不是断集。

p 阶连通图恰有 P ? 1 个线性无关的关联集。然后求出它们所有可能的环合,即可求出
G 的全部断集。

第九章
例 1: (最短道路)

最短道路与最小树

所谓最短道路问题就是在 (vi , v j ) 道路集合 Pij 中,寻求长为最小的道路,这样的道路 称为从 v i 到 v j 的最短道路(shortest path)。 (1) 、利用 Dijnstra 算法计算下图中从 v1 到 v 6 的最短路径。

? ?

图论与组合数学复习笔记 第 20 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

(2) 、利用 Floyd 算法计算下图中任意两点之间的距离。

解: 、步骤如下: (1) ①、首先,我们给起始点标上 P 标号 d ?v1 ? ? 0 ,给其他各点标上 T 标号。其中:

d ?v j ? ? l1 j ( j ? 2,3,?,6) 。
②、再在所有 T 标号中找最小者 d ?v2 ? ? l12 ? 1 ,则把 v 2 的 T 标号改为 P 标号。 ③、从 v 2 开始,重新计算具有 T 标号的其他各点的 T 标号。并比较 d v j 与 d ?v2 ? ? l 2 j 的大小,由于此时只有 v 3 与 v 4 和 v 2 相邻,因此, d ?v3 ? ? min{d ?v3 ?, d ?v2 ? ? l23} ? 4 ,同理 可得, d ?v4 ? ? min{d ?v4 ?, d (v2 ) ? l24 } ? 2 。 ④、重复以上步骤直到 v6 ? P ,而此时 d ?v6 ? 就是 v1 到 v 6 的最短路径。 详细过程如下:

? ?

P 集合

d ?v1 ? ? 0 d ?v2 ? ? 1 d ?v4 ? ? 2

d ?v2 ? ? 1
d ?v3 ? ? 4

d ?v4 ? ? 2
d ?v3 ? ? 3 d ?v5 ? ? 5 d ?v6 ? ? ?

d ?v3 ? ? 3 d ?v5 ? ? 5 d ?v6 ? ? 5

d ?v5 ? ? 5 d ?v6 ? ? 5

d ?v6 ? ? 5

d ?v4 ? ? 2
d ?v5 ? ? ? d ?v6 ? ? ?

T 集合

d ?v3 ? ? ? d ?v5 ? ? ? d ?v6 ? ? ?

图论与组合数学复习笔记 第 21 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

则 v1 到 v 6 的最短路径为 d ?v6 ? ? 5 。 (2) 、步骤如下: ①、首先将图转化为矩阵 D?0 ? ,如下所示:

D ?0 ?

? 0 1 ? 2 ? ?? ? 1 0 3 4 ? ?? ? ? ?? 3 0 1 2 2 ? ? ?lij ? ? ? ? ? 2 4 1 0 3 ?? ?? ? 2 3 0 2 ? ? ? ?? ? 2 ? 2 0 ? ? ?
?k ? ? k ?1? ? , d i?k ?1? ? d kjk ?1?} ,即 D?1?

由 Floyd 算法可以得出下一次变换中元素为 d ij ? min{ d ij

的第一行和第一列是上一个矩阵的第一行第一列, 其余元素则是将此元素所在位置上第一行 以及第一列元素加和后与原矩阵在此位置上的值相比较后的较小值。

? 0 1 ? 2 ? ?? ?0 ? 1 0 3 3 ? ?? ?1 ? ? ? ?? 3 0 1 2 2 ? ? 2 ? ? 4 D ?1? ? ? ? D ?? 2 3 1 0 3 ?? ? ?2 ?? ? 2 3 0 2 ? ?? ? ? ? ?? ? 2 ? 2 0 ? ?? ? ? ? ?0 1 4 2 6 6 ? ?1 0 3 3 5 5 ? ? ? ? 4 3 0 1 2 2? ?4 ? ?5 ? D ?3 ? ? ? ? D ?D ? 2 4 1 0 3 3? ?6 5 2 3 0 2? ? ? ?6 5 2 3 2 0 ? ? ?
那么,我们从 D
?6 ?

1 0 3 3

4 3 0 1

? 2 ? 2

? ?? 3 ? ?? ? 1 2 2? ? 0 3 ?? 3 0 2? ? ? 2 0? ? 2 1 3 2 5 5? 0 3 4 5 5? ? 3 0 1 2 2? ? 4 1 0 3 3? 5 2 3 0 2? ? 5 2 3 2 0? ?

? D ?6 ?

?0 ?1 ? ?3 ?? ?2 ?5 ? ?5 ?

就可以看出每两点之间的距离。

例 2: (最小生成树算法) (1) 、利用 kruskal 算法(避圈 法)求图中的最小生成树。 (2) 、利用断集与连通图的原理 (算法二)求最小生成树。 (3) 、利用破圈法求图中的最小 生成树。 解: 、首先,我们将图中各个 (1) 路径的权值按照从小到大的顺序排 列,然后按照从小到大的顺序将各个边重新添加到原图上(假设原图的边都被去掉了) ,如 果后面加上去的边使得图中生成了圈,那么就把这条边丢弃,直到遍历完最后一条边,具体 步骤如下所示:
图论与组合数学复习笔记 第 22 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

①、将边按权值从小到大排列:

l (e1 ) ? l (e5 ) ? l (e2 ) ? l (e8 ) ? l (e7 ) ? l (e9 ) ? l (e4 ) ? l (e6 ) ? l (e3 )
②、依次画出其最小生成树如下:

(2) 先选取一个点, 、 在找出此点的断集 E (V1 ? V1 ) , 将断集中的最小权值那条边保留, 然后去掉其余边,然后有取与原点相连的点,找出此子图的断集 E (V2 ? V2 ) ,也是取权值最 小的边并保留,重复以上步骤,直到取完所有的点,此时就会得到一个最小生成树。 (3) 、破圈法:找到图中任意一个圈,然后去掉权值最大的那条边,直到图中没有圈为 止。

第十章 有向图
例 1: (有向图) 有向图 D 中,以顶点 v 为起点的弧的数目,叫做 v 的出度(Outdegree),记作 deg ?v ? ;
?

以顶点 v 为终点的弧的数目,叫做 v 的入度(Indegree),记作 deg ?v ? 。
?

有向图 D 满足下列条件的有向图称为有向树(Directed Tree) : (1) D 有且仅有一个顶点的入度为 0(即树根); (2) D 除树根外的顶点入度为 1; (3) D 从树根到任何顶点均有一条有向通路。 例 2: (有向道路和有向圈) 如果在有向图 D 中,有一条 ? u, v ? 有向道路,则 v 称为是从 u 可达的,或者说,从 u 可达 v . ( 1 ) 如 果 有 向 图 D 的 任 何 两 顶 点 都 互 相 可 达 , 则 称 D 是 强 连 通 的 (strongly connected)。 (2) 如果有向图 D 的任何两顶点至少有一个顶点由另一个顶点可达, 则称 D 是单向连 通的(unilateral connected)。 (3)如果有向图 D 的任何两顶点由一条半道路联接,则称 D 是弱连通的(weakly
图论与组合数学复习笔记 第 23 页 共 24 页

哈尔滨医科大学生物信息科学与技术学院

connected)。 有向图 D 是强连通的,当且仅当 D 的每一条弧都在某一有向圈中。 设 P 是有向图 D 的一个子图,如果: (1) deg ?u ? ? 1 , deg ?u ? ? 0 , deg ?v ? ? 1 , deg ?v ? ? 0 u, v ?V ?P ? ;
? ? ? ?

(2) 、对任意的 w?V ?P ? ,有 deg

?

?w? ? deg ? ?w? ? 1 ,那么 P 是一条 ?u, v ? 有向道路。
?

设 C 是有向图 D 的一个子图,如果: (1)对任意的 v ?V ?C ? ,有 deg ?v ? ? deg ?v ? ;
?

(2)对任意的 v ?V ?C ? , deg?v ? ? 2 ,那么 C 是一条有向圈。 有向图 D 有有向圈的充要条件是存在一个所有顶点均满足 deg ?v ? ? 0 和 deg ?v ? ? 0
? ?

的子图。 有向图 D 没有有向圈的充要条件是能通过 w 过程去掉 D 的所有的弧。 v 是有向图 D 设 的一个顶点,如果 deg ?v ? ? 0 或 deg ?v ? ? 0 ,则去掉顶点 v 和 v 关联的的弧,我们称这一
? ?

过程为去掉 v 的 w 过程。

图论与组合数学复习笔记 第 24 页 共 24 页


相关文章:
组合数学及其图论试题库
组合数学及其图论试题库_理学_高等教育_教育专区。组合数学及其图论 1 、一个图...答案第 8 页共 16 页 51、证明任意六个人中三个人互相认识,或三个人互...
组合数学题库-最新-答案版
关键词:组合数学图论排列组合数学信息与通信工程 同系列文档 中国名人老照片 图说...组合数学题库-最新-答案些简单题目只有过程,结果可以自己算。有些简单题目...
组合数学与图论试卷A
组合数学与图论试卷A_理学_高等教育_教育专区。中南...的恰有两个黄球相邻的全排列的个数. (本题 10 ...2008组合数学期末考试试... 2页 1下载券 大学数学...
离散数学图论部分经典试题及答案
离散数学图论部分经典试题及答案_理学_高等教育_教育专区。离散数学图论部分综合练习 离散数学图论部分综合练习 一、单项选择题 1.设图 G 的邻接矩阵为 ?0 1 ?1...
电大离散数学图论部分期末综合练习题
T 中 8 个结点,4 度,3 度,2 度的分支点各一个,T 1 离散数学 2012 春期末图论部分综合练习辅导 的树叶数为( A.8 握手定理 二、填空题 ). B.5 v...
图论复习要点
图论复习要点_理学_高等教育_教育专区。湘潭大学凸轮与组合数学图论复习要点,期末...两个法则的区别及应用 ? 求排列数、环排列数、组合数 ? 课堂练习题 ★ 第...
...数学课后习题答案---第二学期--图论与组合数学
课后习题答案---第二学期--图论与组合数学_理学_...14.按题 13 的 Prim 算法, 求出图 6. 9 的...因此必有 k(G) ≧p-2=δ (G),但 k(G) ≦...
图论与组合
学时数学分数考试 成绩 考查补考评定结果任课教师 现代数学概览 课程类别 (学...外有关图论的赛题,探究了 “图论与竞赛数学组合问题 ”的联 系,搭建起图论...
图论与组合数学 教学大纲 2016 修改版
利用欧拉公式求解具体问 题; 3. 掌握图的着色。 1. 了解向图与无向图在...趣味组合数学和图论4 7页 免费 图论与组合数学期末复习... 24页 1下载券 ...
张清华 图论课后题答案
张清华 图论课后题答案_理学_高等教育_教育专区。很...2.14 证明:用数学归纳法证明: (1)n=1 时,G ...因为此时总的 边数m ≥ 2 ?? ?? ? 1 ,则...
更多相关标签: