离散数学 (第七版) 课件 耿素云 第6-10章 特殊的图-形式语言和自动机初步

1第6章特殊的图6.1二部图6.2欧拉图6.3哈密顿图6.4平面图26.1二部图

二部图完全二部图匹配极大匹配,最大匹配,完美匹配,完备匹配Hall定理

3二部图

定义设无向图G=<V,E>,若能将V划分成V1和V2(V1

V2=V,V1

V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为<V1,V2,E>,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.

注意:n阶零图为二部图.4二部图(续)

例下述各图是否是二部图?

定理无向图G=<V,E>是二部图当且仅当G中无奇圈

不是5匹配

设G=<V,E>,匹配(边独立集):任2条边均不相邻的边子集极大匹配:添加任一条边后都不再是匹配的匹配最大匹配:边数最多的匹配匹配数:最大匹配中的边数,记为

1

例极大匹配最大匹配

1=36匹配(续)设M为G中一个匹配vi与vj被M匹配:(vi,vj)

Mv为M饱和点:M中有边与v关联v为M非饱和点:M中没有边与v关联M为完美匹配:G的每个顶点都是M饱和点例关于M1,a,b,e,d是饱和点

f,c是非饱和点

M1不是完美匹配

M2是完美匹配M1M27二部图中的匹配

定义设G=<V1,V2,E>为二部图,|V1|

|V2|,M是G中最大匹配,若V1中顶点全是M饱和点,则称M为G中V1到V2的完备匹配.当|V1|=|V2|时,完备匹配变成完美匹配.例完备,不完美不完备完美8Hall定理

定理(Hall定理)设二部图G=<V1,V2,E>中，|V1|

|V2|.G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点至少与V2中的k个顶点相邻(k=1,2,…,|V1|).

相异性条件由Hall定理,上一页第2个图没有完备匹配.定理

设二部图G=<V1,V2,E>中,如果存在t

1,使得V1中每个顶点至少关联t条边,而V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配.

t条件证

V1中任意k个顶点至少关联kt条边,这kt条边至少关联V2中的k个顶点,即V1中任意k个顶点至少邻接V2中的k个顶点.由Hall定理,G中存在V1到V2的完备匹配.9一个应用实例例某课题组要从a,b,c,d,e5人中派3人分别到上海、广州、香港去开会.已知a只想去上海，b只想去广州，c,d,e都表示想去广州或香港.问该课题组在满足个人要求的条件下，共有几种派遣方案？解令G=<V1,V2,E>,其中V1={s,g,x},V2={a,b,c,d,e},

E={(u,v)|u

V1,v

V2,v想去u},其中s,g,x分别表示上海、广州和香港.G满足相异性条件，红边是一个完备匹配,对应的派遣方案:a

上海,b

广州,d

香港106.2欧拉图欧拉通路与欧拉回路存在欧拉通路和欧拉回路的充分必要条件11哥尼斯堡七桥问题

要求边不重复地一笔画出整个图12欧拉图

欧拉通路:图中行遍所有顶点且恰好经过每条边一次的通路.欧拉回路:图中行遍所有顶点且恰好经过每条边一次的回路.欧拉图:有欧拉回路的图.半欧拉图:有欧拉通路回路,但无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.13欧拉图实例例是否是欧拉图或半欧拉图?欧拉图欧拉图半欧拉图半欧拉图不是不是14欧拉图的判别法

定理无向图G为欧拉图当且仅当G连通且无奇度顶点.G是半欧拉图当且仅当G连通且恰有两个奇度顶点.定理有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.D是半欧拉图当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.15实例例1哥尼斯堡七桥问题4个奇度顶点,不存在

欧拉通路,更不存在欧拉回路,例2下面两个图都是欧拉图.从A点出发,如何一次成功地走出一条欧拉回路来？应用实例例

设旋转磁鼓分成8个扇区,每个扇区标记一个0或1,有3个探测器能够读出连续的3个扇区的标记.如何赋给扇区标记,使得能够根据探测器的读数确定磁鼓的位置.为了能够根据读数确定磁鼓的位置,必须构造一个由8个0和1组成的圆环,使得圆环上连续3个数字的序列都不相同.16应用实例(续)构造一个4阶有向图,8条边的标记是不同的,图中存在一条欧拉回路:000,001,011,111,110,101,010,100.在这条回路上连续3条边的标记的第一位恰好与第一条边的标记相同.顺着这条回路取每一条边标记的第一位得到00011101,按照这个顺序标记磁鼓的扇区.1700011011000001011010100101110111186.3哈密顿图哈密顿通路和哈密顿回路存在哈密顿通路和哈密顿回路的充分条件与必要条件格雷码19哈密顿周游世界问题每个顶点是一个城市,有20个城市,要求从一个城市出发,恰好经过每一个城市一次,回到出发点.20哈密顿图的定义哈密顿通路:经过图中所有顶点一次且仅一次的通路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.半哈密顿图:具有哈密顿通路而无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响图的哈密顿性.21实例例是否是哈密顿图,半哈密顿图?哈密顿图哈密顿图半哈密顿图不是22无向哈密顿图的一个必要条件

定理

设无向图G=<V,E>是哈密顿图,则对于任意V1

V且V1,均有p(G

V1)

|V1|.证设C为G中一条哈密顿回路,有p(C

V1)

|V1|.又因为C

G,故p(G

V1)

p(C

V1)

|V1|.几点说明定理中的条件是哈密顿图的必要条件,但不是充分条件.可利用该定理判断某些图不是哈密顿图.由定理可知,Kr,s当s

r+1时不是哈密顿图.当r

2时,Kr,r是哈密顿图,而Kr,r+1是半哈密顿图.23实例例设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证(1)设v为割点,则p(G

v)

2>|{v}|=1.根据定理,G不是哈密顿图.(2)若G是K2(K2有桥),它显然不是哈密顿图.除K2外,其他的有桥连通图均有割点.由(1),得证G不是哈密顿图.24无向哈密顿图的一个充分条件

定理设G是n阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n

1,则G中存在哈密顿通路.当n

3时,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路.由定理,当n

3时,Kn均为哈密顿图.定理中的条件是充分条件,但不是必要条件.例如,

n(6)个顶点的路径存在哈密顿通路,但不满足条件.n(5)个顶点的圈是哈密顿图,不满足条件.25判断是否是哈密顿图的可行方法观察出一条哈密顿回路例如右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图.满足充分条件例如当n

3时,Kn中任何两个不同的顶点u,v,均有d(u)+d(v)=2(n

1)

n,所以Kn为哈密顿图.26判断是否是哈密顿图的可行方法(续)例4

4国际象棋盘上的跳马问题:马是否能恰好经过每一个方格一次后回到原处?解每个方格看作一个顶点,2个顶点之间有边当且仅当马可以从一个方格跳到另一个方格,得到16阶图G,如左图红边所示.取V1={a,b,c,d},则p(G

V1)=6>|V1|,见右图.由定理,图中无哈密顿回路,故问题无解.在8

8国际象棋盘上,跳马问题是否有解?不满足必要条件判断是否为哈密顿图是NP完全的27应用实例例某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？解作无向图G=<V,E>,其中V={v|v为与会者}，E={(u,v)|u,v

V,u与v有共同语言,且u

v}.G为简单图.根据条件,

v

V,d(v)

4.于是，

u,v

V,有d(u)+d(v)

8.由定理可知G为哈密顿图.服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.竞赛图竞赛图:任意两个顶点之间恰好有一条有向边.在循环赛中,n个参赛队中的任意两个队比赛一次,假设没有平局,用有向图描述比赛结果:顶点表示参赛队,A到B有一条边当且仅当A队胜B队.28ABCD竞赛图(续)定理

在n(n≥2)阶有向图D中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图D中存在哈密顿通路.根据定理,竞赛图中一定有哈密顿通路,当然也可能有哈密顿回路.当没有哈密顿回路时,通常只有一条哈密顿通路,这条通路给出参赛队的惟一名次.例如,CABD是一条哈密顿通路,它没有哈密顿回路,比赛结果是C第一,A第二B,C第三,D第四.29格雷码(graycode)为了确定圆盘停止旋转后的位置,把圆盘划分成2n个扇区,每个扇区分配一个n位0-1串.要用某种电子装置读取扇区的赋值.

当圆盘停止旋转后,如果电子装置处于一个扇区的内部,它将能够正确的读出这个扇区的赋值,如果电子装置恰好处于两个扇区的边界上,就可能出问题.如何赋值,才能将可能出现的误差减少到最小?30100011010111101000001110格雷码(续)格雷码:相邻的两个以及最后一个和第一个之间只有一位不同的把n位0-1串序列例如,000,001,011,010,110,111,101,100是一个格雷码

构造n维立方体图:2n个顶点,每个顶点表示一个n位串,两个顶点之间有一条边当且仅当它们的n位串仅相差一位.当n

2时,图中一定存在哈密顿回路.3100110111101100010001011001001110326.4平面图平面图与平面嵌入平面图的面极大平面图与极小非平面图欧拉公式平面图的对偶图地图着色与四色定理33平面图和平面嵌入定义如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.

例如下图中(1)~(4)是平面图,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面图.34平面图和平面嵌入(续)今后称一个图是平面图,可以是指定义中的平面图,又可以是指平面嵌入,视当时的情况而定.当讨论的问题与图的画法有关时,是指平面嵌入.K5和K3,3是非平面图设G

G,若G为平面图,则G

也是平面图;若G

为非平面图,则G也是非平面图.Kn(n5),Kn,m(n,m3)都是非平面图.平行边与环不影响图的平面性.35平面图的面与次数设G是一个平面嵌入G的面:由G的边将平面划分成的每一个区域无限面(外部面):面积无限的面,用R0表示有限面(内部面):面积有限的面,用R1,R2,…,Rk表示面Ri的边界:包围Ri的所有边构成的回路组面Ri的次数:Ri边界的长度，用deg(Ri)表示定理

平面图各面的次数之和等于边数的2倍.证每条边可能在两个面的公共边界上，也可能只在一个面的边界上.前者,在每个面的边界上这条边只出现一次,计算两次.后者,它在这个面的边界上出现2次,也计算两次.36平面图的面与次数(续)例1右图有4个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.例2左边2个图是同一个平面图的平面嵌入.R1在(1)中是外部面,在(2)中是内部面;R2在(1)中是内部面,在(2)中是外部面.其实,在平面嵌入中可把任何面作为外部面.37极大平面图定义若G是简单平面图,并且在任意两个不相邻的顶点之间加一条新边所得图为非平面图,则称G为极大平面图.例如,K5,K3,3若删去一条边是极大平面图.K1,K2,K3,K4都是极大平面图(它们已无不相邻顶点).极大平面图必连通.阶数大于等于3的极大平面图中不可能有割点和桥.任何n(n

4)阶极大平面图G均有

(G)

3.定理

n(n3)阶简单平面图是极大平面图当且仅当它连通且每个面的次数都为3.

38实例例是否是极大平面图?不是不是是39极小非平面图

定义若G是非平面图,并且任意删除一条边所得图都是平面图,则称G为极小非平面图.极小非平面图必为简单图例如,K5,K3,3是极小非平面图40欧拉公式定理(欧拉公式)设G为n阶m条边r个面的连通平面图,则n

m+r=2.证对边数m做归纳证明.m=0,G为平凡图,结论为真.设m=k(k0)结论为真,m=k+1时分情况讨论如下:(1)若G中有一个1度顶点v,则G=G-v连通,有n-1个顶点,k条边和r个面.由归纳假设,(n-1)-k+r=2,即n-(k+1)+r=2,得证m=k+1时结论成立.(2)否则,G中必有圈.删除一个圈上的一条边,记作G.G

连通,有n个顶点,k条边和r-1个面.由归纳假设,n-k+(r-1)=2,即n-(k+1)+r=2,得证m=k+1时结论也成立.41欧拉公式(续)推论(欧拉公式的推广)设G是有p(p

2)个连通分支的平面图,则

n

m+r=p+1证设第i个连通分支有ni个顶点,mi条边和ri个面.对各连通分支用欧拉公式,

ni

mi+ri=2,i=1,2,…,p求和并注意r=r1+…+rp+p

1,即得

n

m+r=p+142平面图的性质定理设G为n阶m条边的连通平面图,每个面的次数不小于l(l

3),则

设G为有p(p

2)个连通分支的平面图,且每个面的次数不小于l(l

3),则证由各面次数之和等于边数的2倍及欧拉公式得

2m

lr=l(2+m-n)可解得所需结论.

对

p(p

2)个连通分支的情况类似可证.43平面图的性质(续)推论

K5和K3,3不是平面图.证用反证法,假设它们是平面图,则K5:n=5,m=10,l=3

矛盾.K3,3:n=6,m=9,l=4

矛盾.K5K3,344同胚与收缩

消去2度顶点v

如上图从(1)到(2)插入2度顶点v

如上图从(2)到(1)G1与G2同胚:G1与G2同构,或经过反复插入、或消去2度顶点后同构收缩边e

如下图从(1)到(2)45库拉图斯基定理定理

G是平面图

G中不含与K5同胚的子图,也不含与K3,3同胚的子图.定理

G是平面图

G中无可收缩为K5的子图,也无可收缩为K3,3的子图.46非平面图证明例证明下述2个图均为非平面图.收缩2条边

收缩2条边

K3,3

取子图K5

取子图47平面图的对偶图

定义设平面图G,有n个顶点,m条边和r个面,G的对偶图G*=<V*,E*>如下：在G的每一个面Ri中任取一个点vi*作为G*的顶点,V*={vi*|i=1,2,…,r}.对G每一条边ek,若ek在G的面Ri与Rj的公共边界上,则作边ek*=(vi*,vj*),且与ek相交;若ek为G中的桥且在面Ri的边界上,则作环ek*=(vi*,vi*).

E*={ek*|k=1,2,…,m}.48平面图的对偶图的实例例黑色实线为原平面图,红色虚线为其对偶图

49平面图的对偶图的性质性质：对偶图是平面图，而且是平面嵌入.对偶图是连通图若边e为G中的环，则G*与e对应的边e*为桥;若e为桥，则G*中与e对应的边e*为环.同构的平面图的对偶图不一定同构.

上页两个平面图同构,它们的对偶图不同构.50地图:连通无桥平面图的平面嵌入,每一个面是一个国家.若两个国家有公共边界,则称它们是相邻的.地图着色(面着色):对地图的每个国家涂一种颜色，使相邻的国家涂不同的颜色.地图着色问题:用尽可能少的颜色给地图着色.地图着色可以转化成平面图的点着色.当G中无桥时,G*中无环.G的面与G*的顶点对应,且G的两个面相邻当且仅当G*对应的两个顶点相邻,从而G的面着色等同于G*的点着色.地图着色地图着色与平面图的点着色51例红红兰兰绿绿绿绿绿绿黄黄黄黄黄黄四色定理四色猜想(100多年前):任何地图都可以用4种颜色着色,即任何平面图都是4-可着色的.1890年希伍德证明五色定理:任何平面图都是5-可着色的.1976年美国数学家阿佩尔和黑肯证明,如果四色猜想不成立,则存在一个反例,这个反例大约有2000种可能(后来有人简化到600多种),他们用计算机分析了所有这些可能,都没有导致反例.四色定理

任何平面图都是4-可着色的.5253第7章树7.1无向树及生成树7.2根树及其应用547.1无向树及生成树

无向树与森林生成树与余树用基本关联矩阵求所有不同生成树用拉普拉斯矩阵计算生成树个数最小生成树与避圈法55无向树无向树:无回路的连通无向图平凡树:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点:树中度数

2的顶点右图为一棵12阶树.注:本章中所讨论的回路均指简单回路或初级回路树的应用英国数学家凯莱(ArthurCayley)于19世纪中叶研究饱和碳氢化合物CnH2n+2的同分异构体时提出树的概念.当n=1,2,3时,都只有一棵非同构的树;当n=4时,有2棵不同构的树.56甲烷乙烷丙烷丁烷异丁烷57无向树的性质定理设G=<V,E>是n阶m条边的无向图,则下面各命题是等价的：(1)G是树(连通无回路);(2)G中任意两个顶点之间存在惟一的路径;(3)G中无回路且m=n

1;(4)G是连通的且m=n

1;(5)G是连通的且G中任何边均为桥;(6)G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.58无向树的性质(续)

定理

设T是n阶非平凡的无向树，则T中至少有两片树叶.证设T有x片树叶,由握手定理及前面的定理，

2(n-1)

x+2(n-x)

解得x

2.59例题例1已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.试求树叶数,并画出满足要求的非同构的无向树.解用树的性质m=n

1和握手定理.

设有x片树叶，于是n=1+2+x=3+x,2m=2

(2+x)=1

3+2

2+x解得x=3，故T有3片树叶.T的度数列为1,1,1,2,2,3有2棵非同构的无向树.60例题例2已知无向树T有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.求T的阶数n,并画出满足要求的所有非同构的无向树.解设T的阶数为n,则边数为n

1,4度顶点的个数为n

7.由握手定理得

2m=2(n

1)=5

1+2

1+3

1+4(n

7)解得n=8,4度顶点为1个.T的度数列为1,1,1,1,1,2,3,4有3棵非同构的无向树61生成树

设G为无向连通图G的生成树:G的生成子图并且是树生成树T的树枝:G在T中的边生成树T的弦:G不在T中的边生成树T的余树:所有弦的集合的导出子图注意：不一定连通,也不一定不含回路.黑边构成生成树红边构成余树62生成树的存在性

定理

任何无向连通图都有生成树.证用破圈法.若图中无圈,则图本身就是自己的生成树.

否则删去圈上的任一条边,这不破坏连通性,重复进行直到无圈为止,剩下的图是一棵生成树.推论

设n阶无向连通图有m条边,则m

n

1.基本关联矩阵设G为无环无向图G的基本关联矩阵:从G的关联矩阵M(G)删除任意一行得到的矩阵，记作Mf(G)63v1v2v4v3abcdfe基本关联矩阵的性质设G为n阶无环无向图，从G的基本关联矩阵Mf(G)任选n-1列计算行列式（用模2运算），该行列式不为0当且仅当对应的n-1边构成生成树64v1v2v4v3abcdfe例例7.1用基本关联矩阵求图G所有不同生成树65v1v2v4v3abcdfe例(续)关联矩阵为删除第4行，基本关联矩阵为(1)取1、2、3列（abc不构成生成树）66v1v2v4v3abcdfe例(续)(2)取1、2、4列（abd构成生成树）(3)取1、2、5列（abe构成生成树）(4)取1、2、6列（abf构成生成树）67v1v2v4v3abcdfe例(续)(5)取1、3、4列（acd构成生成树）(6)取1、3、5列（ace构成生成树）(7)取1、3、6列（acf构成生成树）68v1v2v4v3abcdfe例(续)(8)取1、4、5列（ade不构成生成树）(9)取1、4、6列（adf构成生成树）(10)取1、5、6列（aef构成生成树）69v1v2v4v3abcdfe例(续)(11)取2、3、4列（bcd构成生成树）(12)取2、3、5列（bce构成生成树）(13)取2、3、6列（bcf构成生成树）70v1v2v4v3abcdfe例(续)(14)取2、4、5列（bde构成生成树）(15)取2、4、6列（bdf不构成生成树）(16)取2、5、6列（bef构成生成树）71v1v2v4v3abcdfe例(续)(17)取3、4、5列（cde构成生成树）(18)取3、4、6列（cdf构成生成树）(19)取3、5、6列（cef不构成生成树）72v1v2v4v3abcdfe例(续)(20)取4、5、6列（def构成生成树）在(1)~(20)情形中，共有16种不同生成树；剩余4种不构成生成树的情形，恰好对应着4种长度为3的不同回路abc、ade、bdf、cef。73v1v2v4v3abcdfe拉普拉斯矩阵设n阶无环无向图G的顶点度分别为d1,d2,…,dn

G的拉普拉斯矩阵记作L(G)：

（A(G)是图G的邻接矩阵

）74拉普拉斯矩阵例子75v1v2v4v3abcdfev1v2v4v3拉普拉斯矩阵的性质n阶无环无向图G的拉普拉斯矩阵是n阶对称方阵对于n阶无环无向图G，对于任意1

k

n

，从拉普拉斯矩阵L(G)同时删除第k行和第k列，得到n-1阶子方阵，则这个子方阵的行列式（用通常整数运算）等于图G不同生成树的个数76例77v1v2v4v3abcdfe同时删除L(G)第1行和第1列之后计算行列式：所以图G的不同生成树有16个（与例7.1结论一致）例78v1v2v4v3同时删除L(G)第4行和第4列之后计算行列式：所以图G的不同生成树有8个（用破圈法，不含v2v4边的生成树有4个，含v2v4边的生成树也有4个）79无向图与最小生成树

对无向图或有向图的每一条边e附加一个实数w(e),称作边e的权.图连同附加在边上的权称作带权图,记作G=<V,E,W>.设T是G的生成树,T所有边的权的和称作T的权,记作W(T).

最小生成树:带权图权最小的生成树避圈法(Kruskal)——求最小生成树的算法设G是n阶无向连通带权图G.(1)按权从小到大排列边(环除外),设W(e1)≤W(e2)≤…≤W(em).(2)令T

,i

1,k

0.(3)若ei与T中的边不构成回路，则令T

T

{ei},k

k+1.(4)若k<n-1,则令i

i+1,转(3).80例求图的一棵最小生成树

w(T)=38实例817.2根树及其应用有向树与根树、家族树与根子树、有序树根树与有序树的分类r叉(有序)树,r叉正则(有序)树,r叉完全正则(有序)树最优2叉树与Huffman算法前缀码与最佳前缀码中序行遍法、前序行遍法、后序行遍法波兰符号法与逆波兰符号法决策树与信息增益、信息增益比、基尼指数82有向树与根树

有向树:基图为无向树的有向图根树:有一个顶点入度为0,其余的入度均为1的非平凡的有向树树根:有向树中入度为0的顶点树叶:有向树中入度为1,出度为0的顶点内点:有向树中入度为1,出度大于0的顶点分支点:树根与内点的总称顶点v的层数:从树根到v的通路长度树高:有向树中顶点的最大层数83根树(续)根树的画法:树根放上方,省去所有有向边上的箭头如右图所示

a是树根

b,e,f,h,i是树叶

c,d,g是内点

a,c,d,g是分支点

a为0层;1层有b,c;2层有d,e,f;3层有g,h;4层有i.

树高为484家族树定义把根树看作一棵家族树:(1)若顶点a邻接到顶点b,则称b是a的儿子,a是

b的父亲;(2)若b和c为同一个顶点的儿子,则称b和c是兄弟;(3)若a

b且a可达b,则称a是b的祖先,b是a的后代.设v为根树的一个顶点且不是树根,称v及其所有后代的导出子图为以v为根的根子树.85根树的分类有序树:将根树同层上的顶点规定次序r叉树:根树的每个分支点至多有r个儿子r叉正则树:根树的每个分支点恰有r个儿子r叉完全正则树:树叶层数相同的r元正则树r叉有序树:有序的r叉树r叉正则有序树:有序的r叉正则树r叉完全正则有序树:有序的r叉完全正则树86最优2叉树

定义设2叉树T有t片树叶v1,v2,…,vt,树叶的权分别为w1,w2,…,wt,称为T的权,其中

l(vi)是vi的层数.在所有权为w1,w2,…,wt的t片树叶的2叉树中,权最小的2叉树称为最优2叉树.例如W(T1)=47W(T2)=54W(T3)=4287求最优2叉树的算法

Huffman算法:给定实数w1,w2,…,wt,①作t片树叶,分别以w1,w2,…,wt为权.②在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,以这2个顶点为儿子,其权等于这2个儿子的权之和.③重复②,直到只有1个入度为0的顶点为止.

W(T)等于所有分支点的权之和88实例例求权为1,3,4,5,6的最优树.89实例例(续)

W(T)=42,前面的T3也是最优的.90前缀码

设

=

1

2…

n-1

n是长度为n的符号串

的前缀:

1

2…

k

,k=1,2,…,n-1,n

前缀码:{

1,

2,…,

m},其中

1,

2,…,

m为非空字符串,且任何两个互不为前缀2元前缀码:只有两个符号(如0与1)的前缀码如{0,10,110,1111},{10,01,001,110}是2元前缀码

{0,10,010,1010}不是前缀码91前缀码(续)一棵2叉树产生一个二元前缀码:对每个分支点,若关联2条边,则给左边标0,右边标1;若只关联1条边,则可以给它标0(看作左边),也可以标1(看作右边).将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处,所得的字符串构成一个前缀码.例如最佳前缀码设要传输的电文中含有t个字符,字符ai出现的频率为pi,它的编码的长度为li,那么100个字符的电文的编码的期望长度是100.称编码期望长度最小的2元前缀码为最佳2元前缀码.在用2叉树产生2元前缀码时,每个二进制串的长度等于它所在树叶的深度,因而权为100p1,100p2,

,100pt的最优2叉树产生的2元前缀码是最佳2元前缀码.于是,给定字符出现的频率,可以用Huffman算法产生最佳2元前缀码.9293实例例在通信中，设八进制数字出现的频率如下：

0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%采用2元前缀码,求传输数字最少的2元前缀码,并求传输10n(n

2)个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3)的码字传输需要多少个二进制数字?解用Huffman算法求以频率(乘以100)为权的最优2叉树.这里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.94例(续)

