离散数学图与树

第六章树及其应用树是图论中最重要的概念之一。它在许多领域中,特别是在计算机学科中得到了广泛的应用.本章介绍无向树及有向树的概念、性质及其应用.注意:①本章所谈回路均指初级回路即圈或简单回路即闭迹.②在图论中讨论的树,有些术语来源于自然界的树.6.1无向树6.1.1无向树的定义及其性质定义6.1.1连通不含回路的无向图称无向树,简称为树.常用T表示一棵树.平凡图称为平凡树.若非连通无向图的每一连通分支都是树(分支数p≥2),则称其为森林.设T=<V,E>是一棵树.v

V,若d(v)=1,则称v为T的树叶,若d(v)≥2,则称v为分支点。无向树的定义及其性质例图中的①为平凡树,②为由两棵树组成的森林,③为一棵无向树:树有多个等价的定义或性质,以下定理中的各命题都体现树的特征或性质.定理6.1.1

设G=<V,E>是n阶无向图,|E|=m.则以下命题等价(它们的每一个都可以作为树的定义):(1)G为树(即G连通不含回路);(2)G的每对顶点之间有唯一的一条路径;(3)G连通且m=n-1;(4)G中无回路且m=n-1;(5)G中无回路,但在G的任一对不相邻顶点上加一新边后就惟一产生一条初级回路;(6)G连通,但删去任何一边后所得图不再连通(G边为桥).

①②③树叶分支点无向树的定义及其性质证明:

(1)=>(2).设u,v是G中两个顶点,G是树具有连通性,u,v之间有通路,因而必有路径.若路径多于两条,就形成回路,这与G中无回路矛盾.

(2)=>(3).由于G中任意两个顶点之间均有路径,所以任意两个顶点都是连通的,故G是连通图.下面用第二数学归纳法证明m=n-1.

当n=0时,G为平凡树,m=0,结论显然成立.

设n≤k(k≥1)时结论成立,证明n=k+1时结论也成立.设e=(u,v)为G中一条边,由(2)知,u,v之间除路径uv外,再无别的通路,因而G-e得2个连通分支G1和G2.设它们的顶点数与边数分别为n1,n2;m1,m2.易知n1≤k且n2≤k.由归纳假设得m1=n1-1,m2=n2-1.从而得m=m1+m2+1=n1-1+n2-1+1=n-1.

(3)=>(4).只需证明G中无回路.若G中有回路,从回无向树的定义及其性质

路中删去任意一条边后,所得图仍然连通.若所得图中还有回路,再从回路中删除一条边,直到所得图中无回路为止.设共删去r(r≥1)条边所得图为G’.G’无回路,但仍为连通图即G’是树.由(1)=>(2)=>(3)知,G’中m’=n’-1.而n’=n,m’=m-r.于是得m=n-1+r(r≥1),这与条件m=n-1矛盾.

(4)=>(5).由条件(4)易证G是连通的.否则设G有k(k≥2)个连通分支G1,G2,…,Gk.由(4)知,Gi(1≤i≤k)都是树.设Gi有mi条边,ni个顶点,则由(1)=>(2)=>(3)知,mi=ni-1(1≤i≤k).于是n=n1+n2+…+nk=m1+1+m2+1+

…+mk+1=m+k(k≥2).这与m=n-1矛盾.因而G是连通的,又知是无回路的,即G是树.由(1)=>(2)知,G中任意两个不相邻顶点u和v之间存在惟一的路径Puv.Puv再加新边(u,v)形成惟一的圈.无向树的定义及其性质

(5)=>(6).首先证明G是连通图.否则,设G1,G2是G的两个连通分支.v1和v2分别是G1与G2中的一个顶点.在G中加边(v1,v2)不形成回路,这与已知条件矛盾.若G中存在边e=(u,v),G-e仍连通.说明在G-e中存在u到v的通路.

此通路与e构成G中回路,这与G中无回路矛盾.(6)=>(1).只需证明G中无回路.若G中含回路C.在C上删除一边e后,G-e连通,这与(6)中条件矛盾.除了由定理6.1.1.给出的树的充分必要条件外,树还有下述重要的必要条件.定理6.1.2

设T=<V,E>是非平凡的无向树,则T至少有两片树叶.证明:设T是非平凡树,有n个顶点m条边.由树的定义易知,非平凡的树中,每个顶点的度数均大于等于1.设G中有k个1度顶点,即k片树叶,则其余n-k个分支点的度数均大无向树的定义及其性质

于等于2,由握手引理可知

k+2(n-k)≤=2m,由定理6.1.1知m=n-1,代入上式得k+2(n-k)≤2n-2,即k≥2.例6.1.1

设无向树T中有4度、3度、2度的分支点各1个，其余的顶点为树叶,问T中有几片树叶?又问满足T中度序列的无向树在同构的意义下是惟一的吗?解:

