图论及应用剖析

图论简介图论是数学的一个分支,以图为研究对象.这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系.用点代表事物,用连接两点的线表示两个事物之间具有特定关系.图论起源于18世纪,追朔到1736年瑞士数学家L.Euler出版第一本图论著作,提出和解决著名Konigsberg七桥问题.从那时以来,图论不仅在许多领域,如计算机科学,运筹学,心理学等方面得到了广泛的应用,而且学科本身也获得长足发展,形成了拟阵理论,超图理论,代数图论,拓扑图论等新分支.(8.5,8.8二节不讲)图的定义与记号图G是一个二重组:G=V,E,其中V是非空有限集合,它的元素称为结点,E

也是(可空)有限集合,它的元素称为边.图G的边e是一个结点二重组:a,b,a,bV,e可以是有序的,称为有向边,简称为弧,a称为弧e的始点,b称为e的终点;e也可以是无序的,称为无向边.e=a,b时,称e与a,b关联,或a,b与e关联,或a与b相邻接;关联于同一结点的一条边称为自回路.每条边都是无向边的图称为无向图;每条边都是有向边的图称为有向图;我们仅讨论无向图和有向图.(看图8.1-1和图8.1-2)图的定义与记号续不与任何结点邻接的结点称为孤立结点,全为孤立结点组成的图(视为无向图有向图均可)称为零图.在无向图中两结点间(包括结点自身)若多于一条边，则称这几条边为平行边.在有向图中若同始点和同终点的边多于一条,则称这几条边为平行边,平行边的条数称为该边的重数.含平行边的图称为多重图,非多重图称为线图.无自回路的线图称为简单图.例子见图8.1-3.有向图去掉方向所得无向图称为该图的底图.常用一个图形来表示图称为图的图示deg+(1)=2,deg-(1)=0,deg(1)=deg(2)=…deg+(2)=deg-(2)=1,…=deg(6)=3.deg(1)=…=deg(4)=2.1234abcd123456abcdef结点的度(次数)有向图中,以结点v为始点的边数称为v的出度,记为deg+(v);以结点v为终点的边数称为v的入度,记为deg-(v);它们的和:

deg(v)=deg+(v)+deg-(v)称为v的度.无向图中,与结点v相关联的边数称为v的度,记为deg(v).各结点的度都相等的图称为正则图,或k-正则图,其中k为结点度的公共值.(注:可以只考虑正则的无向图,然后再定义其底图的无向图是正则图的有向图为正则有向图.)例子见上一张幻灯片和图8.1-5.关于有

n

结点

m

边的(n,m)图度的定理定理8.1-1

令

v1,…,vn为图的所有结点,则

i=1n

deg(vi)=2m.(1)证:对于公式(1)左边的和式,图的每条边贡献的度数恰为2,从而结论成立.注:对有向图(1)可写成

i=1n

deg+(v)+

i=1n

deg-(v)=2m.定理8.1-2

任何图中度为奇数的结点必为偶数个.证:因偶度点度的和为偶数,若奇度点为奇数个,则奇度点度的和必为奇数.但偶数加奇数得奇数,便与(1)式右边为偶数相矛盾.8.1#4(c)简单无向图

G

必有2结点同度证:令G={v1,…,vn}.若

G

中没有孤立点,则

G

中

n个结点的度只取

n-1

个可能值:

1,2,…,n-1,从而

G

中至少有两个结点的度相同.否则,G中有孤立点,不妨设vk,vk+1,…,vn为全部孤立点,则

v1,…,vk-1的度只取

k-2个可能值:

1,2,…,k-2,从而此

k-1个结点中至少有两个同度点.图的同构定义:对给定两个图G=V,E,G=V,E,若存在双射f:VV

使对任意a,bV,(a,b)E

(f(a),f(b))E,并且(a,b)与(f(a),f(b))有相同重数,则称

G

与

G同构,记为

GG.注:①

两图同构是相互的:GG

GG.②

两图同构时不仅结点之间要有一一对应关系,而且要求这种对应关系保持结点间的邻接关系.对有向图同构还要求保持边的方向.③

寻求判断图同构的简单有效方法仍是图论待解决的重要问题.同构图举例

G

G’

H

H’1

a,2

b,3

c,1

a,2

b,3

c,4

d4

d,5

e,6

f1234abcd123456abcdefGG’HH’非同构图举例存在结点数及每个结点对应度都相等的两个图仍然不同构的情况.一个例子是图8.1-8;另一例如下:(注意:两个4度点或邻接或不相邻接)GG’子图的概念定义:给定两个无(有)向图G=V,E,G=V,E.若VV