编码:0---011---112---0013---1004---1015---00016---000007---00001传100个按比例出现的八进制数字所需二进制数字的个数为W(T)=285.传10n(n

2)个所用二进制数字的个数为2.85

10n,而用等长码(长为3)需要用3

10n个数字.95行遍2叉有序树行遍(周游)根树T

:对T的每个顶点访问且仅访问一次.行遍2叉有序树的方式：①中序行遍法:左子树、根、右子树②前序行遍法:根、左子树、右子树③后序行遍法:左子树、右子树、根当不是正则树时,左子树或右子树可缺省例如,中序行遍:b

a(f

d

g)c

e

前序行遍:a

b(c(d

f

g)e)后序行遍:b((f

g

d)e

c)a96用2叉有序树表示算式每一个分支点放一个运算符.二元运算符所在的分支点有2个儿子,运算对象是以这2个儿子为根的根子树表示的子表达式,并规定被减数和被除数放在左子树上;一元运算符所在的分支点只有一个儿子,运算对象是以这个儿子为根的根子树表示的子表达式.数字和变量放在树叶上.实例例1表示((b+(c+d))

a)

((e

f)

(g+h)

(i

j))的2叉有序树中序行遍:((b+(c+d))

a)

((e

f)

(g+h)

(i

j))前序行遍:((b(cd))a)((ef)((gh)(ij)))后序行遍:((b(cd))a)((ef)((gh)(ij)))注:中序行遍的结果是原式9798波兰符号法波兰符号法(前缀符号法):按前序行遍法访问表示算式的2叉有序树,并舍去所有括号.例1(续)

