第七章图论第一节图的基本概念定义一个图是一

第七章图论第一节.图的基本概念一个图是一个三元组<V(G),E(G),φG>,其中V(G)是一个非空的结点集合,E(G)是边集合,φG是从边集合到结点无序偶(有序偶)集合上的映射.注:1)图也可简记为G=<V,E>,这里V是结点集,E是边集.2)图可以用一个具体的图形来表示,也可以用一个抽象的三元组来表示.例.用三元组给出图G=<V(G),E(G),φG>如下:V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6}φG(e1)=(a,b),φG(e2)=(a,c),φG(e3)=(b,d),φG(e4)=(b,c),φG(e5)=(d,c),φG(e6)=(a,d).它的图形如下图(a)或(b)所示:aabdbdcc(a)(b)定义:1)无序偶和有序偶;无向边和有向边;2)有向图;无向图;混合图.注:今后我们不讨论混合图,而只讨论有向图和无向图.下图中的(a)和(b)分别是有向图和混合图的例子:(a)(b)定义:邻接点:由一条有向或无向边连接的两个结点.邻接边:连接同一结点的两条边.孤立结点:不与任何结点相邻接的结点.自回路(环):连接同一结点的边.零图:仅有若干个孤立结点而没有边的图.平凡图:仅有一个孤立结点的图.注:环既可以看作是有向边,也可以看作是无向边.定义7-1.2(结点的度数deg(v))与结点v关联的边数称为该结点的度数,记为deg(v).定义:图的最大度Δ(G)和最小度δ(G).定理7-1.1每个图中,所有结点的度数之和恰好等于该图的边数的两倍,即有

∑deg(v)=2|E|.利用这一定理以及奇数和偶数的基本性质,不难证明下面有用的结果:定理7-1.2在任何图中,度数为奇数的结点个数必为偶数.定义7-1.3(有向图中结点的出度deg+(v)和入度

deg-(v))显然,在任何有向图中,对任一结点v都有

deg+(v)+deg-(v)=deg(v).定理7-1.3在任何有向图中,所有结点的入度之和必等于它们的出度之和.证明:因为有向图中的每一条有向边都恰好对应和恰好等于有向边的总数.同样地,所有结此它们相等.定义7-1.4(平行边,多重图,简单图)平行边:连接同一对结点如有多于一条边,则称该图有平行边.多重图:有平行边的图.简单图:没有平行边,也没有环的图.定义7-1.5(完全图)每对结点间都恰有一条边相连的图称为完全图.有n个结点的完全图记为

Kn.

n个结点的无向完全图Kn的边数为|E|=(1/2)n(n-1).证明:根据完全图的定义,它的任意两个结点间都恰好有一条边相连,而从个结点中任取两点的所有组合数等于=(1/2)n(n-1).

这正是我们所要证明的.定义7-1.6(相对完全图的补图)给定简单图G,由G中所有结点和所有能使G成为完全图的添加边组成的图称为G的相对于完全图的补图,或简称为G的补图,记为.例如下面两图互为补图.定义7-1.7(子图,生成子图)给定图G=<V,E>,如果有图G’=<V’,E’>,使得E’E,V’

V,则称G’是G的子图.如果子图G’还包含G的所有结点,则子图G’称为G的生成子图.定义(相对于一个图的补图)设图G’=<V’,E’>是图G=<V,E>,的子图.若对另外一个图G’’=<V’’,E’’>有E’’=E-E’,且V’’中仅包含E’’G’’是的子图G’关于图G的补图.例如:下图中(b)和(c)都是(a)的子图;(c)是(b)相对于(a)的补图,但(b)不是(c)相对于(a)的补图.(a)(b)(c)

例:下图中,(b)和(c)都是(a)的子图,且它们都是(a)的生成子图;又(b)是(c)的相对于(a)的补图,且(c)也是(b)的相对于(a)的补图.此外,(b)还和(c)互为关于完全图(这里的完全图指的是K4)的补图.(a)K4(b)(c)

定义7-1.9(图的同构)假设给定两个图G=<V,E>和G’=<V’,E’>,如果存在它们的结点集V与V’之间的一个一一映射g:使得(或者)是G的一条边,当且仅当(或者)是G’的一条边,则称图G与图G’是两个同构的图,记为GG’.容易看出，同构的图有如下一些性质：1）结点数目相同；2）边数相等；3）度数相同的结点个数相等。但要注意的是：以上三个条件仅仅是两个图同构的必要条件，而非充分条件。例子：1）下面两个无向图是同构的。2）下面两个有向图也是同构的。3)下面两个图中虽然结点个数、边数以及度数相同的结点个数都相同,但是它们并不是同构的图.第二节.路,回路与连通性定义7-2.1(路,迹,通路和圈)给定图G=<V,E>,设v0,v1,…,vnV,e1,e2,…,enE,其中ei是关联于结点vi-1和vi的边,我们把由结点和边组成的交替序列

