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

1、组合数学局部第1章排列与组合1、求小于10000的含1的正整数的个数；2、求小于10000的含0的正整数的个数；解：1、小于10000的不含1的正整数可看做 4位数,但0000除外.故有9X 9X 9X9 1 = 6560 个.含 1 的有：9999 6560=3439 个2、“含0和“含1不可直接套用.0019含1但不含0.在组合的习题中有许多类似的隐含的规定,要特别留神.不含 0的1位数有91个,2位数有92个,3位数有93个,4位一一 4 一 . -1-2. 3_4951一.数有9个不含0小于10000的正整数有9999 7380个含0小于10000 的正整数 9999-7380=261

2、9 个.例2:从1,300中取3个不同的数,使这 3个数的和能被3整除,有多少种方案解：将1,300分成3类：A=i|i三 1mod3=1,4,7,298,B=i|i三 2mod3=2,5,8,299,C=i|i三 0mod3=3,6,9,300.要满足条件,有四种解法：1、3个数同属于A;2、3个数同属于B;3、3个数同属于C;4、A,B,C 各取一数；故共有 3c100,3+100 3=485100+1000000=1485100.例3： Cayley定理：过n个有标志顶点的数的数目等于nn 2一1、写出右图所对应的序列；.,2、写出序列22314所对应的序列；解：1、根据叶子节点从小到大

3、的顺序依次去掉节点包含与此叶子节点相连接的线,而与这个去掉的叶子节点相邻的另外一个内点值那么记入序列.如上图所示,先去掉最小的叶子节点,与其相邻的内点为,然后去掉叶子节点,与其相邻的内点为,直到只剩下两个节点相邻为止,那么最终序列为51155.2、首先依据给定序列写出序列长度+2个递增序列,即1234567,再将给出序列按从小到大顺序依次排列并插入递增序列得到：112223344567.我们再将给出序列 22314写在第一行,插入后的递增序列写在第二行.如以下图第一行所示：2231423141122233445671122334467314 14 113447112334471447.我们每次

4、去掉第一行第一个数,并在第二行寻找第一个无重复的元素475并将它取出,将与连接起来,并在第二行去掉第一行的第一个元素,剩下的序列为1122334467,依次执行下去.最终剩下的两个元素47连在一起.那么形成了以下的树.磅©®©©例4 ：圆排列问题：从n个字符中取r个不同的字符构成圆排列的个数为P n,rrn.5对夫妇出席一宴会,围一圆桌坐下有多少种方案要求每对夫妇相邻而坐,方案有多少种?解：1、此问便是考查圆排列的公式定义,由P 10,1010!万式有Q 10,10 9!种.1010 5!2、同样,先将5个丈夫进行圆排列那么有 35_ P n,r _ .

5、Q n,r 0 r n可得,排列r24种,再将5个妻子插到丈夫的空隙之中,每个妻子只有两种选择,要么在丈夫的左边,要么在右边.因此由25种插入的方法,所以一共有4! 25种.有错误！例5:允许重复的排列重集S6a,5b,4c,3d ,做重集S的全排列,问有多少中排列方案解：设可重复Sn1 a1,n2 a2, ,nk a. 其中,21色, ©为S中k个不同元素,那么S的个数为n n1 n2nk , S的全排列为：n!n1!n2! nk!那么据题意可得：方案数为 一1806! 5! 4! 3!列6:允许重复的组合、上、一t4试问x y z 有多少项解：由于 x y zxyzxyzxyzx

6、yz,相当于从右边每个括号里取一个元素相乘,而元素可以对应相同如4个括号我都取x或者不同.这就相当于将4个无区别的球放进 3个有区别的盒子,由于在n个不同元素中取r个进行组合,允许重复,那么组合数为 C n r 1,r.或者说r个无区别的球放进n个有区别的盒子里,每个盒子球数不限,那么共有 C n r 1,r种.问题等价于从3个元素中取4个做允许重复的组合,4 3 16包30 15项.444!2!2例6:线性方程的整数解个数问题线性方程x1 x2xn b, n和b都是整数,n 1 ,求此方程非负整数解的个数解：方程的非负整数解1, 2, , n对应一个将b个无区别的球放进 n个有区别的盒子x1