b+cda

ef

+gh

ij

计算方法:从左到右,每个运算符号对它后面紧邻的2个(或1个)数进行运算.例1(续)设a=3,b=1,c=d=2,e=f=3,g=i=1,h=j=2.

1+22333+1212,

14333+1212

5333+1212,

(15)33

+1212

(15)9+1212,

(15)9312

(15)932,

(15)96,

(15)3,599逆波兰符号法逆波兰符号法(后缀符号法):按后序行遍法访问表示算式的2叉有序树,并舍去所有括号.例1(续)

bcd++a

ef

gh+ij

计算方法:从右到左,每个运算符号对它前面紧邻的2个(或1个)数进行运算.例1(续)

122++33312+12

122++33312+2

,122++33332

122++3

336,122++3

96

122++33,

14+33,53

3,(15)3,5实例例2用2叉有序树表示下述命题公式,并写出它的波兰符号法和逆波兰符号法表达式.(p

q)((p

r)(q

r))解波兰符号法表达式

p

q

pr

qr逆波兰符号法表达式

pq

p

r

qr

注:当一元运算符在运算对象前面时,应画成右儿子.100

ppqqrr决策树（也叫判定树）样例：输入向量与决策值样例集：样例的集合属性：输入向量的每个维度对应一种属性决策树：把输入向量映射为决策值的根树决策树的分支点：从树根开始，每个分支点检测一种属性，不同属性值对应不同分支决策树的树叶：标记了决策值101样例集举例（每行一个样例）样例属性1属性2属性3属性4决策值x111111x211222x312131x422211x523122x623232x731111x831221x932131x1032212102x1=((1,1,1,1),1)，x2=((1,1,2,2),2)，……决策树(圆形分支点、方形树叶)103样例x1=((1,1,1,1),1)的决策路径104样例x9=((3,2,1,3),1)的决策路径105决策树构造对给定样例集，构造的决策树一般不惟一通常希望决策树的大小和深度尽可能小从计算的角度来说，构造最优决策树是个困难问题实用策略优先选择重要的属性，可以用信息增益、信息增益比、基尼指数等指标来衡量属性的重要性信息增益大、信息增益比大、基尼指数小的属性更重要106信息熵设样例集S有k种决策值每种决策值出现的概率分别为p1,