设T有x片树叶,则T有x+3个顶点.由定理6.1.1知,T有(x+3)-1条边,再由握手引理x+2+3+4=2(x-2),解得x=5.即T有5片树叶.度序列相同的树不同构。如图,不同构的2

棵树的度序列都为1,1,1,1,1,2,3,4.无向树的定义及其性质例6.1.2

(1)

画出全部不同构的6阶无向树;

(2)

画出度序列为1,1,1,2,2,2,3的所有非同构的7阶无向树树.解:

设所求树的顶点数为n,边数为m.由题设已知n=6.①由无向树的性质可知m=n-1=5;②树是简单图,其顶点的度满足1≤d(vi)≤5,i=1,2,3,4,5;③由握手引理可知,=10.将10度分配6个顶点,满足上述条件,有5种方案:5,1,1,1,1,1;4,2,1,1,1,1;3,3,1,1,1,1;3,2,2,1,1,1和2,2,2,2,1,1(为什么?).不同度序列对应不同构的树,但相同度序列可能对应不止一棵树.方案3,2,2,1,1,1对应2棵非同构的树,这由3度顶点是否夹在两个2度顶点之间而定.其余方案各对应1棵树.无向树的定义及其性质

所得6棵非同构的树如图所示:

(2)画出所有非同构的无向树不是件易事,但当n较小时还是不难画出的.本题是7阶非同构无向树度数分配方案中的一种,它有3个2度顶点,1个3度顶点,3个1度顶点,3度顶点与1个2度顶点相邻;与2个2度顶点相邻;与3个2度顶点相邻,所得3棵树显然非同构,所以共有3棵非同构的树:生成树与基本回路和基本割集6.1.2生成树与基本回路和基本割集定义6.1.2

设G=<V,E>是无向连通图.若树T是G的生成子图,则称T是G的生成树。G在T中的边称为T的树枝。G不在T中的边称为T的弦.T所有弦的集合的导出子图称为T的余树.余树未必连通,也未必不含回路.因而余树不一定是树,更不一定是生成树。图中②为①的生成树,③为②的余树:生成树与基本回路和基本割集定理6.1.3

任何无向连通图G都存在生成树.证明:若G中无回路,则G本身就是G的生成树.若G中含有回路C,在C中任意删去一条边,不影响图的连通性.若所得图中还有回路,就在此回路中删去一条边,继续这个过程,直到所得图中无回路为止.设最后的图为T,则T是G的生成树.由定理6.1.3可得以下3个推论.推论1.无向连通图G的生成树在下述两种意义下都不一定是惟一的(如图所示):

①非同构意义下;即两棵生成树存在不同的边就认为它们是不同的.

②在同构的意义下;即连通图G可存在非同构的生成树.推论2.设n阶无向简单连通图G中有m条边,则m≥n-1.生成树与基本回路和基本割集证明:由定理6.1.3,G中存在生成树T.设T有m’条边,m’=n-1.因而m≥m’=n-1.推论3.设n阶无向连通图G中有m条边,T是G的一棵生成树,T’是T的余树,则T’有m-n+1条边,T有m-n+1条弦(为什么).例6.1.3

给出下图中①的两棵非同构的生成树,并指出它们的树枝和弦。解:图中②和③深绿色边所示的图都是图①的生成树,

显然它们是非同构的.e2,e3,e4,e5为T②的树枝,e1,e6为弦;e1,e2,e4,e5为T③的树枝,e3,e6为弦.在②中加弦e1;e6分别产生初级回路e3e1e4e2和e6e4e5.在③中加弦e3;e6分别产生初级回路e3e1e4e2和e6e4e5.这些回路的共同特点是:它们中均只含1条弦,其余的边都是生成树与基本回路和基本割集

树枝.称这样的回路为基本回路.定义如下：定义6.1.3

设G是m条边的n阶连通图,T是G的一棵生成树,T的m-n+1条弦为e1,e2,…,em-n+1.G中仅含T的一条弦er(1≤r≤m-n+1)的回路Cr称作对应弦er的基本回路.{C1,C2,

…,Cm-n+1}称作对应生成树T的基本回路系统.在例6.1.3中,树②对应弦e1的基本回路是e1e4e2e3;对应弦e6的基本回路是e6e4e5.基本回路系统为:{e1e4e2e3,e6e4e5}.树③的基本回路系统是{e3e1e4e2,e6e4e5}.一般,G的不同生成树的基本回路可能不同,但基本回路的个数是相同的,都等于m-n+1.再看例6.1.3图②,{e5,e6},{e4,e1,e6},{e2,e1},{e3,e1}

是图中的4个割集,它们有一个共同的特点,每个割集中生成树与基本回路和基本割集