和

EE,则称

G是G的子图;若VV,EE,且

GG,则称

G是

G

的真子图;若V=V

和

EE,则称

G是

G

的生成子图;若子图

G无孤立结点且G由E唯一确定,则称G是由边集E导出的子图;若对子图

G=V,E中任二结点

u,v,(u,v)E

(u,v)E,则称

G是由结点集V导出的子图(易见:V导出的子图G是以V为其结点集,所有在G中同时关联于V中两点的边为其边集).有向图子图举例(图8.1-10)①:由{(1,2),(1,4),(5,1)}导出的子图;②:由{(1,2),(3,2),(3,4),(1,4)}导出的子图(也是此4点导出的子图);③:由{1,2,4,5}导出的子图.①②③11112222555334444完全图与补图E=VV的有向图G=V,E称为有向完全图.n个结点的无向简单图如果任二不同结点都相邻时,称为n结点无向完全图,记为

Kn.完全图的例子见图8.1-11.n

结点线图G=V,E与H=V,E’称互为补图(记为G=H’或H=G’),如果E’是n结点完全图的边集与E的差集.下列二无向图G与H互为补图.GHK48.1#13的用红,兰色给

K6边着色命题:对任意一种着色方案的着色结果,或者有一个红K3,或者有一个兰K3.证:令a,b,c,d,e,f为K6的6结点.因过f的5条边必有三边着为同色,不失一般性,设(a,f),(b,f),(c,f)已着红色.若(a,b),(a,c),(b,c)已着兰色,则{a,b,c}导出的子图是一个兰K3,从而结论成立.否则此三边必有一边,例如(a,b)已着红色,则{a,b,f}导出的的子图是红K3.证毕.推论:任何6人的人群中,或者有3人互相认识,或者有3人彼此陌生.(当二人x,y互相认识,边(x,y)着红色,否则着兰色.则6人认识情况对应于K6边的一个二着色.由上述命题知或者有红K3或者有兰K3.)fabcabc6改5结论不成立路径与回路图

G=V,E

的点边交替序列

P=v0e1v1e2v2

envn称为

G

的一条从v0

到vn的长为

n

的路径,其中,ei=(vi-1,vi)E,i=1,…,n(对有向图要求vi-1,vi为ei的始,终点).P

称为简单路径,如果e1,,en

两两不同;P

称为基本路径(链),如果v0,v1,,vn

两两不同(易见链必为简单路径);P

称为回路,如果v0=

vn;回路

P

称为简单(基本)回路,如果e1,,en(v1,,vn)两两不同.路径

P

可只用边序列

e1e2en表示.若

G

为线图,则路径

P

也可只用结点序列

v0v1

vn

表示.例见图8.2-1.

任何图

G

中有从

u

到

w

的路径(回路)必有从

u

到

w

的基本路径(回路)由于G有从u到w的路径,G必有一条长度最小的从u到w的路径:P.如果P不是基本路径,则

P=ue1v1e2

viei+1

vjej+1

enw

中

vi=vj,于是

P-{ei+1,,ej}仍是G的一条从u到w的路径,但长度比P长度还要小,得出矛盾.vivj+1vj-1vi+1vn-1uwv1P在

n

结点的图中任何链的长度都不大于n-1;任何基本回路的长度都不大于

n证:设任一链

P

的长度为k,则

P穿程于

k+1个结点:P

=

v0e1v1e2v2

ekvkvk.

因

v0,v1,,vk

两两不同,故

k+1n,从而

kn-1.同理,长度为k的基本回路有

k

个不同结点，从而

kn.距离的概念图

G=V,E中,从结点

u

到

w

的最短路径(必为链)的长度称为

G

的从

u

到

w

的距离,记为

d(u,w).

如果从

u

到

w没有路径,则令

d(u,w)=+.(注意:在无向图中恒有

d(u,w)=d(w,u),而在有向图中可能出现d(u,w)d(w,u).)对任意

u,v,wV,d(u,v)是非负整数或+;d(u,v)0;d(u,v)=0

当且仅当

u=w;d(u,v)+d(v,w)d(u,w)(三角不等式,距离特性)三角不等式的证明:若

d(u,v)=+

或

d(v,w)=+,结论显然成立.否则,有从

u

到

v

长度为

d(u,v)的路径和从v到w长度为d(v,w)的路径,从而有从u到w长度为d(u,v)+d(v,w)的路径.无向图的连通性在无向图G中,若有从结点u到w的路径(或从u到w的链,因有u-w路必有u-w链),则称从u到w可达.约定每个结点到自身可达.(图8.2-2(b))无向图称为是连通的,如果任二结点都可达.易见:G