p2,…,

pk

则S的信息熵为

H(S)=（信息熵定义中对数函数以2为底，对于决策树算法来说以10为底也行，因为只考虑信息熵的相对大小）107条件信息熵、信息增益设样例集S的属性y有t种属性值按照属性y把S划分为S1,

S2,…,

St

（要剔除空类），

记作Dy={S1,S2,…,St}则S按照属性y分类的条件信息熵为

H(S|Dy)=属性y的信息增益为IGy(S)=H(S)

H(S|Dy)108信息增益比设样例集S的属性y有t种属性值每种属性值出现概率分别为q1,

q2,…,

qt

则属性y的信息熵为

Hy(S)=属性y的信息增益比为109基尼指数设样例集S有k种决策值每种决策值出现的概率分别为p1,

p2,…,

pk

则S的基尼指数为

Gini(S)=设样例集S的属性y有t种属性值按照属性y的分类为Dy={S1,S2,…,St}

则属性y的基尼指数为

Giniy(S)=110111

组合分析112第8章组合分析初步8.1加法法则与乘法法则8.2基本排列组合的计数方法8.3递推方程的求解与应用1138.1加法法则和乘法法则加法法则与乘法法则应用实例114加法法则使用条件：事件A与B产生方式不重叠适用问题：分类选取.方式分别计数，再相加.推广：事件A1有n1种产生方式，事件A2有n2种产生方式，…,事件Ak有nk种产生的方式，则“事件A1或A2或…Ak”有n1+n2+…+nk