7、,x2, ,xn的情况,允许一盒多球,故原式可以等价转化为将将1到n的正整数取b个作为允许重复的组合,其组合数为n b 1个.b例7:不相邻的组合从A 1,2,3,4,5,6,7中取三个元素做不相邻的组合,有多少种方式解：由于从A 1,2, ,n中,取r个作不相邻的组合,其组合数为c n r 1,r ,因7 3 155!120此在此题中n 7,r 3,组合数种类有2 10种.333!2!12例8:全排列的三种生成算法1、 m 4000, 6! 4000 7!,求m对应的序列.2、利用字典序法求求 839746521的下一个排列.解：1 、 由于 0到n! 1中的任何整数m都可以唯一表示为m a

8、n 1n 1! an 2 n 2 !a2 2! a1 1!其中 0 a, i , 1 i n 1 ,可以证实从 0 到n! 1的n!个整数与an 1,an 2, ,a2,a1 一一对应,我们要得到这些值就得每次除以与其相 对应的数值,就可以得到与 ai相对应的余数值n.由于6! 4000 7!,所以:n14000 a6 6! a§ 5! a44! a3 3! a2 2! an240006!5!2000a6a5一262524!a423!八a3 -a2,a10 r1,n6n7n2n3n4 5n5n6把n-120001T666166V33y666166336!a63!6!36 4!5!4!

9、a5 3!a4 3!5!3534,334!36 0 35,34 1 4, 5!5a6, a5 3 r0,a6 5 r6,所以:4000 533,32 2 26! 3 5! 14 2 3 2 2!.个元素的序列 3nl,an2,a2,a1和n个元素的排列建立一一对应关系,从而得到一种生成排列的算法一一序数法.将3n 1,3n 2,a2,a1与给出序列相对应,例如给数比他小,所以311.综上所述,对应序列为301 .3 ,同理,第二个大2这个数右边有一个出4213,那么对应 33,32,31 ,由大到小的计算当前数值位置右边比此位置数值大的数值的个数,例如最大的数为 4, 4这个数右边有3个数比它

10、小,所以a3 3的数为3,在3这个数右边有0个比它小的数,所以a2 0 ,同理对应同时,由301也可以推出最大数 4的右边有3个比它小的数,为:第二个大的数3右边比他小的数的个数为 0,因此,为: 第三个大的数2右边比他小的数有 1个,而1的位置也 可以确定了因此为一一一一2、字典序法首先从序列P1, P2,Pn后向前找出第一组 Pi 1Pi,记下此式Pi 1的值,然后有从后向前找第一个比Pi 1的值大的数Pk ,并将Pi 1和Pk调换位置,然后再将原来Pi 1 现在Pk位置以后的全部序列倒序即可以了.如题中所示的序列 839746521中,首先找出从右向左第一组Pi 1Pi的Pi 1,此处为

11、4,然后找到Pk为5,将它们两调换得到839756421,然后将5后面的数逆序得到 839751246.例9:格路模型一场电影的票价是 50元,排队买票的顾客中有 n位是才e有50元的钞票,m位是持有100元的钞票.售票处没有准备50元的零钱.试问有多少种排队的方法方法使得购票能顺利进行,不出现超不出零钱的状况.假设每位顾客只限买一张票,而且m.解：在格路模型中,从0,0 m,n的路径选择有 m n!m! n!c m n,m 种.由于这个问题可以看成是由 m个向右和n个向上组成,就是一个可重复的全排列问题.当然,将这一模型推广以后就可以应用于此题了,我们将问题简化就可以得到卖票者从没有钱到把所

12、有票都卖完,在这个期间他必须实现每次卖票成功即有足够的零钱找给顾客.在格路模型中,我们把 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点出发经过从0,1出发经过y=x的路径等于由必须经y=x1, my=xr /'y=x的路径,如右图所示,由对称性以及n m可以知道,1,0出发到达1,m 1m,n的路径,由于由1,0出发到达 m,n转