连通当且仅当

G

有一个生成子图连通.无向图结点间的可达关系是等价关系(满足自反,对称和传递律),因此其商集给出

G

的结点集的一个划分,属于一个等价类的结点导出

G

的一个连通子图,且不存在以此子图为真子图的连通子图.故把这些连通子图称为G的连通分支.G的任何二结点相互可达当且仅当它们属于同一个连通分支.G为连通当且仅当它恰有一个连通分支.G的连通分支数记为

(G).有向图的连通性已知有向图

G,若它的底图是连通无向图,则

G

称为是弱连通的;若

G

的任二结点都相互可达,则G称为是强连通的;若

G

的任二结点至少从一个到另一个可达,则

G

称为是单向连通的.易见:强连通性

单向连通性

弱连通性;但反之不真.反例如下:

强连通单向连通非强连通弱连通非单向连通从a到b不可达从a到b不可达且从b到a不可达aabbcd有向图的强(单向,弱)连通分支已知有向图

G

及其子图

G.若

G是强(单向,弱)连通的,并且

G

中没有以

G为真子图的强(单向,弱)连通子图,则称

G为

G

的强(单向,弱)连通分支.注①一个有向图的上述三种连通分支可能是互不相同的,图8.2-4中的图就是这样.②在有向图中可用‘属于同一强(弱)连通分支’引入结点间的等价关系.但对单向连通分支引入的关系不满足传递性,从而不是等价关系(图8.2-5).8.2#4无向图

G恰有的2个奇度结点可达解1:令u,w为G恰有的2个奇度结点.考察u所在的连通分支G’.因任何图的奇度点为偶数,故G’至少还有另一奇度点.但G’的每个点在G和G’中有相同的度,所以G’恰有2个奇度点而且就是u和w.再由G’的连通性推出u到w可达.解2:可一般地证明在无向图G中从任一奇度点u出发的一条最长简单路的另一端点必为一个奇度点,原因是从u出发的最长简单路不会终止在u处(否则d(u)为偶数);也不会终止在任一偶度点v处(否则d(v)为奇数).赋权图中的距离应用广泛的赋权图是三重组:G=V,E,W,V,E

分别为

G

的结点集和边集,W是从

E

到

R+的函数,边e=(i,j)的函数值

W(e)=W(i,j)称为

e

的权.

赋权图

G的一条路径

P=(e1,…,ek)的长度定义为:W(P)=W(e1)+…+W(ek).从结点u到w的距离定义为d(u,w)=min{W(P)|P为G中从u到w的路径},约定:d(u,u)=0;d(u,w)=

,当从u到w不可达.例如,对右边的图有d(a,c)=5;

d(a,d)=9;d(a,e)=7.21073245abcde求已知简单连通赋权图G中从源点a到其它各点x的最短距离的Dijkstra算法步骤①

把结点集V分割为二子集

S,T.开始时S={a},T=V-S.步骤②

对每结点

tT,求出

D(t)之后再定出xT

使得

D(x)=

min{D(x)|tT}.步骤③

置

S

为

S∪{x}置

T为T-{x}.若

T=则停止,否则转步骤②作下一次循环.将证:第②步求得的每一点x对应有

D(x)=d(a,x).

开始时令

D(t)=W(a,t),结论显然成立:D(x)=min{W(a,t)|tT}=d(a,x).

下一步对S=S∪{x},T=T-{x}令D(t)为T中结点的D(t)值,则D(t)=

min{D(t),D(x)+W(x,t)}.Dijkstra算法的标号法举例21073645210736452210736452107364510

2

95225599990000用Dijkstra算法的标号法解8.2#11(b)11010141

05326101555462233881063

Euler路径与Euler图Konigsberg七桥问题(1736年).穿程于(有向或无向)图

G

的每条边一次且仅一次的路径(回路)称为

Euler

路径(回路).

具有

Euler

回路的连通图称为Euler图.Euler定理

无向连通图G有一条Euler路径当且仅当

G

有零个或两个奇数度结点(证明见教本255页);有向连通图G有一条Euler路径当且仅当

G的每点出,入度相等,只有两点例外,并且它们出,入度之差一为1,一为-1.推论无向连通图

G

是Euler图当且仅当

G

的结点度数都是偶数.应用:Konigsberg七桥问题不可解,因对应图(见图8.2-8(b))都是

3