种产生的方式.事件A有m种产生方式，事件B有n种产生方式，则“事件A或B”有m+n种产生方式.115乘法法则使用条件：事件A与B产生方式相互独立适用问题：分步选取.方式是连续的步骤，各步相互独立，分别计数，然后相乘.推广：事件A1有n1种产生方式，事件A2有n2种产生方式，…,事件Ak有nk种产生的方式，则“事件A1与A2与…Ak”有n1n2…nk

种产生的方式.事件A有m种产生方式，事件B有n种产生方式，则“事件A与B”有mn种产生方式.116应用实例例1由数字1、2、3、4、5构成3位数.(1)如果各位数字都不相同，那么有多少种方法?(2)如果必须是偶数，则有多少种方法?(3)其中可以被5整除的有多少个?(4)其中比300大的有多少个?解(1)5×4×3=60.(2)个位为2,4，十位、百位各5种：2×5×5=50.(3)个位为5，十位和百位同(2)：1×5×5=25.(4)百位取3,4或5，十位和个位各5种:3×5×5=75.117应用实例解1400=23527正因子为：2i5j7k，

0

i

3,0

j

2,0

k

1N=(3+1)(2+1)(1+1)=24例2求1400的不同的正因子个数1188.2基本排列组合的计数方法排列组合的分类集合的排列集合的组合多重集的排列多重集的组合119排列组合的分类选取问题：设n元集合S，从S中选取r个元素.根据是否有序，是否允许重复可将该问题分为四个子类型不重复重复有序集合排列P(n,r)多重集排列无序集合组合C(n,r)多重集组合120集合的排列从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r排列的数目记作

