山东科技大学-离散数学7-6对偶图与着色7-7-树+复习

7-7树树是图论中重要的概念之一，它在计算机科学中应用非常广泛，这里将介绍树的一些基本性质和应用。一、树的概念1、定义7-7.1：一个连通且无回路的无向图称为树（tree）。树中度数为1的结点称为树叶（leave）。度数大于1的结点称为分支点（branchednode）或内点。每个连通分支是树的无向图称为森林。平凡图也是树，称为平凡树。2、定理7-7.1：给定图T=<V，E>，以下关于树的定义是等价的。(1)无回路的连通图(2)无回路且e=v-1(3)连通且e=v-1(4)无回路，但增加一边后得到且仅得一个回路(5)连通，但删去任一边后就不连通(6)每一对结点间有且仅有一条通路。

证明思路：6个命题可以循环推出。即(1)

(2)

(3)

(4)

(5)

(6)

(1)

3、定理7-7.2：任一棵树中至少存在两个叶。证明：因T连通则

u∈T，deg(u)≥1。设T有k个一度点，其它点均大于等于2，则

2e=∑deg(vi)≥k+2(v-k)=2v-k。

因e=v-1，故2(v-1)≥2v-k，则k≥2。二、生成树有一些图，本身不是树，但它的子图却是树，一个图可能有许多子图是树，其中很重要的一类是生成树。1、生成树定义7-7.2：若G的生成子图是一棵树，则称这棵树为G的生成树。设G的一棵生成树为T，则T中的边称为树枝，在G中而不在T中的边称弦，所有弦的集合称为生成树T的补。e1、e7、e5、e8、e3是T的树枝，e2、e4、e6是T的弦，{e2、e4、e6}是T的补。2、定理7-7.3：连通图至少有一棵生成树。证明：如果连通图G无回路，则G本身就是它的生成树。如果G有回路，则在回路上任取去掉一条边，得到图G1仍是连通的，如G1仍有回路，重复上述步骤，直到图Gi中无回路为止，此时该图就是G的一棵生成树。由定理的证明过程可以看出，一个连通图可以有许多生成树。因为在取定一个回路后，就可以从中去掉任一条边，去掉的边不一样，故可能得到不同的生成树。一般如果G有v个点e条边连通，则e≥v-1，则G删除e-(v-1)条边，破坏了e-(v-1)个回路，必成G的一棵生成树，这是”破圈法”。也可以从e条边中选取v-1条边并使它不含有回路，这是”避圈法”。3、定理7-7.4：一条回路和任何一棵生成树的补至少有一条公共边。证明：若有一条回路和一棵生成树的补没有公共边，那么这回路包含在生成树中，然而这是不可能的，因为一棵生成树不能包含回路。4、定理7-7.5：一个边割集和任何生成树至少有一条公共边。证明：若有一个边割集和一棵生成树没有公共边，那么删去这个边割集后，所得子图必包含该生成树，这意味着删去边割集后仍是连通图，与边割集定义矛盾。5、最小生成树设G=<V，E>是一连通图，G的每一条边e有权C(e)，G的生成树T的权w(T)就是T的边的权和。定义7-7.3：在图G所有生成树中，树权最小的那棵树称为G的最小生成树。

构造图的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。该问题等价于：具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能的小。克鲁斯卡尔算法的基本思想：abcdegf195141827168213ae12dcbgf7148531621例如:7121819求最小生成树的克鲁斯卡尔(Kruskal)算法(避圈法)：a)在G中选取最小权的边，记作e1，置i=1。b)当i=n-1时结束，否则转c)。c)设已选择边为e1，e2，……ei，此时无回路。在G中选取不同于这i条边的边ei+1，该边使得{e1，…，ei+1}生成的子图中无回路，并ei+1是满足该条件中权最小的一条边。d)置i：=i+1，转b)。定理7-7.6：克鲁斯卡尔(Kruskal)算法产生的是最小生成树。作业327页（6）(b)的最小生成树有5棵，最小生成树的树权为11。(a)的最小生成树：7-8根树及其应用一、根树1、有向树定义7-8.1

如果一个有向图在不考虑边的方向时是一棵树，那么，该有向图称为有向树。2、根树

定义7-8.2

一棵有向树,如果恰有一个结点的入度为0，其余所有结点的入度都为1,则称为根树(rootedtree)。入度为0的结点称为T的树根。出度为0的结点称为树叶。出度不为0的结点称为分支点或内点。

根树的画法有：树根在下，向上生长；树根在上，向下生长。习惯把有向树的根画在最上方，边的箭头全指向下，则可以省略全部箭头，树根到一个结点的有向通路的长度称为该点的层数。所有结点的最大层数称为树高。3、子树定义7-8.3：任一结点v及其后代导出的子图称为根树的子树。