度结点.用定理8.2-4的证明方法构造Euler回路1155522233444111234113515245=123411352451=12341352451无向图

G

能否一笔画的问题等价于

G

是否有一条Euler路径(回路)的问题若图只有两个奇结点,则任何Euler路径必从其中一点开始到另一点结束.利用这条规律,先在此2奇点之间加条边使之变成Euler图并画出一条Euler回路,然后再去掉所加的边即得一条Euler路径.ab123456789Hamilton路径与Hamilton图无向连通图G穿程于G

的每一结点一次且仅一次的路径(回路)称为G

的一条Hamilton

路径(回路);具有Hamilton回路的无向连通图称为Hamilton图.由定义知Hamilton

路径(回路)必为基本路径(回路).1859年Ireland数学家Hamilton提出环游世界游戏给出Hamilton图的一个经典例子(图8.2-11).可以证明:对任意正整数

n3

完全图

Kn

恒有Hamilton回路(不难从任一点开始作出一条Hamilton回路,每一步都通到一个新结点,最后回到起点).(推广到赋权图的情形,求有最小权的Hamilton回路问题就是有名的货郎问题)Hamilton图的一个必要条件定理若G=V,E为Hamilton图,则对每个

SV有

(G-S)|S|,其中(G-S)表示子图G-S的连通分支数.证:设C是G的一条Hamilton回路(必为基本回路),则对V的任意真子集S都有

(C-S)|S|,(1)(S={a1}时,(1)式成立等式;

S={a1,a2}时,C1=C-{a1}是链;

而

C-S=C1-{a2}是链,当且仅当a2为C1端点,否则

(C-S)=2.总之,(C-S)2=|S|.S={a1,…,ak,ak+1}时,由归纳法得

(C-S)

(C-{a1,…,ak})+1

|{a1,…,ak}|+1=k+1=|{a1,…,ak+1}|.)因生成子图的连通分支数不比母图的多和C-S是G-S的生成子图,故得证

(G-S)(C-S)|S|.a1a2Ca1Ca28.2#15求简单无向图G:(b)G有E-回路但无H-回路;(d)G无E-回路也无H-回路左图G无奇度点故有Euler回路;易见G无Hamilton回路(取S={a,b}时,有

(G-S)=3>2=|S|).右图H有奇度点故无Euler回路;易见H无Hamilton回路(证明同上或用穷举法验证).GHabab非Hamilton图举例例①

图8.2-12不是Hamilton图,原因是:取S为3个黑点时有

(G-S)=4

>3=|S|.例②

图8.1-5的Peterson图不是Hamilton图,但它满足对一切非空子集SV有

(G-S)|S|,所以,定理8.2-6的条件不是充分的.例③

图8.2-13不是Hamilton图(用一种符号标记法证明).结点符号标记法补充图标记结束后,可能出现相邻结点标记符号相同的情况,此时应先在该对结点之间增加一个新结点(此点必为2度点),同时将它标以不同的符号.设所有有相同标记的邻点都做上述处理之后得到的图记为G.则

G

有Hamilton路当且仅当G有Hamilton路.故若

G的不同标记结点数不同时(如下图)即可断定

G

不是Hamilton图.AAABBBAAABBBBGG

n(3)结点无向简单图G为Hamilton图的一个充分条件:n/2,记最小度数证:用反证法.若结论不成立,则必有n结点的最大(边数最多)非Hamilton图G=V,E.因GKn,故G有结点u,v,(u,v)E,且G+(u,v)为Hamilton图,同时G+(u,v)中任一Hamilton回路都含边(u,v).于是G有从u到v的Hamilton路径(u=v1,v2,…,vn=v)(见下图).令S={vi|(u,vi+1)E},T={vi|(vi,v)E},则vnS∪T,|S∪T|<n.又

S∩T=(否则设某viS∩T,则如下图所示G有Hamilton回路矛盾).因此

d(u)+d(v)=|S|+|T|=|S∪T|+|S∩T|<n,与假设矛盾.u=v1v2vi-1vi+1vivn=v注与例注由上面的证明可得更一般结论:n结点无向简单图G为Hamilton

图,如果G的任2结点度数之和都不小于

n/2.例