S

的r-环排列数=

121集合的组合从n元集S中无序、不重复选取的

r个元素称为S的一个r组合，S的所有r

组合的数目记作证明方法：公式代入组合证明（一一对应）122基本计数公式的应用解令

A={1,4,…,298}，B={2,5,…,299}

C={3,6,…,300}将方法分类：分别取自A,B,C:各

A,B,C各取1个：例1从1—300中任取3个数使得其和能被3整除有多少种方法？123基本计数公式的应用（续）解1000!=1000

999

998

…

2

1

将上面的每个因子分解，若分解式中共有

i个5,j个2，那么min{i,j}就是0的个数.1,…,1000中有

500个是2的倍数，j>500;200个是5的倍数，

40个是25的倍数（多加40个5），

8个是125的倍数（再多加8个5），

1个是625的倍数（再多加1个5）

i=200+40+8+1=249.min{i,j}=249.

例2求1000！的末尾有多少个0？124多重集S={n1

a1,n2

a2,…,nk

ak}，0<ni

+∞(1)全排列r=n,n1+n2+…+nk=n证明：分步选取，先放a1,有种方法；再放a2,有种方法，...,放ak有种方法

(2)若r

ni时，每个位置都有k种选法，得kr.多重集的排列125多重集的组合当r

ni