13、化为：路径数m n 1 !m! n 1 !1 !n!1 一 一.然而,n此处是可以接触y=x的,因此我们可以将纵坐标向下移动一个单位如右图所示:即可以接触y=x但是不可以穿过 y=x-1 .此时相当于从m,n点的路径,而这一路径与从1, 1=C m n, m C m n, m 1 = mx-y=l(UU1I0,0到m,n点减去从0,0经过y=x-1到到m, n的路径数相等,所以路径数n m 1om! m n !例10：假设干等式及其组合意义分别解释以下组式子的组合意义.1)、Cn,r C n,n r 即 n r2)、C n, r C(n 1,r) C(n n1, r 1)即 r3)、C(n r

14、 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 nr, l r), (l r)即l5)、C(m,0)C(m,1) C(m,2)C(m, m) 2m,m6)、C(n,0)C(n,1)C(n,2)C(n,n) 0；7)、解:1)、0;C n, rC n, n0,0到达r, n在n个格子上面先走个格子,再走r个格子是样的.2)、C n, r C(n 1,r)C(n义之一便是格路模型中的意义,从1,r的路径数可以被看成是r, n这个式子可以被看作是格路模型的应用,从r个格子,剩下再走n个格子,这个和先走n r

15、1, r1)即0,0到,这个式子组合意r,n r的路径数可以被看成是,从0,0到n r,r 1路径数可以被看成是.就是说我们从 0,0出发都是必须先经过 n r 1, r或n r,r 1再到达r的.还有一种模型便是从含有 a1的n个数中取出r个数有几种取法的问题,首先我们将取得的数分为两类：一类是取得的数中含有a1 ,一类是不含有C(n 1,r 1)种取法(先将 a1取出,再从剩余的 n1个数中取r1个).不含有C(n 1, r)种取法.因此C n,r C(n 1,r) C(n1,r 1).3)、C(n r 1,r)C(n r,r) C(n r 1, r1)C(n1,1) C(n,0),运用上

16、题中的模型即可.4)、 C(n,l)C(l,r)C(n, r)C(n r, l r), (l r)即 n于从n个小球中取出l个小球,再从l个小球中取出r个,右边相当于从n个小球中先取出r个小球,由于这里面有重复度为,它等于从剩下的r个小球中取出lr个小球,这样一组合就相等了5 )、C(m,0) C(m,1) C(m,2)C(m,m) 2m,m 0 ,二项式模型m.等式右边为将 m个无区别的球放入 2个有区别的盒子,左边表示其中一个盒子分别装有0个,1个,一,m个球的组合数纸盒.6)、C(n,0) C(n,1) C(n,2)C(n,n) 0;二项式定理,当y x时,等式左边相当于在有m个红球r个

17、球中有0个红球和r个蓝n n nnx y x 0nm n m n7)、 r 0 r和n个蓝球混合后从中取出球,一个红球和r 1个蓝球yn =0.m nm n1 r 1 r 0r个球,等式右边相当于在取得的 ,个红球和0个蓝球.递推关系与母函数例1:(母函数与递推关系)利用母函数法求解满足递推关系FnF0FnFiFn12 n 2 ,的Fibonacci序列的解.解：首先,我们根据题意设母函数为F0FiXF2x2,贝U：x2 x3 xF2FF.FiF2F3F0FiF2可得：G(x)令 G(x)A1 .51 x21 3x2因此,G(x) 21 1 '51 xG(x)ax2 2ax a x可得

18、,G(x)因此,递推关系式为Fn由于1, n所以,Fnn,52即1一也Fn1 21.618Fn1.618FnFnFm Fn 20.618Fn 1 o例 2： (Fibonacci序列的假设干不等式)(1)、证实:F1F2FnFn 21；(2)、证实:F1F31 F2n ；(3)、证实:_ 2_ 2F1F2Fn2Fn"证：(1)、由于序列为Fibonacci序列,所以有：FnFn 1Fn因此:F1F3F2,F4FnFn2Fn 1F1F2F3 F4 FnFn 2(2)、由于序列为Fibonacci序列,所以有:FnFn1Fn2因此:F1F2F4F2(3)、F2F2,F5 F6F3,F2n

19、1F2n 2 ,所以有F1F3F2n1F2n.由于序列为 Fibonacci 序列,所以有：FnFn 1Fn 2 ,因此：F2 F3F1 , F32FnFnFn FmFm2即F12F n Fn Fn 1 0例3:(线性常系数齐次递推关系)(1)、求解 Fibonacci 数列Fn Fn1 Fn2(n 2)3母的递推关系.F1 F21an an 1 3a n、求数列n n1 na0 1,a102 5a n3 2an 4 (n 4)3 n 4的递推关系.解：1、由原式可得特征方程为所以,由定理可F1C21 . 5101 0,特征根为xi,X2F2C2X4a0FnnnC1X1C2X2得. 又由F1F