n结点无向k-正则图必为Hamilton图只要kn/2.(因=kn/2)Hamilton图的一个应用(习题8.2#6)BCDEFG7位客人入席,A只会讲英语,B会讲英,汉语,C会讲英,意大利,俄语,D会讲日,汉语,E会讲德,意大利语,F会讲法,日,俄语,G会讲法,德语.能否安排圆桌席位使每位客人与其左右邻不用翻译便可交谈?建立无向图模型:结点为客人;会共同语言的2结点相邻接.则问题归结为求此图的一条Hamilton回路.不难验证,此图有一条Hamilton回路是:(A,B,D,F,G,E,C,A).按此回路安排席位可满足要求.A英英法德俄意日汉Hamilton图对编码的一个应用把圆周等分成2n个扇形,每一扇形代表一个n位二进制串用以表示旋转指针的位置(不难设计指针上的n个触点来实现这个数).当n=3时右下图是一例.由于交界附近会出现误差,自然要求相邻二数尽可能接近,即要求ijk与uvw相邻必须满足|{i,j,k}∩{u,v,w}|=2(1)此问题可归结为求立方图G=V,E,V={000,001,…,111},ijk,uvwE当且仅当条件(1)成立,的一条Hamilton路.(解存在但不唯一)111110101100000010011001000001011111110100101010有向线图的邻接矩阵定义将有向线图G=V,E的结点集强行命名(标定次序)为

V={1,2,…,n},则n阶(0,1)方阵A=(aij)称为的G邻接矩阵,其中当(i,j)E,aij=1;否则,aij=0.注①邻接矩阵与结点的标定次序有关,不同的标定次序对应的邻接矩阵不同,但这两个矩阵置换相似,即适当地交换行和列的次序能从一个邻接矩阵变到另一个.或者说,它们对应的有向线图同构.

②有向线图在标定次序后得到唯一邻接矩阵;一个n阶(0,1)方阵对应唯一标定次序的有向线图.换句话说,不计图的同构和矩阵的置换相似有向线图与一个n阶(0,1)方阵一一对应.有限集V上的关系R的图示是以为V结点集的一个有向线图易见:关系R的关系矩阵正是R的图示作为有向线图的邻接矩阵.一个有向线图G=V,E对应的关系R的逆关系R~对应的有向线图G~=V,E~

称为G的逆图.G与G~有相同(的强行命名)的结点集,并且(i,j)E(j,i)E~.逆图G~的邻接矩阵A~与原图的邻接矩阵A之间的关系是:A~=AT.无向线图与赋权图的邻接矩阵定义无向线图G=V,E,V={1,2,…,n}的邻接矩阵是n阶(0,1)方阵A=(aij),其中当(i,j)E,aij=aji=1;否则,aij=aji=0.由此可见,无向线图的邻接矩阵是对称矩阵:A=AT.例如,零图的邻接矩阵是零矩阵;

完全图Kn的邻接矩阵是恰有n个0并全在对角线上的n阶(0,1)方阵.定义赋权图G=V,E,W,V={1,2,…,n}的邻接矩阵是n阶(0,1)方阵A=(aij),其中当(i,j)E,aij=W(i,j);否则,aij=0.邻接矩阵的图论意义设A为有向线图G的邻接矩阵.①A的第i行(列)和等于第i结点的出(入)度,i=1,…n.②B=AAT=(bij)的元素

bij=ai1aj1+…+ainajn=k表示有k个点,它们都是从i,j引出的有向边的公共交点.特别,bii是第i结点的出度.对偶地可讨论ATA的元素的图论意义.③A2=AA=(aij(2))的元素aij(2)=ai1a1j+…+ainanj=k表示有k个点,它们都是从i到j长为2的有向路径的中点,即从i到j长为2的路径恰有k条.一般地,从i到j长为m的路径恰有aij(m)条;过i的长为m的回路恰有aii(m)条.ij有向线图的可达矩阵将任一有向多重图G的多重边只保留其中一边所得的线图记为G’,则G’是G的生成子图,并且任2结点在G内可达当且仅当它们在G’可达.因此可以只限于研究有向线图G’的可达性.为了研究有向线图结点间的可达性而引入可达矩阵的概念.其定义如下:设G=V,E是有向线图,V={1,2,…,n}.n阶(0,1)矩阵P=(pij)称为G的可达矩阵,其元素定义为:当点i到点j可达,pij=1;否则,pij=0,i,jV(i到i可达指过i有回路).例如,右之有向图的可达矩阵是

A=1234如何求n结点线图G的可达矩阵?先求出G的邻接矩阵A和矩阵B=A+A(2)+…+A(n).因为G的基本路径长不超过n-1和没有基本u-w路便没有任何u-w路,故对ij,bij0

当且仅当vi到vj可达(bij是G的长度不超过n的所有路径数).又因G的基本回路长不超过n,故bii0

当且仅当G中有过vi的回路.方法①

利用矩阵B确定可达矩阵P=(pij):当bij=0,pij=0;否则,pij=1.方法②

直接由邻接矩阵确定可达矩阵:P=A∨A2∨…∨An,其中Ak为A的布尔方幂,例如(易见A(k)与Ak的对应元素同时为0或同时不为0)例2(p265)计算中的一些说明由B或P可求得G的强连通分支对应结点集为:{1},{2},{3,4,5}.由A,A(2),…,A(n)的(i,j)元决定i到j的距离我们知道:当B=A+A(2)+…+A(n)的(i,j)元不为0时,G至少有一条长度不超过n的i-j路径,从而i到j可达.不仅如此,使aij(k)0的最小正整数k恰好就是i到j的距离:d(i,j).例如,k=2,aij=0,aij(2)0

说明点i与j不相邻,但存在某点m满足aim=amj=1,即有从i到j的长为2的路,所以d(i,j)=2.实例在教本p.265例2中有a15=a15(2)=0,a15(3)0,由此推出

d(1,5)=3.因A(k)与Ak的对应元素同时为0或同时不为0,故用Ak代替A(k)也可以求两结点的距离.8.3#5如何从邻接矩阵判断是否欧拉图?解:首先,利用图G的邻接矩阵的第i行(列)和求出

d+(vi)(d-(vi));其次,利用可达矩阵

P=A∨A2∨…∨An

是否为全1矩阵判断图G是否为强连通;最后,利用下列等价式判断图G是否为欧拉图:G为欧拉图

d+(vi)=d-(vi),i=1,…,n

∧G为强连通二部图的概念定义:简单无向图G=V,E称为二部图,如果V可划分为两个子集X和Y使得E中每条边的二端点都分别属于X,Y.二部图G常记为

G=X,E,Y.二部图G=X,E,Y称为完全二部图,如果X的每一点都与Y的每一点邻接,完全二部图常记为Km,n,其中,m=|X|,n=|Y|.例图8.4-1.用结点标记法判断已知图G是否为二部图方法:步骤:①

任选一点标为A;②

把所有与上一步标为A(B)的点相邻的点标为B(A),照此继续,直到每点都被标记为止.③

判断原则:如果标记后的图没有任何相邻二点有相同的标记,则G是二部图,其互补结点子集X,Y分别为两种标记点的集;否则,G不是二部图.AAAAAAAABBBBBBB非二部图二部图无向图G为二部图当且仅当所有回路长为偶数证

必要性:若G=X,E,Y为二部图,C=(v0,v1,v2,…,vk,v0)为任一回路,则{v0,v2,…,vk-1},{v1,v3,…,vk}分属X,Y.因此k为奇数,从而C的长度k+1是偶数.充分性:不妨设G为任何回路长度均为偶数的连通图.取定v0V后,定义V的一个划分:X={v|d(v0,v)是偶数}(易见v0X);

Y=V-X用反证法证Y(X)的任二点不相邻.若vi,vjY∧(vi,vj)E,则d(v0,vi),d(v0,vj)都为奇数,由此推出G中有过v0,vi,vj的长为奇数的回路的矛盾.v0vivj二部图的匹配与最大匹配定义:(二部)图

G=X,E,Y

的边集E的子集M称为G的一个匹配,如果M的任二边都没有公共端点;G中边数最多的匹配称为最大匹配(不唯一);含有G的每一点的匹配称为完美匹配(必为最大匹配仍不唯一).下面是最大,完美匹配的例子(用粗线表示):工作分配问题问题某教研室有4位教师:A,B,C,D.A能教课程5;B能教1,2;C能教1,4;D能教课程3.能否适当分配他们的任务,使4位教师担任4门不同课并且不发生安排教师教他不能教的课的情况?此问题可归结为二部图的数学模型:G={A,B,C,D},E,{1,2,3,4,5},(X,y)E,如果X能教y.一个满足要求的工作分配正是一个含有4条边的一个最大匹配.ABCD12345求图G最大匹配的方法首先

任取一个匹配(含一边也可)M作为起点.接着按下列方法逐步调整当前匹配(每一步使它调整为边数多1的匹配)最后达到一个最大匹配:步骤①在X中选定一个不属于M的点xi标记(*).步骤②在X的新标记的点中选一点,如xi,用(xi)标记通过不属于M的边与xi邻接并且尚未标记的点(如yi);在Y的新标记的点中选一点(如yi),用(yi)标记通过M的边与yi邻接并且尚未标记的点;照此继续,直到发现标记到Y的一个点,该点不与X中任一边相关联或标记不到任何这样的点为止.出现前一情况,便找到一条关于M的交替链(定义8.4-4);利用它可调整M到一个比M多一边的匹配;出现后一情况便表示M已为最大匹配.求最大匹配举例解:①取一个初始匹配M={Bb,Cc,Dd}.②用标记法从点A开始求得一条交替链:=(AcCe)(左图).③用调整匹配M:将中属于M的边删去并将其中不属于M的其它边添加到M中得到比M多一边的新匹配M’(如右图示).④因对M’用标记法只能从E或F开始,但都不能求出M’的任何交替链,故判定M’是一个最大匹配.A(c)BCD(d)abc(D)d(E)eE(*)F(*)fA(*)BC(c)Dabc(A)de(C)EFfM’树的概念树是应用中特别重要的特殊图,分无向树和有向树两种.定义无回路的无向连通图称为无向树.也可以说,无基本回路的无向连通图称为无向树,因为:无回路等价于无基本回路.连通分支全为无向树的图,即无回路的无向图,称为森林.树的1度点称为树叶,不是树叶的点称为分枝点.例图8.6-1.(n,m)无向线图G是树的5个等价条件①G是树—连通无回路.②G无回路且m=n-1.③G连通且m=n-1.④G无回路且加一边得唯一回路.⑤G连通且少一边不连通.⑥G任二点间有唯一(基本)路径.证

①

②:2结点树的边数为1=2-1.假设k结点树的边数为k-1.要证k+1结点树的边数为k.事实上,树G必有一树叶w(否则G任一点的度都大于1,从任一点出发沿一边进入另一点恒可沿另一边离开.因G的结点有限,故有限步以后一定要回到前面的点,便与G无回路相矛盾).子图G-{w}显然是树,其点数是k,按归纳假设其边数是k-1,从而G的边数是k=(k+1)-1,归纳证明完成.证

②

③:要证若G无回路且m=n-1,则G连通.不然的话,G有k(2)个无回路的连通分支(树):T1,…,Tk,设Ti为(ni,mi)图,则

m=m1+…+mk=(n1-1)+…+(nk-1)=(n1+…+nk)-k<n-1矛盾.③

④:要证若G连通且m=n-1,则G无回路且加一边得唯一回路.先对n用归纳法证明G无回路.n=2时显然成立.设n=k时结论已成立并考虑n=k+1的情形.此时若G无1度点,则2m2n与m=n-1矛盾.故G必有1度点w.易见G-w连通且满足条件(边数比点数少1),由归纳假设G-w无回路.因w为1度点,故G也无回路.再证G加任一边e=(vi,vj)得唯一回路.G连通性保证有vi-vj路,从而G+e有回路.因删去两条回路中的任一边仍有回路留下,故G+e不会有两条回路(否则G有回路).证

④

⑤:要证若G无回路且加一边得唯一回路,则G连通且删去一边不连通.用反证法,因G是森林,若G不连通,则在G的二连通分支的点间加边不会得新回路,故G连通.若连通的G删去一边e还连通,便得出G=(G-e)∪{e}有回路的矛盾.⑤

⑥:要证若G连通且删去一边不连通,则G任二点间有唯一路径.事实上,G连通性保证任2点u,w间有路径.若有两条这样的u-w路径便与G删去一边不连通的假设矛盾.⑥

①:要证若G任二点间有唯一路径则G是树.任2点都可达表示G连通.若G有回路,则G必有两点其间有两条路径,与条件⑥矛盾.推论由条件⑤,树是结点数固定下边数最少的连通图,并且min{m|(n,m)图连通}=n-1.由条件④,树是结点数固定下边数最多的无回路图,并且max{m|(n,m)图无回路}=n-1.每棵树至少有两片树叶(n2).证:若不是这样便有d(v1)+…+d(vn)2(n-1)+1>2(n-1)=2m,与d(v1)+…+d(vn)=2m的已知规律矛盾.8.6#12

证任何无向树T都是二部图解:取定一点wT(树根).对T-w的每一点v,w到v有唯一链,于是d(w,v)=h(v)是v的一个特性参数（关于树根的高).对T-w的任二不同结点u,v,u和v相邻仅当|h(u)-h(v)|=1.于是令X={v|h(v)为偶数},Y={v|h(v)为奇数},则X(Y)的不同点不会相邻,得证T=X,E,Y是二部图.wvu生成树的概念定义无向图G=V,E的生成子图T是树,则称T是G的一棵生成树(不唯一,图8.6-2).任何连通无向图G至少有一棵生成树.证(破圈法)若G无简单回路,则G自己是一棵生成树.否则,G有简单回路C1,删去C1的一边所得G的生成子图记为G1.若G1无回路,则G1为生成树;否则G1有简单回路C2,删去C2的一边所得G1的生成子图记为G2.若G2无回路,则G2为生成树;否则,…照此继续.易见经m+1-n步必可找到G的一棵生成树.推论无向图G连通当且仅当G有生成树.最小生成树的概念定义赋权简单连通无向图G=V,E,W的子图