，

多重集S={n1

a1,n2

a2,…,nk

ak}的组合数为

证明一个

r组合为{x1

a1,x2

a2,…,xk

ak}，其中

x1+x2+…+xk

=r,xi为非负整数.这个不定方程的非负整数解对应于下述排列

1…101…101…10……01…1

x1个

x2个

x3个

xk个r个1，k-1个0的全排列数为126实例解：设盒子的球数依次记为x1,x2,…,xn,则满足下述方程：

x1+x2+…+xn=r，x1,x2,…,xn为非负整数该方程的解的个数为：例3r个相同的球放到n个不同的盒子里，每个盒子球数不限，求放球方法数.127实例解：固定a

和b中间选7个字母，有种方法将它看作大字母与其余17个全排列有18！种，例4排列26个字母，使得a与b之间恰有7个字母，求方法数.128实例（续）解:(1)

(2)例5(1)10个男孩，5个女孩站成一排，若没女孩相邻，有多少种方法？

(2)如果站成一个圆圈，有多少种方法？129实例（续）解：相当于2n不同的球放到n个相同的盒子，每个盒子2个，放法为例6把2n个人分成n

组，每组2人，有多少分法？130实例（续）例79本不同的书，其中4本红皮，5本白皮.(1)9本书的排列方式数有多少？