v0e1v1e2…envn

称为是从点v0到点vn的一条路.这条路中边的条数称为这条路的长度.当v0=vn时,称这条路为一条回路.若一条路中所有的边均不相同,称之为迹.若这条路中所有的结点均不相同,称之为通路.当v0=vn而其余结点均不相同时,称之为圈.例子.在下面的图中找出一条路,一条迹,一条通路和一个圈来.v1e1e2

e3v2v3e4e5e6e7v4e8v5n个结点的图中,如果从结点vj到结点vk存在一条路,那么从结点vj到结点vk必存在一条边数至多为n-1的路.推论.在一个有n个结点的图中,如果从结点vj到结点vk存在一条路,那么从结点vj到结点vk必存在一条边数至多为n-1的通路.定义7-2.2(点的连通性)设G为无向图,若在结点vj与结点vk之间存在一条,路则称结点vj与结点vk是连通的.注：不难证明，结点之间的连通性是结点集合V上的一个等价关系，即它满足自反性，对称性和传递性。由此可以根据结点之间有无连通性来将结点集合进行分类：把凡是连通的结点放在同一个类中。这样得到的每个类中的所有结点和相应的边作成的子图称为是原图的一个连通分支。图G的连通分支的个数记为W(G)。例如，下面的图有三个连通分支，即W(G)=3。定义7-2.3(连通图)若图G只有一个连通分支,即有W(G)=1,则称它是一个连通图.定义7-2.4(点割集,割点)设无向图G=<V,E>为一连通图,若有点集V1V,使得在图中删去了点集V1中所有的结点后,去点集V1的任一真子集后,得到的子图仍是连通图.则称点集V1是图G的一个点割集.若点割集中恰只有一个结点,则称它是该图的一个割点.定义7-2.5(边割集,割边)设无向图G=<V,E>为一连通图,若有边集E1E,使得在图中删去了边集E1中所有的边后,中删去边集E11是图G的一个边割集.若边割集中恰只有一条边,则称它是该图的一个割边,也称为一个桥.定义(点连通度)设G是一个图，则定义

k(G)=min{|V1|:V1是G的点割集}为图的点连通度(或连通度).Kp来说,显然有k(Kp)=p-1.定义(边连通度)设G是一个图，则定义

λ(G)=min{|E1|:E1是G的边割集}为图的边连通度.对于平凡图，也即仅由一个孤立结点作成的图G,可以规定有λ(G)=0.此外,对于任何不连通的图G,也有λ(G)=0.定理7-2.2对任何一个图G有

k(G)≤λ(G)≤δ(G),这里k(G)是点连通度,λ(G)是边连通度,而δ(G)是图的最小度.证明1）根据图的最小度以及边连通度的定义易见,不等式λ(G)≤δ(G)总是成立的.2)下面来证明不等式k(G)≤λ(G).情形一.若λ(G)=1,也即图G有一条割边,此时显然也有k(G)=1(因为只要把这条割边的任一个端点删去,该图就一定成为不连通图了),故结论已成立.情形二.若λ(G)≥2,则可从图中删去某λ(G)条边,使之不连通;然而若从那λ(G)条边中删去λ(G)-1条边,得到的图仍是连通的,且在这样得到的子图中恰有一个桥e=(u,v).对于那λ(G)-1条边中的每一条边,都选取一个不同于u和v的结点,把这些结点全部删去,就至少删掉了图中的λ(G)-1条边.如果这样得到的图是不连通图,就有k(G)≤λ(G)-1<λ(G);如果这样得到的图仍是连通图,则e仍然是桥,这时再删去结点u或者v,就必然得到一个不连通的图,故有k(G)≤λ(G).这就完成了我们的证明.(注)下面的图中容易看出有k(G)=2，λ(G)=3，δ(G)=4，

这对定理7-2.2的结论也给出一个例证.G中的结点v是图G的割点的充分必要条件是:存在两个结点u和w,使得连接结点u和w的每一条路都通过结点v.v是图GG中删去该点就得到一个不连通的图F,于是F至少有两个连通分支F1和F2,分别从F1和F2中各任取一点u和w,由于原图G是连通的,而在去掉割点v后得到的图F中它们不再连通,这就表明在图G中连接这两个结点的任一条路必定都经过结点v.

2)u和w,使得连接结点u和w的每一条路都通过结点v.那么显然,只要去掉结点v,u和w这两个结点就会变成不连通的,从而图G也v必为图的割点.注意:1)无向图的连通性不能直接推广到有向图.2)在有向图中可以定义可达性如下:如果从结点u到结点v有一条(有向的)路相通,则称从点u到点v可达.注意,结点间的可达性是自反的和传递的,但一般不是对称的.3)如果在一个有向图中从点u到点v可达,则称从点u到点v的所有(有向的)路中最短的那条路的长度为结点u到v的距离,记为d<u,v>.