20、2.5 2C2城5 带入上述式子可得:1、51.51 .52,52、有原式可得特征方程为 X43x2 5x 2 0,特征根为X12 nn由定 理可得 angc2nc3nx1,2,3C4x4X2X31 ,由初值条件0, a21,a32可以得至kC4C1 C2G 2c2C1 3c2c34c32c44c4C29c3 8c4C3C442522952 ,故递推关系式为:7521052an4252空 n 1n A 15252n W522no例4:线性常系数非齐次递推关系(1)、求 an an 1a.5, a16an 235*4n , 一的递推关系.解：1、由题意可得,此题为线性非齐次递推关系的求解,我们可

21、以将an表布为齐次局部的通解加上特解,即*ananan ,其中an为特解,an为通解.对于其次局部,其特征多项式为X2 x 6 0 ,解得特征解为X1X23*nn,我们仅anC1X1C2X2 ,所以2*nnanc1 3 c22 ,又由于 anban 1b2an 2bkan kf n , n k ,那么可以得5*4n,我们设 anAonk Ank 11m nAk 1nAk n,那么由题意可得anA.* 4n,将此式带入原式可得A.*4n A0* 4n 1 6*A0* 4n 2 5*4n,那么解此式可得A0403*由 ananan可得annnCi 3C22竺*4.3a.5, ai 3 可以得到Ci

22、c23cl2c2竺5340*,* 4解得3右an为anBanCiC2675 ,所以an7615b?an 2bk an kanban 1b2an 2bkan kf n的一个通解,那么的通解.有以下结论:、假设fn为n的k次多项式,那么 an A.、 Ank1待定系数；an (AdI、假设f67.n357615404 .3an*an*,an为an原非齐次递推关系人,其中A0,A, ,Ak为假设导出的常系数线性齐次递推关系特征根为1的m重根,那么Ank 1Ak)nmon为bn “的形式,假设 是导出的常系数线性齐次递推关系的m重特征根,b n为n的p次多项式,那么an Ad、 Am 1m nAk)n

23、.例5:指数型母函数问题对于序列a0,a1, a2,Ge xa1a22a33a.-xx-x1!2!3!为序列aj的指数定义型母函数.几个具有代表性的指数型母函数:(1)、序列1,1,1,的指数型母函数为:Ge x1 k -x2 -x31!2!3!xj(2)、序列0!,1!,2!,的指数型母函数为:(3)、序列Ge x 0!1!2! 2 3!3x x x1!2!3!1,k,k2,k3的指数型母函数为:j 0 j!Ge x1kxI 2 3k 2 k 3xx2!3!kx e(4)、序列 1,1 3,1 35,1 3 57,的指数型母函数为：31 2x 2假设有8个元素,其中设a1重复3次,a2重复2

24、次,a3重复3次.从中取r(r8个组合,其组合数为多少?解:设Cr的母函数为:Ge2x2!3x3!x1!2x2!2 x 2!3x3!=1 3x14 3x3d 3=1 x1!对应当r排列数为1 x2!2835 4 x121 3 x3!"x1270 1x44!35 x721708 7 x 721 5 x 5!1时,即从中取一个进行排列,70.排列数为3,x72350 1 x66当r 4时,17560 x77!560 - x8.8!即从中取4个进行排列,例6：整数的拆分问题假设有1克的祛码3枚,2克的4枚,4克的2枚,问能称出哪些重量各有几种方案?解：由题意可得,我们设 G x 123,2

25、468,4x x x 1 x x x x 1 x其中第一项表木1克祛码3个,第二项表木2克祛码2个,第二项表木4克祛码2个. 这个多项式可得：借出G x 3x151 x 2x32x162x173x418x5, 6, 7891011, 12, 133x 4x 4x 5x 5x 5x 5x 4x 4x19x3x14那么比方能称出11克的方法就有5种,由于5X11.例 7： (Stirling数问题n个有区别的球放到 m个无区别的盒子中,要求无一空盒,其不同的方案数用 S n,m表示,称为第二类Stirling 数.即S n, m是将n个数拆分成非空的m个局部的方案数.Stirling数具有以下几点

26、性质:1)、S n,0S Qn0,2)、S n,k0,假设n1 ； S n,k 0,假设k n 1 ；3)、S n,1S n,n1,n1;4)、S n,22n 1 15、S n,33n1 12n 16、n,nC n,27、n,n8、n,mmS1, m1,m1 ,n1, m 1 ；9、n,mm!2n1n 1m!k 0以上式子的证实都可以用Stirling数的定义来证实,详见教材P101P02 .编Rn个球m个盒子是否空盒方某个数后区别后区别后空盒n m后区别后区别无空盒m! S n, m后区别无区别后空盒S n,1S n,2S n, m , nmS n,1S n,2S n, n , nm后区别无