都有且只有1条树枝,其余边均为弦.称这样的割集为生成树T②对应的基本割集.下面是其一般定义.定义6.1.4设T是n阶连通图G的一棵生成树,e1,e2,…,en-1为T的树枝.设Sr是只含树枝er(1≤r≤n-1),其余边均为弦的割集.称Sr为对应树枝er的基本割集,{S1,S2,…,Sn-1}为对应T的基本割集系统.一般,G的不同生成树的基本割集可以不同,但基本割集的个数是相同的,都等于n-1.在例6.1.3中,对应生成树③也有4个基本割集:{e5,e6},{e4,e3,e6},{e2,e3},{e1,e3}.由它们组成的集合,就是③

的基本割集系统.例6.1.4

在题图G中,深绿色边构成G的生成树T.求对应T的基本回路和基本生成树与基本回路和基本割集

割集系统.解:G的顶点数n=6,边数m=9,基本回路个数为m-n+1=4;基本割集个数为n-1=5.T的4条弦为e,b,c,i.它们对应的基本回路分别是:Ce=edfg,Cb=bda,Cc=cadfgh,Ci=igh.

基本回路系统为{Ce,Cb,Cc,Ci}.T的5条树枝是a,d,f,g,h.所对应的基本割集分别是:Sa={a,b,c},Sd={d,e,b,c},Sf={f,e,c},Sg={g,e,i,c},Sh={h,i,c}.基本割集系统为{Sa,Sd,Sf,Sg,Sh}.你能找出求树枝e’对应的基本割集的方法吗?(将e’从T

中删除.T-e’有两个连通分支,记为T1,T2.设V1,V2为T1,T2的顶点集.则e’对应的基本割集Se’={e|e∈E(G)∧e的一个端点在V1中,一个端点在V2中}.无向连通图G的怎样的边不在G的任何生成树中,怎样的边必在G的每个生成树中?(环;桥或割边)最小生成树6.1.3最小生成树现在我们讨论最小生成树问题。先看一个例子:假定要修建连接n个城市的公路网,已知连接城市vi与vj的公路造价是wij,要求设计公路网使总造价最小。如果把城市看成顶点,公路看成边,公路的造价wij看成是边的权,则该问题就是在一个赋权无向连通图中求一棵权最小的生成树.定义6.1.5

设G为无向连通赋权图,T是G的一棵生成树,T的各边的权的和称为T的权,记作W(T).G的所有生成树中权最小的一棵生成树称为G的最小生成树。最小生成树亦称最优树。设G=<V,E,W>是赋权无向连通图.求G的生成树T,使得权W(T)=最小.图G是有限图,只有有限棵生成树,故最优树总是存在的.

最小生成树1956年克拉斯科(J.Kruskal)给出了求解上述问题的一个算法.这个算法称为Kruskal算法,其步骤如下:☆输入赋权无向连通图G=<V,E,W>,其中|V|=n.①取G的非环边,使得W(e)最小;

②边e1,e2,…,ek选定后,从E-{e1,e2,…,ek}中选边ek+1满足以下两个条件:

(a)G[{e1,e2,…,ek+1}]不含圈,及

(b)

在满足(a)的前提下W(ek+1)最小；

③当②不能进行时,则算法停止并输出G[{e1,e2,…,ek}].上述Kruskal算法求最优树的方法,称避圈法.下面是由

Kruskal算法求最优树的具体例释:对最优树算法的例释

**Kruskal算法的输出一定是G的最优树吗？以下定理从理论上回答了这个问题.**定理6.6.4

Kruskal算法输出的T*=G[{e1,e2,…,ek}]是赋权连通无向图G的一棵最优树.**Kruskal算法证明:

首先证明当算法终止时T*一定是G的生成树.若G[{e1,e2,…,ek}]不是G的生成树,则由算法知它是一森林.

这样由G的连通性知,总可以在E-{e1,e2,…,ek}中选边

ek+1使得G[{e1,e2,…,ek,ek+1}]无圈且W(ek+1)最小.这样算法会进行下去直到G[{e1,e2,…,ek}]是生成树,即k=n-1时为止.

若T*不是最优树,则在全部最优树中选最优树T,使T与T*的公共边数最大.因T*不是最优树,T*≠T.设在T*的边集{e1,e2,…,en-1}中不属于T的下标最小的边为ek,由定理知T+ek包含圈C,因T*是树,故C中有不属于T*的边e,显然

e是T的边.因而T’=(T+ek)-e是G的生成树.因ek是T*中不属于T的下标最小的边,故e1,e2,…,ek-1既是T*中的边也是T中的边.因e不是T*的边,故e

E-{e1,e2,…,ek-1}.又**Kruskal算法

因e是T中的边,所以e1,e2,…,ek-1,e都是T中的边.于是

G[{e1,e2,…,ek-1,e}]不含圈.

当克拉斯科算法进行到第k步时,e和ek都属于E-{e1,e2,

…,ek-1}又G[{e1,e2,…,ek-1,e}]和G[{e1,e2,…,ek-1,ek}]

都不含圈,由算法②中的(b)可知W(ek)≤W(e),从而W(T’)=W(T)+W(ek)-W(e)≤W(T),故T’也是G的一棵最优树.但

T’与T*的公共边数比T与T*的公共边数多1，这与T的选择矛盾.求最优树的算法不止一种.下面给出的是称为破圈法的最优树算法.☆输入赋权无向连通图G=〈V,E,W〉.

①选取e1,使得W(e1)最大且G-e1连通;②当Gk=G-{e1,e2,…,ek}选定时,在E-{e1,e2,…,ek}**Kruskal算法

中选边ek+1满足以下两个条件：

(a)Gk+1=G-{e1,…,ek,ek+1}连通,及

(b)

在满足(a)的前提下,W(ek+1)最大;

③当步骤②不能进行时输出Gh=G-{e1,…eh}.不难证明,这一算法的输出Gh是G的一棵最优树.上面所介绍的两个算法分别被形象地称为避圈法与破圈法.这两个算法有一共同特点,就是在过程中的每一步都取目前最为有利的选择.这种只顾眼前的最佳选择而不顾整体效果如何的算法,称之为贪婪型算法.需要指出的是:一般,贪婪型算法并不一定总能给出问题的最优解。根树及其应用6.2根树及其应用

一个有向图D,如果D的基础图是无向树,则称D为有向树.在有向树中,最为重要的是根树,它在诸如数据结构,数据库等专业课程中占据着极其重要的位置。6.2.1根树及其分类定义6.2.1

一棵非平凡的有向树,如果有一个顶点的入度为0,其余顶点的入度均为1,则称此有向树为根树.在根树中,称入度为0的顶点为树根;称入度为1,出度为0的顶点为树叶;称入度为1,出度大于0的顶点为内点;内点和树根统称为分支点。右图中的①是一棵根树,

②是根树①的简图(①的基础图,是一般根树图)。树根树叶内点分支点根树及其分类

在根树T中,树根到任一顶点v的路长称为v的层数,记作

l(v),层数最大顶点的层数称为树高,记作h(v).h(v)为根树T的高度。上页附图所示根树T中,有0,1,2,3共4层,树高为3.

一棵根树可以看作一棵家族树:若顶点a邻接到顶点b则称b为a的儿子,a为b的父亲;若b,c的父亲相同,则称b,c为兄弟;若a≠d,而a可达d,则称a为d的祖先,d为a的后代.

在根树T中,称由一个非根顶点a及其后代导出的子图T’为T的以a为根的根子树。上述概念,从前页附图所示根树T中,都可显然指定.在应用中,往往将根树同层上的顶点或它们所关联的边排序(次序可全标在顶点处,也可以全标在边上,标序数不要求一定是连续的数),这样的根树称为有序树。根树及其分类根据根树各分支点儿子的多少以及顶点是否排序,可将根树分类:

设T是非平凡的根树.如果T的每个分支点至多有r个儿子,则称T为r元树;如果T的每个分支点都恰有r个儿子,则称T为r元正则树,进而,若所有树叶的层数都为树高,则称T为r元完全正则树.如果T还是有序树,则相应称之为r元有序树,r元有序正则树和r元有序完全正则树。在所有r-元树中,2元树最重要,在数据结构中称2叉树.下面讨论2元树的应用.6.2.2最优树与哈夫曼(Huffman)算法定义6.2.2

设2元树T有t片树叶v1,v2,…,vt,权分别为w1,w2,…,wt,称W(T)=为T的权,其中l(vi)是vi的层数.在所有含有t片树叶,带权w1,w2,…,wt的2元树中,最优树与哈夫曼算法

权最小的2元树称最优2元树。附图中,给出了带权1,3,4,5,6

的4棵2元树:其权分别为47,54,43和42(由哈夫曼算法将知,权为42的第四棵2元树为最优2元树).

☆Huffman算法给定递增实数列:w1≤w2≤…≤wt.

①连接权为w1,w2的两片树叶,得一分支点,其权为w1+w2;

②在w1+w2,w3…,wt中选出两个最小的权,连接它们对应的顶点(不一定是树叶),得新分支点及所带的权;最优树与哈夫曼算法

③重复②,直到形成t-1个分支点,t片树叶为止。例6.2.1

求带权为1,3,4,5,6的最优2元树,

并计算它的权.解:为了熟悉哈夫曼算法,右图将计算最优树的过程分步骤给出.所得最优树是图中排在最右的一棵树,其权W(T)=42.在计算机通信事业中,常用二进制码表示字符.例如用00,01,10,11分别表示A,B,C,D.称这种表示法为等长表示法.在传输过程中,若A,B,C,D出现的频率相等,用等长的表示法是很好的表示法.但当它们出现的频率并不根树及其应用

相同时,譬如A占50%,B占25%,C占20%,D只占5%,能否找到非等长的表示法,既能节省二进制数位,又能实现准确无误地传输?这就是下面要讨论的所谓前缀码.6.2.3最佳前缀码定义6.2.3

设是长度为n的符号串,称其串,

分别为该符号串的长度为1,2,…,n-1的前缀.设符号串集合A={}.若对于任意的βi,βj∈A,i≠j,βi,βj都互不为前缀,则称A为前缀码.如果A中符号串都以0,1两个符号构成,则称A为二元前缀码。例如{1,01,001,000},{00,10,11,011,0100,0101}都是二元前缀码.而{1,01,111,1100}不是前缀码,因为1是111和1100的前缀。如何产生二元前缀码?可用2元树产生二元前缀码.最佳前缀码给定一棵有t片树叶的2元树T.设v为T的一个分支点,则v至少有一个儿子,至多有两个儿子.若v有两个儿子,在由引出的两条边上,左边的标上0,右边的标上1.若v只有一个儿子,在由v引出的边上可标上0,也可标上1.设vi是T的任意一片树叶,从树根到vi的通路上各边的标号组成的0,1符号串放在vi处,t片树叶处的t个符号串组成的集合为一个2元前缀码.由以上的作法看出,vi处的符号串的前缀均在vi所在的通路上除vi外的顶点处达到,因而所得符号串集合为2元前缀码.特别若T存在带一个儿子的分支点,则由T产生的前缀码可能不惟一,但若T为正则2元树,则由T产生的2元前缀码是惟一的.此即定理6.2.1

由一棵给定的2元正则树,

可以产生惟一的一个二元前缀码。右图所示2元正则树产生的前缀码为:{00,10,11,010,0110,0111}.根树及其应用若已知要传输符号的频率,用各符号出现频率的100倍当权,用Huffman算法求最优二叉树T,则称由T产生的前缀码为最佳前缀码.用最佳前缀码传输对应的符号,可以使传输的二进制位数最省。例6.2.2

设在通信中八进制数字出现的频率为:7-5%,6-5%,5-5%,4-10%,3-10%,2-15%,1-20%,0-30%.求传输它们的最佳前缀码。解:用100乘各频率,并写成递增序得:w1=5,w2=5,w3=5,W4=10,w5=10,w6=15,w7=20,w8=30,它们与7,6,5,4,3,2,1,0分别对应.用哈夫曼算法求最优2元树如图所示:

图中方框内的八个码字组成的集合是最佳前缀码.根树及其应用

8个码字传输数字的对应情况是:01-0,11-1,001-2,100-3,101-4,0001-5,00001-6,00000-7.注意:除了等长的码字可以互换(如0与1的码字,2,3,4的码字,6,7的码字)外其余的码字不可互换.显然一旦码字与传输的数字定下来以后,等长的码字也是不能互换的。6.2.4根树的周游及其应用

若对于一棵根树的每个顶点都访问一次且仅访问一次,则称为行遍或周游一棵树。对于2元有序正则树,主要有以下3种周游或行遍方法:①中序行遍法.其访问次序为:左子树,树根,右子树;②前序行遍法.其访问次序为:树根,左子树,右子树;③后序行遍法.其访问次序为:左子树,右子树,树根.对下页图的根树按中序,前序,后序的周游结果分别为:根树及其应用(db(hei))a(fcg),a(bd(ehi))(cfg),(d(hie)b)(fgc)a.利用2元有序树可以表达算式,然后根据不同的访问方法得到不同的算法.利用2元有序树存放算式时,

在每一步上都要将算式(或其子式)的最高层次的运算放在树根(或子树的树根)上,将参加运算的数放在树叶上,并规定被除数、在左子树树叶上。例6.2.3

①用2元有序树表示算式((a-b*c)*d+e)÷(f*g+h).②用3种行遍法访问该2元有序树.解:①的解如图.②中序:((a-b*c)*d+e)÷(f*g+h);前序:÷+*-a*bcde+*fgh(称波兰符号法);后序:abc*-d*e+fg*h+÷(称逆波兰符号法)。对第六章树及其应用的小结定义部分：无向树、森林、平凡树、树叶、分支点，生成树、树枝、弦、余树，最优树,基本回路和基本割集,根树,r元树；定理部分：关于树定价的(6条)定理,平凡树至少有两片树叶定理,无向连通图存在生成树定理及其三条推论,2元正则树产生惟二元前缀码定理；算法部分：Kruskal算法,Huffman算法；术语部分：避圈法与破圈法,贪婪算法；例题部分：关于树中的度,在连通赋权图中求最优树,基本回路和基本割集,根树及应用的例.第六章树及其应用的课后作业1.画出互不同构的6棵6阶树.2.证明:Δ(T)≥k的树T至少含有k片树叶.3.证明阶数大于等于2的连通无向图中至少有两个顶点,将它们删除之后得到的图仍是连通图.4.在赋权无向连通图G中有一长为k的圈C,且C上每一边的权皆取最小值.证明G中至少有k棵不同的最优树.**6.3超图离散数学的一项基本任务是研究集合的各类有限子集族的结构和性质。这些子集族通常具有实际的应用背景和优美的数学结构。所谓超图实际上就是有限集合上的有限子集族。人们之所以将其称为超图主要是强调处理这类数学对象时的数学观点，数学语言和研究方法。它们大多是图论式的，是图论中的概念和方法非常自然的推广。用图论的语言描述这类问题往往具有直观和易于把握本质的特点。可以把无向图理解为在有限集合上，由一元子集与二元子集构成的子集族，所以超图是无向图的一个自然的推广。超图理论在各类学科中有着广泛的应用。如在计算机学科中,有关数据库结构的研究,以及很多优化问题的算法都是以超图理论为理论基础的.本节讨论超图的一些最基本的概念和性质。

超图定义6.3.1

设V={v1,v2,…,vn}是一有限集合,V上的一个超图H是V上的一个子集族(E1,E2,…,Em),其中Ei满足①

Ei≠φ,1≤i≤m;②称vi(1≤i≤n)为超图H的顶点,Ei(1≤i≤m)为超图H的边,n称为超图H的阶。注意:超图的边并不要求互异。超图H=(E1,E2,…,Em)称是简单的,若Ei

Ej=>i=j.超图

H=(E1,E2,…,Em)称为r-均匀的,如果|Ei|=r(1≤i≤m).若超图H=(E1,E2,…,Em)满足|Ei|≤2(1≤i≤m),则H即为一个无向图。反之任何一个无孤立顶点的无向图都是一个超图。定义6.3.2

设H=(E1,E2,…,Em)是V={v1,v2,…,vn}上的超图.定义矩阵AH=(aij)n×m如下:超图

vi

Ej

,vi

Ej.则称AH为超图H的关联矩阵。也可用平面上的图形来表示一个超图.将v1,v2,…,vn用平面上的n个小圆圈表示.如果Ei={v},则Ei用过v的一个环来表示.如果E={u,v},则Ei用连接u与v的线段来表示.如果|Ei|≥3，则Ei用恰包含Ei中点的闭曲线表示。图21给出了超图H的图形和该超图的关联矩阵:

超图定义6.3.3

设H=(E1,E2,…,Em)是V={v1,v2,…,vn}上的超图。令:V*={e1,e2,…,em},Vi={ej|vi∈Ej},1≤i≤n.则

H*=(V1,V2,…,Vn)是V*上的超图,称为H的对偶超图。图22给出了图21中超图的对偶超图的图形及其关联矩阵:超图容易看出,H*的关联矩阵是H的关联矩阵AH的转置,即.因而有(H*)*=H.

设H=(E1,E2,…,Em),r(H)=,则分别称之为超图H的秩与反秩。若r(H)=s(H),则H是均匀超图。

设H是V上的超图.由H定义V上的简单图(H)2:u,v(u≠v)

在(H)2中有边相连

存在H的边E,使得u,v∈E.称(H)2是超图H的二截图.当(H)2连通时,称H是连通的.H的连通分支数定义为(H)2的连通分支数。

设H=(E1,E2,…,Em)是V上的一个超图.定义V*={e1,e2,…,em}上的图L(H)为:ei与ej在L(H)中相连

Ei∩Ej≠φ,则称L(H)为H的代表图或线图。

超图很多超图的线图都是有趣的图类。

设H是V上的超图.P=v0E1v1E2…Ekvk是H中的顶点与边的交替序列.如果vi(0≤i≤k)彼此不同,Ei(1≤i≤k)亦彼此不同且vi-1,vi∈Ei(1≤i≤k),则称P是H中的一条长为k的从v0到vk的路.如果v0=vk,k≥2且其它顶点边均互异,

则称P是一个长为k的圈.注意:只包含一个顶点的边在超图中不称为圈.

显然超图H是连通的

H中任意两顶点之间都有路相连.定理6.3.1n阶连通超图H=(E1,E2,...,Em)中不存在圈

.证明:作二部图G(H).取H的顶点做为G(H)的一组顶点.取H的边做为G(H)的另一组顶点.在G(H)中vi与Ej相邻当且仅当vi∈Ej.图G(H)共有m+n个顶点，条边.注意到

超图

超图H无圈

G(H)无圈,H连通

G(H)连通.故H是无圈连通超图

G(H)连通无圈,即G(H)是树.设G(H)的边数与顶点数分别为:m(G(H))和n(G(H)),则由树的一组等价定义知,连通图G(H)是树当且仅当m(G(H))=n(G(H))-1,即:或.

设H=(E1,E2,…,Em)是V上的超图.如果,并且对任意的边Ei

,T∩Ei≠φ,则称T是H的一个横截或一个径集.若T是H的横截,但对,T-{x}都不是H的横截,则称T是H的一个极小横截。

设T1,T2,…,Tk是H的全部互异的极小横截,则易证(T1,T2,

…,Tk)是V上一个简单超图,称H的横截超图,记为Tr(H).例6.3.1设V是一个n元集合.由V的全部r(1≤r≤n)元子集构成的超图称为V上的完全r均匀超图,记为.显然共有(n,r)条边.容易验证,任何一个具有n-r+1个顶

超图

点V的子集,都是超图的1个极小横截,∴.我们引出下述定理,但不加证明:定理6.3.2

若H是一个简单超图,则Tr(Tr(H))=H.从定理5.3.2立得,对任意超图H与F,Tr(H)=F

Tr(F)=H利用该结果可以解决下述有趣问题:例6.3.2

保险柜钥匙问题。国家某安全部门每个成员的保密级分别为1,2,…,k,共k个级别.规定当在场的成员保密级别之和大于等于r时就可以打开机密文件保险柜.该机密文件柜的锁和钥匙应该如何配备?解:

该安全部门成员构成一个有限集合V.每一个可以打开文件柜的成员小组构成V的一个子集。设全部能打开文件柜的成员的极小组分别是E1,E2,…,Em

(即Ei(1≤i超图

≤m)组成员的保密级别之和大于等于r,但对任一v

Ei,Ei-v成员组的保密级别之和小于r),则H=(E1,E2,…,Em)

构成了一个超图.设Tr(H)=(F1,F2,…Fh),则Tr(H)就给出了一个锁和钥匙的配置方案.共用h把锁,将第i把锁的钥匙分配给Fi组中的人.那么部门任何成员小组E,只要它含有Ei(1≤i≤m)之一必能打开文件柜,否则它将一定不能打开文件柜.为了说明这一点只需证明Ei(1≤i≤m)是超图(F1,F2,…,Fh)的全部极小横截,因为这时包含某个Ei的成员有每一把锁的钥匙,而不包含任一Ei(1≤i≤m)的成员小组,必定缺少某把锁的钥匙.即是要证明Tr((F1,F2,…,Fh))=H.但已知Tr(H)=(F1,F2,

…,Fh),因而由定理2知:Tr((F1,F2,…,Fh)=Tr(Tr(H))=H.

超图☆所以解决这一问题的实际步骤是：

①构造超图H;②计算超图Tr(H)(已有现成的算法).☆如果安全部门共有n个成员,并规定只要有r个人在场就可打开文件柜,那么这个问题的答案是简单的.这时H=Knr,Tr(H)=Knn-r+1,即需要配置Cnn-r+1把不同的锁,且每把锁需有n-r+1把钥匙.n个成员中的每n-r+1个成员的不同小组每一组的同组成员都恰好得到同一把锁的钥匙,就是本问题锁与钥匙的配置方案.超图小结定义部分：n元集上的超图H,超图H的关联矩阵,对偶超图,超图H的秩与反秩,2截超图及其连通性,超图H中长为k的路和圈,超图的横截与极小横截,横截超图；定理部分：连通超图无圈的充要条件,简单超图与极小横截;例题部分：均匀超图的极小横截,保险柜钥匙问题.建议作业:练习8-8(P255)(1)(2)(3)(4).课程作业总括一、命题逻辑基本概念部分1.构造一个只含命题变元P,Q,R的命题公式,使之当P,Q为真R为假时该命题公式为真,否则为假.2.构造一个只含命题变元P,Q,R的命题公式,使之当P,Q和

R恰有两个为真时该命题公式为真,否则为假.3.将下述电话系统规范写成命题符号形式:

如果电话号码数据库是打开的,那么监督程序被置于关闭状态,只要系统不在初态(首先将原子命题设为命题标识符,然后恰当使用逻辑联词形成公式).4.证明定理1.1:命题公式A=B当且仅当A

B是永真式。5.运用真值表方法证明：

①¬(P∨(¬P∧Q))与¬P∧¬Q逻辑等值；课程作业总括

②P∧Q→P∨Q是重言式.6.复习(理解并区分)以下概念:

逻辑等值式;重言式(永真式);矛盾式(永假式);一般可满足式。二、命题逻辑等值演算部分1.按提示和要求证明异或具有以下性质：

①PQ＝QP(真值表法).②P

(QR)＝(PQ)

R(等值推演并用①).③P∧(QR)＝(P∧Q)

(P∧R)(考虑改∧为∨).④PP＝F,FP＝P,TP＝¬P(由定义).⑤若PQ＝R,则QR＝P,RP＝Q,进而PQR=0(等值替换并用①,②).课程作业总括2.用逻辑联词或非式等值表示与非式P↑Q.3.用等值演算法证明P→Q＝¬Q→¬P.4.证明P↑(Q↑R)≠(P↑Q)↑R以及P↓(Q↓R)≠(P↓Q)↓R(即证↑与↓不具有结合律).三、范式部分1.写出含有3个命题变元的极大项或极小项(所求布尔项的脚标是十进制脚标):m0,

M0;m7,

M7;m5,M5.2.设命题公式G(P,Q,R)的主析取范式为

P∧

Q∧

R,求

命题公式

G(P,Q,R)的主析取范式和主合取范式.3.求命题公式(

(P→Q)∨R)∧(F→R)的对偶式.4.由范式判定命题公式P→P∧(Q→P).5.求命题公式P∧(Q∨

R)的主析取范式和主合取范式.课程作业总括6.在校田径运动会上四位短跑好手A,B,C,D同组比赛,甲,

乙,丙三位观众同学猜名次.甲猜A第一,B第二;乙猜C

第二,D第三;丙猜A第二,D第四.如果三位同学都只猜对了一项,求四位短跑好手的实际名次.四、命题逻辑推理部分1.在推理系统P中证明:小王学过英语或日语。如果小王学过英语,则他去过英国。如果他去过英国,他也去过日本。所以小王学过日语或去过日本。2.在推理系统P中证明:如果周静是上海人,则她是复旦大学或中山大学的学生。如果她不想离开上海,她就不是中山大学学生。周静是上海人并且不想离开上海。所以她是复旦大学学生。课程作业总括五、一阶逻辑的公式与分类部分1.符号化命题“不存在可导但不连续的函数”.2.符号化命题“每个人的外公都是她母亲的父亲”.3.符号化命题“在美国留学的学生未必都是亚洲人”.4.熟练掌握课程讲习所举的11个例子和复习讲习所举的5

个做解释的例子.5.深入理解对一阶谓词公式的解释的概念.六、一阶逻辑等值演算部分1.求一阶公式

(x)((y)G(x,y)→(x)(y)(H(x,y)∧(y)(G(y,x)→H(x,y))))的前束范式.2.求1.中公式的司寇伦范式.3.给出一阶公式(x)(y)G(x,y)与其司寇伦范式(y)G(课程作业总括a,y)不逻辑等值的一种解释I.七、一阶逻辑推理理论1.在自然推理系统F中,构造以下证明:

每个大学生或者享有奖学金或者交费学习.每个大学生当且仅当学习评优才享有奖学金.有些大学生学习被评优,但并非所有大学生学习都能被评优.因此,有些大学生要交费学习.八、证明技巧部分1.用数学归纳法证明:前n个正奇数之和为n2.2.用数学归纳法证明:∀n∈Z+,3|(n3-n).3.用数学归纳法证明:∀n∈Z+,n!≥2n-1.4.证明命题“对于每个正整数n,都存在n个连续的正合数”.课程作业总括九、集合及其表示法部分1.用集合演算的第①种方法证明:对任意集合A,B有

(1)A∩E=A.(2)A∩～A=φ.(3)A-B=A∩～B.(4)A

A∪B.(5)A∩BA.2.用集合演算的第②种方法证明:对任意集合A,B,C有A-(B∪C)=(A-B)∩(A-C).十、一般二元关系部分1.证明:①A×(B∪C)=(A×B)∪(A×C);②A×(B∩C)=(A×B)∩(A×C).课程作业总括自反性反自反对称性反对称传递性集合表达式关系矩阵关系图自反性反自反性对称性反对称性传递性R-1R∩SR∪SR-SRS举反例举反例举反例举反例举反例举反例举反例举反例2.按照要求填表:3.按照要求填表:课程作业总括4.设R是非空集合A上的自反关系.证明:R在A上对称且传递当且仅当成立若〈a,b〉〈a,c〉∈R,则〈b,c〉∈R.5.设R,S,T分别是A到B,B到C和C到D的二元关系,证明(二元关系关于复合具有结合律):(RS)T=R(ST).十一、等价关系与划分部分1.设A={1,2,3},R={〈1,2〉,〈2,3〉,〈3,1〉},求r(R),s(R),t(R),sr(R),tr(R)和ts(R).2.设P(x):x≥3是整数集合I上的一元谓词.在I上定义关系R:iRjP(i)=P(j).证明R是I