如果从结点u到v不可达,则记d<u,v>=∞.

注意,当从点u到点v可达时,从点v到点u不一定也可达;即使从点v到点u也可达,一般也不一定有d<u,v>=d<v,u>.定义(无向图的直径)设G=<V,E>是一个无向图,称

D=max{d<u,v>,u,v

V}为图G的直径.

第三节.图的矩阵表示定义7-3.1(图的邻接矩阵)设G=<V,E>是一个简单图(即没有平行边和环的图),它有n个结点

V={v1,v2,...,vn},我们称n阶方阵A(G)=(aij)为G的邻接矩阵,这里aij=1(当vi邻接vj时),aij=0(当vi不邻接vj时).例子.下图(a)的邻接矩阵如(b)所示.

v1

v2

v5A(G)=

v3

v4(a)(b)注:1)无向图的邻接矩阵必为对称阵;而有向图的邻接矩阵一般不一定是对称阵;显然,一个图为零图(全由孤立结点构成的图)的充分必要条件是它的邻接矩阵必为零阵.2)有向图(无向图)中邻接矩阵中第i行元素之和恰为结点vi的出度(度).3)图的邻接矩阵一般说来与结点的书写次序有关.4)给定两个同阶矩阵,如果能通过对其中任一矩阵的某些行作次序调换,同时对相应的列作同样的调换,就可将它变成另一个矩阵,就称这两个矩阵是彼此

置换等价的矩阵.显然,从同一个图作出的任意两个邻接矩阵一定是置换等价的矩阵.问题:怎样计算图中从一个结点vi到另一个结点

vj的长度为k的路的条数?G和它的邻接矩阵A(G),用矩阵乘法计算出邻接矩阵A(G)的k次幂Ak(G),则矩阵Ak(G)中第I行第j列元素bij的值即为图G中从结点vi到结点vj的长度为k的路的条数.G(见下图(a)),要求其中(1)从结点v1到结点v2的长度为3的路的条数;(2)从结点v2到结点v2的长度为3以及长度为4的回路的条数.解:容易算出此图的邻接矩阵A如(b)所示.

v5

v1

v2A=

v4(a)v3(b)计算给出A2=A3=A4=结论:(1)从结点v1到结点v2有2条长度为3的路.(2)从结点v2到结点v2没有长度为3的回路.(3)从结点v2到结点v2有4条长度为4的回路.定义7-3.2(有向图的可达性矩阵)令G是一个简单有向图,其结点数为|V|=n,并设已将图的所有结点进行了编序:V={v1,v2,...,vn}.则称如下定义的n阶方阵P=(pij)为图G的可达性矩阵,这里pij=1(如果从到至少有一条路)或者pij=0(如果从到不存在路).注:可达性矩阵的概念也容易推广到无向图中,只要在无向图中将每条无向边改成两条有向边就行了.问题:怎样从图的邻接矩阵求出其可达矩阵呢?解答:设n阶矩阵A是图G的邻接矩阵,用矩阵乘法依次算出A2,A3,...,An,然后计算出矩阵B=A+A2+A3+...+An,再在矩阵B中将所有的非零元素都换成数1;而B中为零的元素仍保持数零不动,这样得到的矩阵K就是图G的可达性矩阵.G的邻接矩阵是

A=求出它的可达性矩阵来.解:计算给出A2=A3=A4=B=++

+=

第四节.欧拉图与哈密尔顿图欧拉(L.Euler)与哥尼斯堡(K

nigberg)七桥问题

CABDCABD定义7-4.1(欧拉路与欧拉回路)设图G无孤立结点,若G中存在一条路,它经过图G中每条边一次且只经过一次,则称这条路为一条欧拉路;如果它还是一条回路,则称它为一条欧拉回路.我们称有欧拉回路存在的图是一个欧拉图.(注)我们不讨论有孤立点的图中有无欧拉路或欧拉回路存在的问题.定理7-4.1设G是一个无孤立结点的无向图,那么G中存在一条欧拉路,当且仅当G是连通的,且恰有零个或两个奇数度结点.例子(哥尼斯堡七桥问题).由于该图中有4个奇结点,从而该图中必不存在欧拉路或欧拉回路.有关一笔画与多笔画问题的结论:(1)无孤立结点的无向图G是一个一笔画的充分必要条件是:它是一个连通图,且奇结点的个为0或为2.(2)设G是一个连通无向图,它有2n个(n>1)奇结点.那么图G必是一个n笔画,且最少是一个n笔画.欧拉路及欧拉回路的概念在有向图中的推广:定义7-4.2(单向欧拉路与单向欧拉回路)设G是一个有向图,如果G中存在一条有向路(有向回路),它经过图中每条有向边恰好一次,则称它为一条单向欧拉路(单向欧拉回路).G是一个有向图.(1)G中存在一条单向欧拉路的充分必要条件是:

G是连通图,且除去两个结点外,其余每个结点的入度等于出度;在剩下的两个结点中,一个结点的入度比出度大1,另一个结点的入度则比出度小1.(2)G中存在一条单向欧拉回路的充分必要条件是:G是连通图,且每个结点的入度等于出度.

定义7-4.3(哈密尔顿路与哈密尔顿回路)设G是一个图,若G中存在一条路(回路),它经过图中每个结点恰好一次(在回路的情形,起始点允许重复),则称它是一条哈密尔顿路(回路).我们称有哈密尔顿回路存在的图是一个哈密尔顿图.定理7-4.3(一个图有哈密尔顿回路的必要条件)若图G=<V,E>有哈密尔顿回路,则对结点集V的每个非空子集S均有不等式

W(G-S)≤|S|成立,其中W(G-S)表示子图G-S中的连通分支的个数.(证明略)例子.(1)用定理7-4.3可证下图不是一个哈密尔顿图.必要条件,而非充分条件.右图(Petersen图)就但并非哈密尔顿图的例子.定理7-4.4(一个图有哈密尔顿路的充分条件)设G是一个有nG中每一对结点的度数之和都大于或等于n-1,则G中存在一条哈密尔顿路.(证明略)注意:此定理仅是充分条件而非必要条件,例如右图显然是一个哈密尔顿图,当然它的任一对结点度数之和都小于该图的结点总数.例子.证明下图中不存在哈密尔顿路.

ABBBAAAABBABAAAB

定理7-4.5(一个图有哈密尔顿路的充分条件)设G是一个有nG中每一对结点的度数之和都大于或等于n,则G中存在一条哈密尔顿回路.(证明略)附:哈密尔顿的周游世界问题(1859年)2151161432041713191812511961087第五节.平面图定义7-5.1(平面图)设G是一个无向图,如果能够把G的所有结点和边画在平面上,使得任何两条边除是一个平面图.以下我们仅研究连通的平面图.例子.下图(a)可以重新画成(b)的样子,所以图(a)仍是平面图.(a)(b)定义7-5.2(连通平面图的面,面的边界)设G是一个G中的边所包围的区域称为图G的一个面(每个图也包含一个无限的、位于图的外部的面),而包围该面的各个边就构成这个面的边界.r5划分成5个面:r1,r2,r3,r4和一个无限的C面r5.其中的三个面r1,r2和r4的边界均A

r4由一条回路组成,面r3的边界虽然并不Br2FE是一条回路,但如果按照下面的方式r1r3走完它的边界:CDEFEC(或顺时针走D也可),那么它的边界也作成一条回路.今后我们对面的边界就规定为用这样的方式定义的一条回路.定义(平面图中面的次数)设G是一个连通的平面图,按照上述约定,它把整个平面分成的每个面ri的边界都是一条回路.称该回路的长度为这个面的次数,记为deg(ri).例如,在上面那个平面图中有deg(r1)=3,deg(r2)=3,deg(r3)=5,deg(r4)=4,deg(r5)=3.定理7-5.1设G是一个有限平面图,则它的所有面的次数之和等于边数的两倍.定理7-5.2设G是一个非平凡的有限连通平面图,它有v个结点,e条边和r个面,则有下述欧拉公式成立:v-e+r=2.证明(对图的边数用归纳法):(1)若G只有一条边,则v=2,e=1,r=1,结论显然成立.(2)(归纳假设)设当G有k条边时结论成立:

vk-ek+rk=2.(1)(3)现在设G有kk条边的连通图G1中添加一条边,使之仍为连通图(G1中的结点数、边数与面数满足(1)式).这只能有以下两种情况:1)在G1中增加一个新结点

,使之与G1中某个结点

相连.此时有vk+1=vk+1,ek+1=ek+1,rk+1=rk,于是欧拉公式

vk+1-ek+1+rk+1=2仍然成立.2)将G1中某两个结点与

vk+1=vk,ek+1=ek+1,rk+1=rk(此处证明细节略去),于是此时欧拉公式vk+1-ek+1+rk+1=2仍然成立.

定理7-5.3设G是一个有v个结点和e条边的简单v≥3,则有e≤3v-6.证明:设G有r个面.(1)若v≥3,e≤3,则结论显然成立.(2)若v≥3,e≥4,一方面:G的所有面的次数之和等于2e,另一方面,由于它是简单图,故每个面的次数至少为3,从而又有2e≥3r,即r≤(2/3)e.将此不等式代入欧拉公式即得2=v-e+r≤v-e+(2/3)e2≤v-(1/3)e6≤3v-e

e≤3v-6.

例子.(1)证明K5不是平面图.解:在K5中有v=5个结点,e=10条边,因而对它有e=10>9=3v-6,根据定理7-5.3,它不是平面图.