27、区别无空盒S n,m无区别后区别后空盒C n m 1,n无区别后区别无空盒C n 1,m 1无区别无区别后空盒一1一 nG X2m的Xn项系数1 X 1 X 1 Xn个球放到m个盒子里n m ,依球和盒子是否有区别是否允许空盒共有多少种状态其方案计数分别列于下表.无区别无区别无空盒mx- nG x 2寸的xn项系数1 x 1 x 1 x解释：、当我们认为盒子无区别的时候,由Stirling数的定义可得有 S n,m种组合.然后,将m个盒子进行全排列,共有 m!种全排列,因此全部的排列数为m!Sn,m .、对于无区别盒子有空盒情况的全排列,我们可以转化为无区别盒子无空盒的情况解决.即将非空盒数分

28、为 1个非空、2个非空、m个非空的各种情况的加和的情况.由于盒子无区别,所以不用考虑空盒子的情况.S n,1表示只有1个盒子非空,S n,2表示只有2个盒子非空,S n,m表示只有m个盒子非空,当然,这是球数n大于盒子数量 m的结果,当球数小于盒子数时,由性质2可以得到最大的情况就是 n个盒子不为空,为Sn,n,综上所述,方案数为S n,1S n,2S n,1S n,2S n,m ,n m种.S n,n ,n m、由Stirling 数的定义可得.、这个模型可以转化为从m个元素中取n个元素允许重复抽取做允许重复的组合,那么可以得出组合数为 C n m 1,m.、我们的目的就是要将 n个球放入m

29、个有区别的盒子.首先,我们将n个球排成一列,1之间共有n 1个空隙,然后我们用隔板法将这列小球分成m局部,而要将球分成 m部分,我们只需要 m 1块隔板就可以了,问题就转化为将m 1块隔板插入n 1个缝隙共有多少种插法,由分析可得有 C n 1,m 1种插法.、此模型可以转化为整数拆分模型,目的就是将n个无区别的球拆分成1,2,3, ,m等数的和的问题,所以母函数 G x 1 x x21 x2 x4转化后即得出G x11 x 1 x21 xm的xn项系数即为整数n的拆分.、此模型也可以转化为整数拆分模型,首先,我们从 n个球中选取 m个球放进盒子 里面,保证每个盒子里面有一个球,这只有一种方法

30、.然后将剩下的n m个无区别的球拆分成1,2,3, ,m等数的和的问题,但是此处是取其中xnm项的系数,所以母函数G x 1 x x21 x2 x41 xm x2m,当然,如果仍然想取xn项系m数,我们将上式转化后即得出G x x-的xn项系数即为整数 n m的1 x 1 x 1 x拆分,再乘以从n个球中选取m个球放进盒子里的方法数第三章容斥原理例1:(容斥原理的根本定义)(1)、一个学校只有三门课程： 数学、物理、化学.修这三门科的学生分别有 170、 130、120人；同时修数学物理两门课的学生有 45人；同时修数学、化学的 20人；同时修 物理、化学的22人；同时修三门科的学生 3人.问