定义7-8.3

根树包含一个或多个结点,这些结点中的某一个称为根,其他所有结点被分成有限个子根树。

在有向树中，结点的出现次序是没有意义的。但实际应用中，有时要给出同一级中结点的相对次序，这便导出有序树的概念。4、有序数：在根树中规定了每一层上结点的次序，称为有序树。为表示结点间的关系，有时借用家族中的术语。定义在以v0为根的树中，（1）v1，v2,…，vk称为v0的儿子，v0称为它们的父亲。vi，vj

同为一顶点v的儿子时，称它们为兄弟。（2）顶点间的父子关系的传递闭包称为顶点间的祖孙关系。即当vi为vi+1(i=1,2,…,l-1)的父亲时，v1是vl的祖先，vl为v1的子孙。（3）根树T自身及以它的树根的子孙为根的根树（T的子图），均称为T的子树（subtree），后者又称为T的真子树。5、m叉树

定义7-8.4：在根树中,若每个结点的出度均≤m，则称T为m元树(m叉树)，若每个分支点的出度恰好等于m，则称T为m叉完全树，若T的所有树叶的层数均相同，则称T正则m元树。若m元树是有序的，则称T为m元有序树，若m元完全树是有序的则称T为完全m元有序树，若m元正则树是有序的，则称T为m元正则有序树。当m=2时，称为二元树，二元有序树的每个结点至多有两个儿子，其序按左右分，分别为左儿子，右儿子，任一分支点最多有两棵子树，称为左子树和右子树。当m=2时，便可得到常用的二叉树、完全二叉树和正则二叉树。不难看出，二叉树中的每个结点v，至多有两个子树，分别称为v的左子树和右子树。若v只有一个子树，则称它为左子树或右子树均可。在二叉树的图形表示中，v的左子树画在v的左下方，v的右子树画在v的右下方。

6.定理7-8.1设有完全m叉树，其树叶的数目为t,分支数为i,则(m-1)×i=t-1。

7.定义7-8.5在根树中，一个结点的通路长度，就是从树根到该结点的通路中的边数。分支点的通路长度称为内部通路长度，树叶的通路长度称为外部通路长度。二、最优树二叉树的一个重要应用就是最优树问题。给定一组数w1，w2，…，wn。令一棵二叉树有n个叶结点，并对它们分别指派w1，w2，…，wn作为权，则该二叉树称为加权二叉树。

8.定理7-8.2设有完全二叉树有n个分支点，且内部通路长度为总和为I

，外部通路长度总和为E

，则

E=I+2n。

已知w1，w2，…，wn为权，T0为加权二叉树，其权为w(T0)，如果对任意加权二叉树T，它的权是w(T)，均有w(T0)≥w(T)，则称T0是最优树或Huffman树。

9.定义7-8.6在带权二叉树T中，若带权为wi树叶，其通路长度为L(wi),把

t

w(T)=

wi

L(wi)

i=1

称为该带权二叉树权，所有带权w1,w2,…,wt的二叉树树中，w(T)最小的那棵树，称为最优树。6-1格P243（7）（8）（9）（11）7.设a和b是格<A,≤>中的两个元素，证明

(1)a∧b=b当且仅当a∨b=a

(2)a∧b<b和a∧b<a当且仅当a与b是不可比较的证明：(1)在格中吸收律满足,则由a∧b=b,a∨b=a∨(a∧b)=a反之,若a∨b=a,则a∧b=

(a∨b)∧b=b(2)若a∧b<b和a∧b<a,即表明a∧b≠b和a∧b≠a,用反证法：假设a与b是可比较的,则a≤b，a∧b=a，矛盾;b≤a，a∧b=b，矛盾因此a与b是不可比较的。反之,a与b是不可比较的,则a≤b和b≤a均不成立,即a∧b≠b和a∧b≠a根据∧的定义：a∧b≤a

和a∧b≤b,故 a∧b<b和a∧b<a8.证明：在格中a≤b≤c,则

(1)a∨b=b∧c(2)(a∧b)∨(b∧c)=b=(a∨b)∧(a∨c)证明：(1)a≤b，a∨b=bb≤c,b∧c=b(2)在格中吸收律满足,(a∧b)∨(b∧c)=(a∧b)∨b=b(a∨b)∧(a∨c)=b∧c=b9.证明：在格中成立：

(1)(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)(2)(a∧b)∨(b∧c)∨(c∧a)≤(a∨b)∧(b∨c)∧(c∨a)证明:(1)因为a∧b≤a,c∧d≤c,故(a∧b)∨(c∧d)≤(a∨c)