K5vk-ek+rk=2.A=5(完全图)每对结点间都恰有一条边相连(5)T连通,但删去任何一条边后便不连通;证明:设给定一棵二叉树.7(前缀码)给定一个序列的集合,若其中个面F1,F2,…,Fn,若有另外一个图G*=<V*,E*>满足v4(a)v3(b)G的所有结点和边画在平面上,使得任何两条边除它们是在二度结点内同构的图.对于平凡图，也即仅由一个孤立结点作成的图G,可以规定有λ(G)=0.e1,e2,…,ei的边ei+1,使{e1,e2,…,ei,ei+1}中无此外,对于任何不连通的图G,也有λ(G)=0.1)因为T是连通图,故它的任意两个结点间必有一条路.(1)证明K5不是平面图.其EMEM(2)证明K3,3不是平面图.解:在K3,3中有v=6个结点,e=9条边,因而对它有e=9<12=3v-6,.注意K3,3中2e≥4r

e≥2r

2=v-e+r≤v-e+(1/2)e

e≤2v-4,

然而实际上有

e=9>8=2v-4,

故它不是平面图.

K3,3

定义7-5.3(在二度结点内同构的图)设G1和G2是两个图,如果它们同构,或者通过反复(有限次)插入或除去度数为2的结点后,能成为同构的图,则称它们是在二度结点内同构的图.插入和除去二度结点的简单例子:→→(a)(b)

定理7-5.4(Kuratowski定理)一个图是平面图,当且仅当它不包含与K3,3或K5在2度结点内同构的子图.(证明略)第六节.对偶图与着色定义7-6.1(对偶图)给定平面图G=<V,E>,设它有n个面F1,F2,…,Fn,若有另外一个图G*=<V*,E*>满足如下三条件,则称图G*是图G的对偶图:(a)对图G的每个面,G的内部有且仅有一个结点

v*i

G*.(b)对于图G中任意两个面Fi和Fj之间的每一条公共边界ek,都存在一条边e*k

G*,使得e*k=(v*i,

v*j),且e*k和ek相交.(c)当且仅当单独一条边ek构成图G的某一个面Fi

的边界时,(b)中与ek对应的边e*k=(v*i,v*i)是一个环,且e*k和ek相交.(注)显然,若图G*是图G的对偶图,那么图G也是图G*的对偶图,从而它们必是互为对偶的图.对偶图的简单例子:下图中实线和虚线作成的两个图是互为对偶的图.(注)若图G*与图G是互为对偶的图,那么,只要两个图中有一个图是连通的平面图,另一个图必也是连通的平面图.定义(自对偶图)若图G的对偶图恰与G同构,则称图G是一个自对偶图.例子.由右图容易看出,完全图K4就是一个自对偶图.(1)四色定理的历史简介:

1)FrancisGuthrie(~1899,后成为位于开普顿的南非大学数学教授):1850年前后提出四色猜想.2)AugustusdeMorgan1852年10月23日给WilliamR.Hamilton爵士的信提出四色猜想.3)A.Cayley先后于1878年6月13日和1879年在伦敦数学会的会议上以及英国皇家地理协会会报上两次重新提出这一问题.4)A.B.Kempe和G.Tait于1879年给出第一个证明.5)P.J.Heawood于1890年指出了他们证明中的错误.6)K.Appel,W.Haken和J.Koch于1976年用计算机给出完全的证明(发表的两篇论文长达139页,在Illinois

大学的计算机上共花去1200小时的计算机时间).地图的着色问题与对偶图的着色问题之间的联系:(1)将地图的着色问题转化成对偶图的着色问题.(2)对偶图的正常着色问题.定义(图的正常着色)设G是一个图,对它的每个结点指定一种颜色,使得没有两个邻接的结点能有相同的颜色,这样的着色就称为是图G的一种正常的着色.定义(n色图和图的着色数)如果图G在正常着色时用到n种不同的颜色,则称该图是一个n-色的图;对图G进行正常着色所需的最少的颜色数称为图G的着色数,记为χ(G).定理7-6.1对有n个结点的完全图Kn,有χ(Kn)=n.定理7-6.3(五色定理)对任何平面图G,有χ(G)≤5.(证明略)第七节.树与生成树(树与森林)(1)一个连通且无回路的无向图称为树.(2)树中度数1为的结点称为树叶.(3)树中度数大于的结点称为分枝点或内点.(4)一个无回路的无向图称为森林.显然,森林的每个连通分支都是一棵树.森林和树的例子:定理7-7.1给定图T,则以下关于树的定义等价:(1)T无回路且为连通图;(2)T无回路且e=v-1,其中e是边数,v是结点数;(3)T连通且e=v-1;(4)T无回路,但如果任意增加一条新的边,便得到一条且恰只得到一条回路;(5)T连通,但删去任何一条边后便不连通;(6)T的每一对结点之间有唯一一条路.证明:(1)

(2)(对结点数v≥2用归纳法.)设T无回路且为连通图,要证明T无回路且e=v-1.1)如果v=2,由于T无回路且连通,故必有e=1