31、这学校有多少学生(2)、把n本不同的书放入 m个有编号的箱子中去(n>n),使得没有一个箱子为空. 共有多少种方法解：(1)、设M为修数学这门学科的学生集合,F为修物理学科学生的集合,C为修化学这门学科的学生集合.那么根据题意可得,M 170, F 130, C 120,MF45,MC20,FC22,M F C 3.那么根据容斥原理的定义可得在校生人数为：M F C M FCMFMCCFMFC=170+130+120-45-20-22+3=336 .(2)、对应于n个小球放入 m个盒子模型中的第种.但是,此处我们用容斥原理来解决.首先,对应于原题条件,我们用表示盒子允许为空的放球放法数,

32、然后用Ai表示第i个盒子为空的情况,那么A1A2AiAi 1Am表示所有盒子都不为空的情况,由容斥原理可得:AA2AmAAj1ABCDCDEFABCDEFGHAB CDAB EFABGHAB EFCDGHEFCD根据格路模型可以知道,CDGHEF GH经过路径EFGHABCD EFAB CD GHAB CD EFGHAB可以被认为先从0,0到A 2,2的路径数再乘上从B3,2到10,5的路径数,那么,由此可得：S C 10 5,5 .AB:C 2 2,2 C 10 3 5 2,5 2 CD : C 4 2,2 C 10 5 5 2,5 2EF :C 6 2,2 C 10 6 5 3,5 3 G

33、H :C 7 2,2 C 10 7 5 3,5 3ABCD :C 4,2 1C 8,3ABEF :C 4,2 1C 6,2AB GH :C 4,21C 5,2CDEF :C 6,2 1C 6,2CDGH :C 6,2 1C 6,2EF GH : C8,20 C5,2ABCD EF :C4,2 11C 6,2AB CDGH :C4,2 1 1 C 5,2CDEF GH :C6,2 10C 5,2 AB CDEF GH : C 4,2 1 10 C5,2那么,AB CD CD EF =3003-720-840-420-360+336+90+60+900+150+0-80-60-0+0=2049,因

34、此,共有2049种路径(仅供参考)第四章鸽巢原理m 1 一一例1：(鸽巢原理的证实：m只鸽子,n个巢,那么至少有一个巢不少于m1只鸽子)n(1)、证实：假设把n 1个物体放到n(n 1)个盒子中去,那么至少有一个盒子放有至少2个物体.(2)、证实：假设在一个集合S中存在n2 1个不相同的元素,那么在S中至少可以找出一组由n 1个元素组成的或未单调递增或者单调递减的子序列.证实：(1)、用反证法证实.如果n个盒子中每个盒子至多放入一个物体,那么放入n个盒子中的物体总数至多为 n个.这与假设有 n+1个物体矛盾.从而定理得证.(2)、我们从集合S中选取一个元素ai,再向后找比ai大的元素,直到后面

35、再也没有比它前一个元素还大的元素为止,例如,有一个序列如下：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中每一个元素ai都有假设干个单调递增的子序列,但其中有一个最多的子序列,设这个子序列的元素个数为li,i 1,2, n2 1,于是得到序列1i,12,ln2 1,当序列某一个元素lk n 1 ,那么已经符合要求,否那么,设序列中不存在超过n个元素的单调递增子序列,即：0 li n,i 1,2,

36、,n2 1 ,这就相当于把n2 1个小球放到n个盒子中取,由于此处2 一 m 1,m n 1 ,那么共有 1nn2 1 11 n 1 种.例2： ( Ramsey二染色定理)设a、b为正整数,令R(a,b)是保证a个人彼此熟悉或b个人彼此不熟悉的所需最少人 数,那么称 R(a,b)为 Ramsey数.R(3,3)=6 ; R4,3)=9 ; R3,4)=9 ; R4,4)=18 .注：这些定理只给出了几个Ramsey数的上界,并不一定是最好的结果.证实：6个人中一定有3个人相互熟悉或相互不熟悉.证实：(1)、这类问题其实就是Ramsey二染色问题.如右图所示,在六个人中,对于某个人A,要么他与

37、别人相互熟悉、要么互不相识,所以存在 这两种情况.我们将另外的五个人分为Friend和Stranger两个集合,那么：Friend=其余5个人与A互相熟悉的集合；Stranger=其余5个人与A不互相熟悉的的人；依据鸽巢原理,在 Friend集合或者Stranger 集合里至少有3个人,假设是在 Friend集合里有3 个人分别是B、G D,那么依据鸽巢原理可得在这个Friend=5的集合中,至少有F"end11 3个人相互熟悉或者不熟悉,如果 3个人互2相不熟悉,那么满足题意“至少有 3个互不熟悉,否那么其中两个人 B、C相互熟悉,又由于 A与Friend集合里面的人互相熟悉,所以