H的权定义为

H

的所有边的权和.G中权最小的生成树称为最小生成树(对普通简单连通图不考虑最小生成树).最小生成树有很强的应用背景,例如:设计联系若干城市的最短线路通信网;设计供应若干居民点的最短自来水管线路等.求最小生成树的Kruskal算法(避圈法)算法将赋权简单连通无向图G的边排序:e1e2…em.开始时k:=1,A:=.步骤①

若A∪{ek}导出的子图无回路,则

A:=A∪{ek}.步骤②

若|A|=n-1,算法结束;否则转步骤①.例对左边无向图用Kruskal算法求得右边的最小生成树.123456789101112√

√

√

√

√

√√1234567=n-11234567891011121235689Kruskal算法的正确性证明:由Kruskal算法必可求得赋权简单图G的一棵生成树T0(因G连通),不妨令T0的边为e1,…,en-1.若T0不是最小生成树,则G的每棵最小生成树对应一个i,使得ei+1T但{e1,…,ei}T(i=0表示T与T0无公共边).由于最小生成树有限,我们取T为对应最大i的那棵最小生成树.于是,T+ei+1有唯一基本回路C(包含ei+1).因树T0无回路,故有边fC且fT0,即fT-T0.在T中以ei+1代f(仍无回路)得新生成树T’=T+ei+1-f,其权为W(T’)=W(T)+W(ei+1)-W(f)W(T).于是W(ei+1)W(f).因T为树,{e1,…,ei,f}诱导的子图无回路,从而由Kruskal算法选边的过程知W(ei+1)W(f).所以W(ei+1)=W(f).这意味着W(T’)=W(T),即T’也是G的最小生成树.但T’包含{e1,…,ei,ei+1},他比T对应更大的i值,引出矛盾.得证必须是最小生成树.求最小生成树的破圈法此法1975年由中国数学家管梅谷教授首先提出,具体算法如下:将赋权简单连通无向图G=V,E的边排序:e1e2…em.开始时A:=E.步骤①