e=v-1.2)设结论对有k-1个结点的无回路连通图已经成立.3)设图T有v=k个结点,它连通且无回路.故它至少有一条边e1=(u,w)的一个端点u度数为1(否则图T中就存在一个结点度数均为偶数的子图T1,T1中必存在一条欧拉回路,即图T中存在一条回路,这是不可能的).从图T中去掉结点u(边e1=(u,w)也就同时被去掉,但其它的边不受影响),就得到一个有v*=k-1个结点的无回路的连通图T*.由归纳假设,在图T*中有e*=v*-1=k-2.最后再将结点u和它关联的边e1=(u,w)添加到图T*中去就得到图

T,于是在图T中有v=v*+1=k和e=e*+1=k-1=v-1,从而结论对有k个结点的树依然成立.w

u证明:(2)

(3)设T无回路且e=v-1,要证明T连通且e=v-1.用反证法.若T不连通,设它有k≥2个分支

T1,T2,…,Tk,因为每个分支都是无回路的连通图,若设Ti有vi个结点和ei条边,则由上证知ei=vi-1,从而对图T有

e=e1+e2+...+ek=(v1-1)+(v2-1)+…+(vk-1)=(v1+v2+…+vk)-k=v-k<v-1,矛盾.证明:(3)

(4)(对结点数v≥2用归纳法.)设T连通且e=v-1,要证明T无回路,但如果任意增加一条新的边,便得到一条且恰只得到一条回路.1)当v=2时,e=1,故必无回路;且如增加一边,恰好得到一条回路.2)设对有k-1个结点的图结论已成立.3)设连通图T=<V,E>有v=k个结点且边数为e=v-1=k-1.

∵T连通

uV,deg(u)≥1.现证

u0V,deg(u0)=1.

uV,deg(u)≥22e=∑deg(v)≥2v,与条件

e=v-1u0及与它关联的那条边得到图T*,

显然图T*是连通图且满足e*=v*-1,由归纳假设,T*无回路,向T*中加入u0及与它关联的那条边得到图T,故T也必无回路.现在向T中任意增加一条新的边(ui,uj),这条边与图T中连接结点ui和uj的路(因为T连通,此路必存在)合起来作成一条回路,且T中必定也只有这一条回路.否则的话,在这条回路中将新加的这条边(ui,uj)去掉,就会在图T*中也得到一条回路,这与归纳假设矛盾,因而是不可能的.证毕.证明:(4)

(5)设T无回路,但如果任意增加一条新的边,便得到一条且恰只得到一条回路,要证明T连通,但删去任意一条边后便不连通.1)反证.若不连通,则必存在结点ui和uj,它们之间没有路.向图中添加新的边(ui,uj),将不会产生回路,这与条件矛盾.2)另一方面,在图中任取一条边ei,则必存在至少两个结点ui和uj,它们之间恰有一条经过这条边的路(但它们之间没有回路,因为T中无回路),于是去掉这条边后,图就变成不连通图(因为去掉这条边后,结点ui和uj变得不再连通).证毕.证明:(5)

(6)设T连通,但删去任意一条边后便不连通,要证明T的每一对结点之间有一条且仅有一条路.1)因为T是连通图,故它的任意两个结点间必有一条路.2)下面用反证法来证明他们之间只有唯一一条路.否则的话,它们之间必存在一条回路,于是从刚才选取的那条路中任意删去一条边后,这两个结点之间因为仍有一条路,所以这两个结点仍然是连通的.也就是说,从T中删去任意一条边后,仍然得到一个连通图.这显然与条件矛盾.证明:(6)

(1)设T的每一对结点之间有一条且仅有一条路,要证明T无回路且为连通图.由条件可见结论显然成立.定理7-7.2任一棵树中至少有两片树叶.证明:1)设T=<V,E>是树,|V|=v.因为T是连通图,

vi

T有deg(vi)≥∑deg(vi)=2(|V|-1)=2v-2(*).若图中每个结点度数都≥2,则∑deg(vi)≥2v明了T中至少有一片树叶.2)下面来证T中至少有两片树叶.用反证法.如果只有一个结点度数为1,其它结点度数均2,则有∑deg(vi)≥2(v-1)+1=2v-1,这也与上面的结论(*)矛盾.定义7-7.2(生成树)若图T是图G的生成子图,且T是一棵树,则称T是图G的生成树.(注:我们称T是G的生成子图,是说T是G的子图,且T与G有相同的结点集合)生成树T中的边称为树枝,图G的不在生成树T中的边称为弦,所有弦的集合称为生成树的补.树,其中e1,e2,e4,e5,e7是T的树枝,e3,e6,e8是T的弦,{e3,e6,e8}是T的补.

e1e2