38、至少有 A、B C相互熟悉.同理,对于 Stranger 集合也是一样的.图论局部第五章图的根本概念例1:(图的定义)一个图G定义为一个偶对 V,E ,记作G V,E ,其中：(1)、V是一个集合,其中的元素称为顶点；(2)、E是无序集V到V中一个子集合,气元素称为边,其中的元素可在E中出现不止一次.二部图(二分图)：设/口2是6的顶点子集 ,使 回Vi V2=V G , Vi V2,且G的每条边的一个端点在Vi中,另一个端点在 V中,那么称 G为二部图,记 G Vi,V2；E.完全二部图：如果Vi中的顶点和V2中的每一个顶点都邻接,那么称为完全二部图,记为Kn,m.补图：设G W,E为完全图

39、,G1 V,E1, G2 V, E2为简单图,其中EiE2,EiE2E ,那么称G3G2相对于G互为补图,记GiG2C2Gi.生成子图：设图G V,E, 一个满足1、V H V G ;2、E H EG；的真子图,叫做 G的生成子图spaning graph 条件：点同边少.途径点、边可相同闭链边小同回路闭链道路点小同圈对于途径0©1 1n ien n 其中i表示顶点,3表示两顶点之间相连的边,假设其中ee2en均不同,那么称为 链chian .所有顶点0 i0均不相同从而所有边都必然不相同的路径称为道路path.一条封闭的道路成为 圈cycle .设u,v是图G中的两个顶点,假设G中

40、存在一条 u,v道路,那么称顶点u和v是连通的connected .如果图G中每一对不同的顶点 u,v间都有一条 u,v道路,那么称图G是连通的.假设以u v表示顶点u与v是连通的,那么这种顶点间的连通关系是一个等价的关系,即:I、u u 反身性；2、u v ,那么v u 对称性；3、u v,v w,那么 u w 传递性；每一个等价关系确定一个类,这些类称为G的连通分支或简称为分支 compouent,分支的个数记为k G .环和ring sum : G G2在G1和G2的并中去掉G1和G2的交所得到的图,即GiG2GiG2GiG2GiG2 G2Gi环合运算满足交换律和结合律.第六章树例1:破

41、圈法和避圈法给定图T,以下关于树的定义是等价的.1、无回路的连通图.2、无回路且e v 1其中e是边数,e是结点数.3、连通且e v 1.4、无回路,但增加一条新边,得到一个且仅有一个回路.5、连通,但删去任一边后便不连通.6、每一对结点之间有一条且仅有一条路.如果图G中删去一条边后,图 G的分支数增加,那么称此边位 G的割边cut-edge.如 果图中去掉一个顶点同时去掉与该点关联的所有边后图的分支数增加,那么称该点为G的割点cut-vertex .图G有生成树的充分必要条件是图G是连通的.任何连通图G至少存在一棵生成树.设n阶无向连通图G有m条边,那么m n 1.设n阶无向连通图G有m条边

42、,T是G的生成树,T'是T的余树,那么T'中有m n 1 条边.1、利用“破圈法求出图的一个生成树.2、利用“避圈法求出图的一个生成树.解：1、所谓“破圈法,就是先在图中找 出一个圈,然后再去掉圈中的一条边,使其破开,如右图所示,先在图中找一个圈v1,v2,v3,v然后又将其中的e3去掉,在余下的图中,再取一个新圈 “,v2,v4,v3, v1,然后又将e4去掉,在余下的圈中,取新圈»2,丫5,丫4»3,5,然后再在余下的圈 v3,V4,V5,V3中去掉e6,最后再将余下圈中的 e8也去掉,此时剩余的图 中不含圈,那么这个生成树就生成出来了.2、所谓“避圈法