因为a∧b≤b,c∧d≤d,故(a∧b)∨(c∧d)≤(b∨d)(2)a∧b≤a,b∧c≤b,c∧a≤a,故

(a∧b)∨(b∧c)∨(c∧a)≤a∨b同理：(a∧b)∨(b∧c)∨(c∧a)≤b∨c

(a∧b)∨(b∧c)∨(c∧a)≤c∨a故：得证11.设<A,≤>是格,证明<A,≤R>也是格。证明:(1)证明<A,≤>是一个偏序集对任意a,b,c∈A，a≤a

当且仅当a≤Ra,故满足≤R自反性若a≤Rb且b≤Ra,则有b≤a且a≤b,因≤满足反对称性,所以有a=b,故≤R满足反对称性若a≤Rb且b≤Rc,则b≤a且c≤b,故c≤a,即a≤Rc,故≤R满足传递性(2)对任意a,b∈A,因<A,≤>是格,故可设a,b的最小上界和最大下界分别是c和d,则有：a≤c

和b≤c,即c≤Ra和c≤Rb,因此c是a和b关于≤R的最大下界同理：d是a和b关于≤R的最小上界。格的定义：偏序集+最大下界+最小上界6-2分配格P249（5）（9）5.设<A,≤>是分配格,任意a,b∈A且a<b,证明：f(x)=(x∨a)∧b是从A到B的同态映射,其中B={x|x∈A且a≤x≤b}证明:任意x∈A,必有f(x)∈B因为a≤x∨a且a<b,故a=a∧b≤(x∨a)∧b≤b即a≤f(x)≤b,所以f(x)∈B,f是从A到B的一个映射任意x,y∈A,f(x∨y)=(x∨y∨a)∧b=(x∧b)∨(y∧b)∨(a∧b)f(x)∨f(y)=((x∨a)∧b)∨((y∨a)∧b)=((x∧b)∨(a∧b))∨((y∧b)∨(a∧b))=(x∧b)∨(y∧b)∨(a∧b)同理可证：f(x∧y)=f(x)∧f(y)故：f是从A到B的同态映射9.一个格<A,≤>是模格当且仅当

任意a,b,c∈A均有：a∨(b∧(a∨c))=(a∨b)∧(a∨c)证明:<A,≤>是格,且有上式成立,证<A,≤>是模格当a≤c时,有a∨c=c,故：a∨(b∧(a∨c))=a∨(b∧c)=(a∨b)∧(a∨c)=(a∨b)∧c所以<A,≤>是模格。(2)<A,≤>是模格,任意a,b,c∈A,当a≤c时,有a∨(b∧c)=(a∨b)∧c因为a≤c,故c=a∨c,所以a∨(b∧(a∨c))=(a∨b)∧(a∨c)6-3有补格P252（1）（6）1.答案证明:a和f都没有补元不是不是6.设<A,≤>是一个有界格，对于任意x,y∈A,证明：若x∨y=0,则有x=y=0若x∧y=1,则有x=y=1证明:若x∨y=0,由∨的定义知x≤0,y≤0,由于0为全下界,所以不可能有x<0和y<0，因此x=y=0若x∧y=1,由∧的定义知1≤x,1≤y,由于1为全上界,所以不可能有x>1和y>1，因此x=y=16-4布尔代数P260（1）（3）（4）（7）3.设<A,∨,∧,~>是一个布尔代数,若在A上定义二元运算⊕为：a⊕b=(a∧b)∨(a∧b)证明:<A，⊕>为一个Abel群。分析：Abel群的定义封闭性可结合性可交换性幺元逆元4.设<A,∨,∧,~>是一个布尔代数,在A上定义：a+b=(a∧b)∨(a∧b)a.b=a∧b证明:<A,+,.>是以1为幺元的环。分析：+即为(3)中的⊕运算,(3)已证明<A,+>为一个Abel群。由∧运算的封闭性和可结合性,<A,.>为半群.对+的分配律<A,.>的幺元为1:对任意a∈A,1.a=1∧a=aa.1=a∧1=17.设<K,∨,∧,~>和<L,∪,∩,->是两个布尔代数,并设f是从K到L的满同态,即对任意x,y∈K,有：f(x∧y)=f(x)∩f(y)f(x∨y)=f(x)∪f(y)f(x~)=f(x)--证f(0k)=0l,f(1k)=1l,这里0k,0l和1k,1l分别为相应的布尔代数的全上界和全下界。证明:因为f是从K到L的满射,故即对任意l∈L,必有k∈K,使得f(k)=l又因l∪f(0k)=f(k)∪f(0k)=f(k∨0k)=f(k)=ll∩

f(1k)=f(k)∩