e6e7e3e5e4e8.证明:1)如果连通图G没有回路,那么它本身已经是自己的生成树了.2)如果图G至少有一条回路,从该回路中任意删去一条边,得到的图G1仍是连通图,且G1与图G有同G1不再有回路了,它就是图G的一个生成树;如果不然,可以再次重复上述步骤,直到得到与图G既有相同的结点集,又是无回路的连通子图Gk为止,这个子图就是原图的生成树.(注)由证明可见:一般来说,一个图的生成树不是唯一的.例子.1)2)(注)设G是一个有n个结点m条边的连通图,它的生成树有n-1G中删去m-(n-1)m-n+1称为图G的秩.定理7-7.4图G的一条回路和图G的任意一棵生成树T的补至少有一条公共边.补的定义知:如果图G的一条回路和图G的一棵生成树T的补没有公共边,这就表明这条回路完全含在这棵生成树之中.然而,生成树中不可能有回路,这就导出了矛盾.定理7-7.5图G的一个边割集和图G的任意一棵生成树T至少有一条公共边.证明:用反证法.如果图G的一个边割集S和图G的一棵生成树T没有公共边,那么从G中删去边割集S后得到的子图必包含该生成树,这就表明从G中删去此边割集后仍然得到一个连通图,矛盾.定义(带权的图)设G是有n个结点的连通图,对其每一条边e指定一个正数C(e),称之为边e的权(权可以表示长度,运输量,费用等等).G的生成树T的所有边的权的和称为这棵树T的树权.定义7-7.3(最小生成树)图G的所有的生成树中,树权最小的那棵树称为是G的最小生成树.定理7-7.6(Kruskal算法)设图G有n法产生的是图G的最小生成树.1)选取最小权边e1,置i←1;2)当i=n-1时结束,否则转到步骤3);3)设已选取好边e1,e2,…,ei,在G中再选取不同于

e1,e2,…,ei的边ei+1,使{e1,e2,…,ei,ei+1}中无回路且ei+1是满足此条件的权最小的边;4)i←i+1,转到步骤2).事实上对图中有若干条边的权相同的情形,只要将它们的权作微小的变动,使之各不相同,即可使用这个算法.计算最小生成树的实例:1116932781045红

绿

粉红

紫

蓝5图G的一个边割集和图G的任意一棵生+ek=(v1-1)+(v2-1)+…+(vk-1)该点就得到一个不连通的图F,于是F至少有两个连通分支F1和F2,分别从F1和F2中各任取一点u和w,由于原图GG中的边所包围的区域称为图G结点u和w的每一条路都通过结点v.V(G)={a,b,c,d},(注)若图G*与图G是互为对偶的图,那么,只要两个二叉树的应用之一:最优树问题.明了T中至少有一片树叶.T1,则有w(T1)-w(T)=2)另一方面,在图中任取一条边ei,则必存在至少两个结删去此边割集后仍然得到一个连通图,矛盾.ceBBB因此L(w1)=L(w2)=L(wx)=L(wy).<V(G),E(G),φG>,第八节.根树及其应用定义7-8.1(有向树)设G是一个有向树.定义7-8.2(根树)设G个结点的入度为0,而其余结点的入度都为1,则称它是一个根树.入度为0的结点称为根,出度为0的结点称为叶,出度不为0的结点称为分枝点或内点.根树的例子:v1右图中是一棵根树.其中v1是它的根,v2v3v4v1,v2,v4,v8和v9为它的分枝点,其余v5v6v7v8v9了根以外,这棵根树有三个结点v2,v3和v10v11v12v4的层次为1,有五个结点v5,v6,v7,v8和v9的层次为2,还有三个结点v10,v11和v12的层次为3.定义(父亲、儿子、兄弟、祖先和后裔)设a是一棵树Ta到b有一条边,则称结点b是结点a的“儿子”,或称结点a是结点b的“父亲”;假如从a到c有一条单向通路,则称a是c的“祖先”,或称c是a的“后裔”;同一个分枝点的多个儿子称为“兄弟”.定义7-8.4(m叉树、完全m叉树、正则m叉树、二叉树)在根树中,如果每个结点的出度至多为m,则称之为m叉树.如果根树中每个结点的出度要么等于m,要么等于零,则称这棵树为完全m叉树.若一棵根树所有树叶的层次都相同,则称之为正则m叉树.特别当m=2时,m叉树又称为二叉树.用叉树表示实际问题举例:

EMM、E两人之间采EMEM用连胜两盘或总共EMEM胜三盘者取胜的赛制进行网球比赛.其EMEM中出现的各种可能情形可用右图的二叉EMEM树表示(E表示E胜,M表示M胜),比赛所有可能结果如下示:MM,MEMM,MEMEM,MEMEE,MEE,EMM,EMEMM,EMEME,EMEE,EE.或者pij=0(如果从到不存在路).必存在一条边数至多为n-1的路.因为T2是带权w1+w2,w3,…,wt的最优树,故有给定图G=<V,E>,设v0,v1,…,vnV,e1,e2,…,enE,其中ei是关联于结点vi-1和vi的边,我们把由结点和边组成的交替序列图中有一个图是连通的平面图,另一个图必也是连通的平面图.行第j列元素bij的值即为图G中从结点vi到结点vj的长D=max{d<u,v>,u,vV}问题:怎样计算图中从一个结点vi到另一个结点孤立结点:不与任何结点相邻接的结点.G’=<V’,E’>,如果存在它们的结点集V与V’之2)如果被译码的信息的最后部分不能成为前缀码定义(带权二叉树)设T是一棵二叉树,它有t片树叶,将任意一棵有序树改写成二叉树的方法:(1)从每个结点分出的分枝中,只保留最左边的那个分枝与该结点的连线,其余分枝与该上层结点的连线均被删除.(2)位于同一层次的所有兄弟结点均改用从左到右的有向边加以连接.(3)如下法选定二叉树的左儿子和右儿子:直接位于给定结点下方的结点作为其上方结点的左儿子,位于同一水平线上与给定结点右邻的结点作为右儿子.将一棵有序树改写成二叉树的例子见下图所示:ccadadbcefgbcefgkhjkhjcabdcekhfjgG是一个完全m叉树,它有t片树叶,有i个分枝点,则(m-1)i=t-1.证明:把m叉树看成是每局有m位选手参加的单淘汰比赛计划表.其中t可代表参赛的选手数,i表(m-1)位选手,故最后经i局比赛后总共淘汰掉(m-1)i位(m-1)i+1=t,此即(m-1)i=t-1.例1.设有28盏电灯,打算使用一个电源插座,问需用多少块有四个插座的接线板?解:考虑利用四叉树(m=4).将四叉树的每个分枝点看成是一个有四个插座的接线板,将每片树叶看作是一盏电灯(t=28).则有(4-1)i=28-1,这里i此求得i=9,故一共需要九块有四个插座的接线板.例2.设有一台计算机,它用一条加法指令可计算三个数的和,如果要计算九个数的和,至少需执行几次加法指令?解:把这九个数看成是一棵完全三叉树(m=3)的九片树叶(t=28),则有(3-1)i=9-1,这里i表示需要执行的加法的次数(也即这棵树中分枝点的个数),从而求得i=4.定义7-8.5(内部与外部通路长度)在根树中,一个结点的通路长度就是指从树根到此结点的通路中所内部通路长度;而把树叶的通路长度称为外部通路长度.G是一个完全二叉树,它有n个分枝点,且其内部通路的长度的总和为I,外部通路的长度的总和为E,则E=I+2n.(证明略)定义(带权二叉树)设T是一棵二叉树,它有t片树叶,这些树叶分别带有权w1,w2,…,wt,则称该二叉树为带权的二叉树.二叉树的应用之一:最优树问题.定义7-8.6(最优树)设T是一棵带权的二叉树,设其中带权为wi的树叶的通路之长度为L(wt),则称w(T)=∑wiL(wi)w1,w2,…,wt的二叉树中,使得w(T)取到最小值的那棵二叉树称为最优树.(最优树的必要条件)设T是带权

w1≤w2≤…≤wt的最优树,则:1)带权w1,w2的树叶v1,v2是兄弟;2)以树叶v1,v2为儿子的分枝点的通路的长度最长.证明:设在带权w1,w2,…,wt的最优树中,v是通路长度v的儿子分别带有权wx和wy,从而有

L(wx)≥L(w1),L(wy)≥L(w2).若有L(wx)>L(w1),则将wx和w1对调,得到新的树T1,则有w(T1)-w(T)=(L(wx)w1+L(w1)wx)-(L(wx)wx+L(w1)w1)=L(wx)(w1-wx)+L(w1)(wx-w1)=(wx-w1)(L(w1)-L(wx))<0

w(T1)<w(T),这与TL(wx)=L(w1).同理有L(wx)=L(w2).因此L(w1)=L(w2)=L(wx)=L(wy).分别将w1,w2与wx,wy对调得到一棵最优树,其中带权w1和w2的树叶是兄弟.定理7-8.4设T是带权w1≤w2≤…≤wt的最优w1和w2的树叶作为儿子的分枝点改成带权w1+w2的树叶,这样得到的新的树T1必也为最优树.证明:由定理假设有w(T)=w(T1)+w1+w2.用反证法.若T1不是最优树,则必有另一棵带权w1+w2,w3,…,wt的最优树T2,让T2中带权w1+w2的树叶v生成两个儿子,由此得到一棵新的树T3,则有w(T3)=w(T2)+w1+w2.因为T2是带权w1+w2,w3,…,wt的最优树,故有w(T2)≤w(T1).如果w(T2)<w(T1),则w(T3)<w(T),这与T是带权为w1,w2,…,wtw(T2)=w(T1).从而T1是带权w1+w2,w3,…,wt的最优树.

求带有给定的个权的最优树的方法:根据上述两个定理,要作出一个有t个权w1,w2,…,wt的最优树,只需作出一个有t-1