43、,就是防止在生成树的过程中产生圈,因此,我们以V1为起始点开始找出与Vi不构成圈的边,因此,接着取 e1、a、e4、e7,这样再也找不出不能产生圈的生成树了,因此,最终结果就是0、e2、e4、e7.第七章 欧拉图和哈密顿图例1:环路环路cir 是圈与圈的边不重并.圈是环路,圈是连通的,环路不一定连通.闭链是环路.环路中每个顶点的度均为偶数.图G是连通环路当且仅当存在一条包含G的所有边的闭链.每个顶点的度为偶数的图G是环路.环合：例2：欧拉图顶点的度均为偶数的图称为欧拉图Euler graph.图中存在经过所有顶点、所有边的闭路径,此图称为连通欧拉图.结论：1、闭链是欧拉图；2、环路是欧拉图；3

44、、图G是连通欧拉图当且仅当存在一条包含G的所有边的闭链；4、两个欧拉图的环和仍是欧拉图.无向图G为欧拉图当且仅当 G连通,并且所有顶点的度都是偶数.无向图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

45、) n ,那么G是哈密顿图 的充要条件是 G uv为哈密顿图.设G为一 n阶图,假设任意一对顶点u,v满足：deg(u) deg(v) n ,而且边(u,v) E G ,那么将(u,v)加于图G上,彳#到G u,v ,如此反复加边直到无边可加为止,这样得到的图叫做图 G的闭包,记作 6.如以下图所示GG?图G称为可2-着色(2-chromatic ),如果可用两种颜色给 G的所有顶点着色,使每个 顶点着一种颜色,而同一边的两个不同端点必须着不同颜色.设图G是可2-着色的.如果G是哈密顿图,那么着两种颜色的顶点数目相等；如果G有哈密顿通路,那么着两种颜色的顶点数目之差至多为一.第八章割集例1：(

46、割集与断集)我们定义连通图 G的顶点数减1为图G的秩,记作R G ,即R G p 1 ,如果G有k个连通分支,那么RG p ko,eRGSp2设S E(G),如果p,那么称边集S为图G的一个割集.对 S' S,RG s' p 1割集是指一个边集 S,在G中去掉S的所有边后G变为具有两个分支的别离图,但是去 掉S中的局部边时图仍然是连通的,割集就是“害掉的局部的边的集合.图G中端点分别属于Vi和V1的所有边的集合称为 G的断集(broken set).E(Vi V)表示一个端点在 Vi中,另一个端点在 V2中的所有边的集合.设T是连通图G的一棵生成树,并且 e是任一树枝,那么：、

47、连枝集中不包含G的割集.、T e包含G的一个唯一的割集.连通图G的一个割集至少包含生成的一个树枝.例2:关联集v的关联集,记作S v.设v是图G的一个顶点,与v关联的所有边的集合,称为顶点设Vi,V2,V3,V4是图G的顶点集合的非空子集,其中任何两个的交均为空集,那么：EV1V2V3V4EV1V3EV1V4V2V3V2V4设 Vi和 V2 是图 G 顶点集合的非空子集,那么：EV1V1EV2V2= EV11V22V12V21EV3V3.其中,ViiViV2 ,图G的任一断集均可表示成假设干个关联集的环和.图G中任一顶点的关联集等于其余顶点关联集的环和.例3：割集空间设S是图G的一个割集,T是

48、一棵生成树,如果S中恰好含有T的一树枝,那么称S为G 的关于生成树T的根本割集.P 1个根本割集称为图 G的根本割集组.每个根本割集只含有一个树枝,这P 1个根本割集称为图 G关于生成树T的根本割集组,记作Sf.图G的任一断集均可表示成假设干根本割集的环和.图G的所有断集和空图的集合作成向量空间 G的一个子空间,称为 G的割集空间.结论：1、p阶连通图G关于生成树T的根本割集组是 G的割集空间的一组基底,割集空间维数为P 1.2、图G的全部断集的个数为 2p 1 1,空集不是断集.p阶连通图恰有P 1个线性无关的关联集.然后求出它们所有可能的环合,即可求出G的全部断集.第九章最短道路与最小树例1:最短道路所谓最短道路问题就是在vi,vj道路集合Pj中,寻求长为最小的道路,这样的道路称为从vi到vj的最短道路shortest path .1、利用Dijnstra算法计算以下图中从 v1到v6的最短路径.2、利用Floyd算法计算以下图中任意两点之间的距离.解：(1)、步骤如下：、首先,我们给