若A无回路,则A是最小生成树,算法结束,否则转步骤②.步骤②

在A中任取的一条回路C中取有最大权的边e,置A:=A-e后转步骤①.破圈法的正确性基于下列事实(定理8.6-9):G的任何一条简单回路C中权最大的边f一定不属于任何最小生成树T.(C必有一边e不属于T,若f属于T,则以e代f所得的生成树T’的权W(T’)=W(T)+W(e)-W(f)<W(T),产生矛盾.)123568947121110结点123456789101112删去顺序254

318.6#5

证连通简单无向图G的任一边e都是G的某棵生成树的边解:令G的每一边的权为1得出的赋权图记为G’.显然赋权图G’的任一最小生成树也是G的一棵生成树.

在用Kruskal算法或破圈法求赋权图G’的最小生成树时,只要把所考虑的那边e排在第一位(因为每边的权相同,故任何边都可排在第一位)就能保证所求得的最小生成树中一定含有e.有向树与有根树的概念借鉴无向树的概念可以建立有向树的概念.定义

底图为树的有向图称为有向树.有向树称为有根树,如果存在一点(树根)入度为0而其余每点入度都为1,或等价地,树根到其它各点都有且仅有一条有向链(仅有一条显然;从任何点一定可以反推到树根).有根树必为有向树,反之不真(右图为一反例).有根树的特殊画法:始点在上终点在下,箭头略去.例图8.7-1(a).(与Hasse图类似)树叶,分枝点,子树的概念有根树的典型例子是家谱树.树根是家谱的第一代老祖宗;每条弧始点和终点分别是父和子;每条路径始点是祖先,终点是后裔.出度为0的结点(没有儿子者)称为树叶,否则称为分枝点;分枝点及其所有后裔组成子树(非根的分枝点导出真子树).从树根r到一结点a有唯一有向路径,其长度t称为a的层次(a为第t代孙),有根树各结点层次最大值称为树的高度.8.7#6

如何利用邻接矩阵判断有根树?解:按定义有向图G是有根树

其底