(2)若白皮书必须放在一起，那么有多少方法？

(3)若白皮书必须放在一起，红皮书也必须放在一起，那么有多少方法？

(4)若把皮和红皮书必须相间，有多少方法？解：

(1)9!(2)5！5！

(3)5！4！2！(4)5！4！1318.3

递推方程的求解与应用Hanoi塔问题递推方程的定义二分归并排序算法的分析快速排序算法的分析递归树分治算法分析的一般公式132Hanoi塔问题Hanoi塔问题：从A柱将这些圆盘移到C柱上去.如果把一个圆盘从一个柱子移到另一个柱子称作1次移动，在移动和放置时允许使用B柱，但不允许大圆盘放到小圆盘的上面.问把所有的圆盘的从A移到C总计需要多少次移动？133算法设计与分析算法Hanoi(A,C,n)//*把n个盘子从A移到C1.Hanoi(A,B,n-1)2.move(A,C)//*把1个盘子从A移到C3.Hanoi(B,C,n-1)

移动n个盘子的总次数为T(n)，得到递推方程

T(n)=2T(n

1)+1.T(1)=1.可以求得T(n)=2n

11秒钟移动1次，64个盘子大约需要5000亿年134135递推方程的定义定义10.5

设序列a0,a1,…,an,…,简记为{an},一个把an与某些个ai（i<n）联系起来的等式叫做关于序列{an}的递推方程.实例：

Fibonacci数列：

fn=fn-1+fn-2,初值f0=1,f1=1

阶乘数列{an}，an=n!：an=nan-1,a1=1

求解方法：迭代法136二分归并排序算法算法Mergesort(A,s,t)//*排序数组A[s..t]1.m(t-s)/22.AMergesort(A,s,m)//*排序前半数组3.BMergesort(A,s+1,t)//*排序后半数组4.Merge(A,B)//*将排好序的A,B归并假设n=2k，比较次数至多为W(n)

W(n)=2W(n/2)+n

1归并两个n/2大小数组的比较次数为n

1137实例

输入：[5,1,7,8,2,4,6,3]

划分：[5,1,7,8],[2,4,6,3]

递归排序前半个数组:[5,1,7,8]

[1,5,7,8]

递归排序后半个数组:[2,4,6,3]

[2,3,4,6]

归并:[1,5,7,8]和

[2,3,4,6]

输出：[1,2,3,4,5,6,7,8]归并过解递推方程139归纳法验证解n=1代入上述公式得

W(1)=1log1

1+1=0，符合初始条件.假设对于任何小于n的正整数t，W(t)都是正确的，将结果代入原递推方程的右边得

2W(n/2)+n

1=2(2k

1log2k

1

2k

1+1)+2k

1=2k(k

1)

2k+2+2k

1=k2k

2k+1=nlogn

n+1=W(n)140快速排序算法算法Quicksort(A,p,r)//*排序数组A[p..r]输入：数组A[p..r]输出：排好序的数组A1.ifp<r2.thenq

Partition(A,p,r)//*以A[p]为准划分A3.A[p]A[q]//*A[p]与A[q]交换

4.Quicksort(A,p,q-1)//*对子数组递归排序

5.Quicksort(A,q+1,r)141Partition(A,p,r)1.x

A[p]2.i

p3.j

r+14.whiletruedo5.repeatj

j16.untilA[j]<x//*右边第1个比A[p]小的A[j]7.repeati

i+18.untilA[i]>x//*左边第1个比A[p]大的A[i]9.ifi<j10.thenA[i]A[j]//*交换A[j]与A[i]11.elsereturnj划分过程14227

99

081364861671088

25

9027

25081364861671088999027

25081310861676488999027

25081310716866488999016250813107866488999027143平均时间复杂度T(n)为对数组的各种输入平均做的比较次数将输入按照A[p]在排好序后的位置分别为1,2,…,n进行分类.假设每类输入出现的