f(1k)=f(k∧1k)=f(k)=l故有f(0k)≤l和l≤f(1k)由于l的任意性,所以f(0k)和f(1k)分别是L中的全下界和全上界，而布尔代数的全下界和全上界均是唯一的，因此，必有f(0k)=0l和f(1k)=1l,第7章习题课练习7-1（6）简单图的最大度小于结点数。证明：设简单图G中有n个结点。任取一个结点v，由已知G是简单图没有环和重边，v至多和n-1个结点相邻，也即deg(v)

≤n-1,而△(G)＝maxdeg(v)≤n-1,

因此最大度小于结点数。练习7-2（2）：若无向图G中恰有两个奇数度的结点，则这两个结点之间必有一条路。证明：设无向图G中两个奇数度的结点为u和v。从u开始构造一条迹，即从u出发经关联于结点u的边e1到达结点u1，若deg(u1)为偶数,则必可由u1再经关联于结点u1的边e2到达结点u2,如此继续下去,每边只取一次,直到另一个奇数度结点停止,由于图G中只有两个奇数度结点,故该结点或是u或是v。如果是v,那么从u到v的一条路就构造好了。如果仍是结点u,此路是闭迹。闭迹上每个结点都是关联偶数条边,而deg(u)为奇数,所以至少还有一条关联于结点u的边不在此闭迹上。继续从u出发,沿着该边到达另一个结点u1’,依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v,这就是一条从u到v的路。练习7-2（3）：

若图G是不连通的，则G的补图G是连通的。

证明：若G=<V,E>是不连通的，可设图G的连通分支为G[V1],G[V2],……,G[Vm](m≥2)。由于任意两个连通分支G[Vi],G[Vj]不连通，因此Vi与Vj之间的连线在补图中，在G中任取两个结点u和v，则u和v的位置有两种情况：1)若u和v均在同一个连通分支G[Vi]中,根据上面的分析，可在另一个连通分支G[Vj]（i≠j)中取一个结点w，使得u与w，v与w在G中连通，故有u－w－v，即u与v在G中连通2)若u与v分别属于两个不同的连通分支G[Vi]与G[Vj]，由上面的分析可知，u与v在G中连通。故当图G不连通时，则补图G是连通的7-2（4）:当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。证明：必要性。（e是G的割边）设e是连通图G的割边，e关联的两个结点是u和v。如果e包含在G的一个回路中，那么除边e=(u,v)外还有另一条分别以u和v为端点的路，所以删去边e后，G仍为连通图，这与e是割边相矛盾。充分性。如果边e不包含在G的任一条回路中，那么连接结点u和v的边只有e，而不会有其它连接u和v的任何路。因为如果连接u和v还有不同于边e的路，此路与边e就组成一条包含边e的回路，从而导致矛盾。所以删去边e后，u和v就不连通，故边e是割边。300页（2）如果u可达v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为u和v之间的距离（或短程线），记作d<u,v>，如果从u到v是不可达的，则通常写成d<u,v>=∞距离矩阵为

0121∞011∞1

01∞120dij=1表示存在边<vi,vj>。300页（3）用Warshall算法求可达性矩阵。邻接矩阵为

000001

01101

00000

010000000A=i=1时，因为A的第一行全为0，所以A不变。i=2时，因为A的第2列全为0，所以A不变。i=3时，因为A[2，3]=A[4，3]=1，将第3行加到第2行和第4行。000001

01101

00001

010000000A=i=4时，因为A[4,2]=1，将第四行加到第2行，A不变。i=5时，因为A的第5列全为0，所以A不变。000001

01101

00001

010000000P=故A的可达性矩阵为：距离矩阵为

0∞

∞

∞

∞1011∞1∞0∞∞2∞10∞∞∞∞∞0300页（4）：写出如图7-3.11所示的图G的完全关联矩阵，并验证其秩如定理7-3.2所述。e1e2e3e4e5e6e7e8e9A100001010B011000100C000110010D110000001E000011100F001100001完全关联矩阵为:此图为连通图，由定理7-3.2，其秩为5。311页（2）构造一个欧拉图，其结点数v和边数e满足下述条件a)v，e的奇偶性一样。b)v，e的奇偶性相反。

如果不可能，说明原因。v=3,e=3v=5,e=5v=4,e=4v=4,e=6v=7,e=8v=6,e=7

无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点度数全为偶数。下面的图中所有结点度数全为偶数，所以都是欧拉图。311页（6）a)画一个有一条欧拉回路和一条汉密尔顿回路的图。在无孤立结点图G中，经过图中每条边一次且仅有一次的一条回路，称为欧拉回路。

给定图G，经过图中每个结点恰好一次的回路称作汉密尔顿回路。b)画一个有一条欧