离散数学 (第七版) 课件 第三部分 图论

1

图论

2图论部分第5章图的基本概念第6章特殊的图第7章树3第5章图的基本概念5.1无向图及有向图5.2通路,回路和图的连通性5.3图的矩阵表示5.4图的着色45.1无向图及有向图无向图与有向图顶点的度数握手定理简单图完全图子图补图5无向图

多重集合:元素可以重复出现的集合无序积:A

B={(x,y)|x

A

y

B}定义无向图G=<V,E>,其中(1)顶点集V是非空有穷集合,

其元素称为顶点(2)边集E为V

V的多重子集，其元素称为无向边，简称边.例如,G=<V,E>,其中V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}6有向图定义有向图D=<V,E>,其中(1)顶点集V是非空有穷集合,

其元素称为顶点(2)边集E为V

V的多重子集，其元素称为有向边，简称边.D的基图:用无向边代替有向边如D=<V,E>,其中

V={a,b,c,d}E={<a,a>,<a,b>,<a,b>,<a,d>,<c,b>,<d,c>,<c,d>}图的数学定义与图形表示,在同构意义下一一对应7无向图与有向图(续)通常用G表示无向图,D表示有向图,也常用G泛指无向图和有向图.V(G),E(G),V(D),E(D):G和D的顶点集,边集.n阶图:n个顶点的图零图:E=

平凡图:1阶零图空图:V=

8顶点和边的关联与相邻定义设e=(u,v)是无向图G=<V,E>的一条边,称u,v为e的端点,e与u

(

v)关联.若u

v,则称e与u

(

v)的关联次数为1;若u=v,则称e为环,此时称e与u

的关联次数为2;若w不是e端点,则称e与w

的关联次数为0.无边关联的顶点称作孤立点.定义设无向图G=<V,E>,u,v

V,

e,e

E,

若(u,v)

E,则称u,v相邻;若e,e

至少有一个公共端点,则称e,e

相邻.对有向图有类似定义.设e=

u,v

是有向图的一条边,又称u是e的始点,v是e的终点,u邻接到v,v邻接于u.9顶点的度数

设G=<V,E>为无向图,v

V,

v的度数(度)

d(v):v作为边的端点次数之和

悬挂顶点:度数为1的顶点

悬挂边:与悬挂顶点关联的边

G的最大度

(G)=max{d(v)|v

V}

G的最小度

(G)=min{d(v)|v

V}例如d(v5)=3,d(v2)=4,d(v1)=4,

(G)=4,

(G)=1,

v4是悬挂顶点,e7是悬挂边,e1是环10顶点的度数(续)

设D=<V,E>为有向图,v

V,v的出度d+(v):v作为边的始点次数之和

v的入度d

(v):v作为边的终点次数之和

v的度数(度)d(v):v作为边的端点次数之和

d(v)=d+(v)+d-(v)D的最大出度

+(D)=max{d+(v)|v

V}

最小出度

+(D)=min{d+(v)|v

V}

最大入度

(D)=max{d

(v)|v

V}最小入度

(D)=min{d

(v)|v

V}

最大度

(D)=max{d(v)|v

V}

最小度

(D)=min{d(v)|v

V}11例例d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,

+(D)=4,

+(D)=0,

(D)=3,

(D)=1,

(D)=5,

(D)=3.12图论基本定理——握手定理定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数.证G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.有向图的每条边提供一个入度和一个出度,故所有顶点入度之和等于出度之和等于边数.推论

任意无向图和有向图的奇度顶点个数必为偶数.13图的度数列

设无向图G的顶点集V={v1,v2,…,vn}G的度数列:d(v1),d(v2),…,d(vn)如右图度数列:4,4,2,1,3设有向图D的顶点集V={v1,v2,…,vn}D的度数列:d(v1),d(v2),…,d(vn)D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d

(v1),d

(v2),…,d

(vn)如右图度数列:5,3,3,3

出度列:4,0,2,1

入度列:1,3,1,214握手定理的应用例1(3,3,3,4),(2,3,4,6,8)能成为图的度数列吗?解不可能.它们都有奇数个奇数.例2已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解设G有n个顶点.由握手定理,43+2(n-4)210解得n815握手定理的应用(续)例3证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证用反证法.假设存在这样的多面体,作无向图G=<V,E>,其中V={v|v为多面体的面},

E={(u,v)|u,v

V

u与v有公共的棱u

v}.根据假设,|V|为奇数且v

V,d(v)为奇数.这与握手定理的推论矛盾.16多重图与简单图

定义

(1)在无向图中,如果有2条或2条以上的边关联同一对顶点,则称这些边为平行边,平行边的条数称为重数.(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点,则称这些边为有向平行边,简称平行边,平行边的条数称为重数.(3)含平行边的图称为多重图.(4)既无平行边也无环的图称为简单图.注意:简单图是极其重要的概念17实例e5和e6是平行边重数为2不是简单图e2和e3是平行边,重数为2e6和e7不是平行边不是简单图18图的同构

定义设G1=<V1,E1>,G2=<V2,E2>为两个无向图(有向图),若存在双射函数f:V1

V2,使得对于任意的vi,vj

V1,(vi,vj)

E1（<vi,vj>

E1）当且仅当

(f(vi),f(vj))

E2（<f(vi),f(vj)>

E2），并且,(vi,vj)（<vi,vj>）与(f(vi),f(vj))（<f(vi),f(vj)>）的重数相同，则称G1与G2是同构的，记作G1

G2.同构实例

19彼得森图例1证明下述2对图是同构的20同构实例(续)例2试画出4阶3条边的所有非同构的无向简单图例3判断下述每一对图是否同构:(1)度数列不同不同构21同构实例(续)(2)(3)不同构入(出)度列不同不同构(左边没有三角形,右边有三角形)注意:度数列相同

(1)(2)

22图的同构(续)几点说明：图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件,但它们都不是充分条件:①边数相同，顶点数相同②度数列相同(不计度数的顺序)③对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构至今没有找到判断两个图同构的多项式时间算法

23完全图

n阶无向完全图Kn:每个顶点都与其余顶点相邻的n阶无向简单图.简单性质:边数m=n(n-1)/2,

=

=n-1n阶有向完全图:每对顶点之间均有两条方向相反的有向边的n阶有向简单图.简单性质:边数m=n(n-1),

=

=2(n-1),

+=

+=

-=

-=n-1

K53阶有向完全图24子图定义设G=<V,E>,G

=<V

,E

>是两个图(1)若V

V且E

E,

则称G

为G的子图,G为G

的

母图,记作G

G(2)若G

G且V

=V，则称G

为G的生成子图(3)若V

V或E

E，称G

为G的真子图(4)设V

V且V,

以V

为顶点集,以两端点都在

V

中的所有边为边集的G的子图称作V

的导出子图，记作G[V

](5)设E

E且E,

以E

为边集,以E

中边关联的所有顶点为顶点集的G的子图称作E

的导出子图,记作G[E

]25生成子图实例K4的所有非同构的生成子图导出子图实例

26GDG[{v1,v2}]G[{e1,e3,e4}]D[{e1,e3}]D[{v1,v2}]27补图定义设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作.若G

,则称G是自补图.例对K4的所有非同构子图,指出互为补图的每一对子图,并指出哪些是自补图.285.2通路、回路、图的连通性

简单通(回)路,初级通(回)路,复杂通(回)路无向图的连通性

无向连通图,连通分支有向连通图

弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥)29通路与回路

定义给定图G=<V,E>（无向或有向的），G中顶点与边的交替序列

=v0e1v1e2…elvl，(1)若

i(1

i

l),vi

1,vi是ei的端点(对于有向图,要求vi

1是始点,vi是终点),则称

为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称

为回路.(2)若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.(3)若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).通路与回路实例3031通路与回路(续)说明:表示方法①用顶点和边的交替序列(定义),如

=v0e1v1e2…elvl②用边的序列,如

=e1e2…el③简单图中,用顶点的序列,如

=v0v1…vl④非简单图中,可用混合表示法,如

=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构成长度为2的圈.在无向简单图中,所有圈的长度

3;在有向简单图中,所有圈的长度

2.32通路与回路(续)在两种意义下计算圈的个数①定义意义下在无向图中,一个长度为l(l

3)的圈看作2l个不同的圈.如v0v1v2v0,v1v2v0v1

,v2v0v1v2,v0v2v1v0,v1v0v2v1

,v2v1v0v2看作6个不同的圈.

在有向图中,一个长度为l(l

3)的圈看作l个不同的圈.②同构意义下所有长度相同的圈都是同构的,因而是1个圈.33通路与回路(续)定理在n阶图G中，若从顶点u到v（u

v）存在通路，则从u到v存在长度小于等于n

1的通路.推论在n阶图G中，若从顶点u到v（u

v）存在通路，则从u到v存在长度小于等于n

1的初级通路.定理在一个n阶图G中，若存在v到自身的回路，则一定存在v到自身长度小于等于n的回路.推论在一个n阶图G中，若存在v到自身的简单回路，则存在v到自身长度小于等于n的初级回路.34无向图的连通性设无向图G=<V,E>,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R={<u,v>|u,v

V且u

v}是V上的等价关系连通图:任意两点都连通的图.平凡图是连通图.连通分支:V关于连通关系R的等价类的导出子图设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,其个数记作p(G)=k.G是连通图

p(G)=1例35点割集

记G

v:从G中删除v及关联的边

G

V

:从G中删除V

中所有的顶点及关联的边

G

e:从G中删除e

G

E

:从G中删除E

中所有边定义设无向图G=<V,E>,V

V,若p(G

V

)>p(G)且

V

V

,p(G

V

)=p(G),则称V

为G的点割集.若{v}为点割集,则称v为割点.36点割集实例例{v1,v4},{v6}是点割集,v6是割点.{v2,v5}不是点割集37边割集定义设无向图G=<V,E>,E

E,若p(G

E

)>p(G)且

E

E

,p(G

E

)=p(G),则称E

为G的边割集.若{e}为边割集,则称e为割边或桥.在上一页的图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8是桥，{e7,e9,e5,e6}不是边割集说明：Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E

为边割集，则p(G

E

)=2若G连通，V

为点割集，则p(G

V

)

238有向图的连通性

设有向图D=<V,E>u可达v:u到v有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通(连通):基图为无向连通图D单向连通:

u,v

V，u可达v

或v可达u

D强连通:

u,v

V，u与v相互可达强连通

单向连通

弱连通39有向图的连通性(续)

定理(强连通判别法)

D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法)

D单向连通当且仅当D中存在经过每个顶点至少一次的通路例

强连通单向连通弱连通405.3图的矩阵表示无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵无向图的邻接矩阵41无向图的关联矩阵定义设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},

令mij为vi与ej的关联次数，称(mij)n

m为G的关联矩阵，记为M(G).例

M(G)=

42无向图的关联矩阵定义设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},

令mij为vi与ej的关联次数，称(mij)n

m为G的关联矩阵，记为M(G).性质(1)每一列恰好有两个1或一个243有向图的关联矩阵定义设无环有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

则称(mij)n

m为D的关联矩阵，记为M(D).有向图的关联矩阵(续)性质(1)每一列恰好有一个1和一个-1(2)第i行1的个数等于d+(vi),-1的个数等于d-(vi)(3)1的总个数等于-1的总个数,且都等于m(4)平行边对应的列相同44例

M(D)=

45定义设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()m

n为D的邻接矩阵,记作A(D),简记为A.性质有向图的邻接矩阵

有向图的邻接矩阵实例4647

D中的通路及回路数定理设A为n阶有向图D的邻接矩阵,则Al(l

1)中元素为D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.48D中的通路及回路数(续)例问在有向图D中(1)长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)长度小于或等于4的通路为多少条？其中有多少条回路？推论设Bl=A+A2+…+Al(l

1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.49例(续)

长度通路回路

合计50818121133141417350定义设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令aij为顶点vi与顶点vj之间的边数，称(aij)m

n为G的邻接矩阵,记作A(G),简记为A.性质(1)无向图邻接矩阵是对称方阵(2)无环顶点所在行或列之和等于该顶点的度数(3)关于通路与回路数的前述定理和推论也成立无向图的邻接矩阵

无向图的邻接矩阵实例51v1到v3长度为2的通路有3条v1到v3长度为3的通路有9条v1到v1长度为2的回路有5条v1到v1长度为3的回路有5条长度为2的通路总共有27条，其中有13条回路525.4

图的着色点着色（简称着色）边着色点着色（简称着色）定义

设无向图G无环,对G的每个顶点涂一种颜色，使相邻的顶点涂不同的颜色，称为图G的一种点着色,简称着色．若能用k种颜色给G的顶点着色，则称G是k-可着色的．图的着色问题:用尽可能少的颜色给图着色.53例121222111111222322221111311122234例2例2541122221112123213321232314应用有n项工作,每项工作需要一天的时间完成.有些工作由于需要相同的人员或设备不能同时进行,问至少需要几天才能完成所有的工作?计算机有k个寄存器,现正在编译一个程序,要给每一个变量分配一个寄存器.如果两个变量要在同一时刻使用,则不能把它们分配给同一个寄存器.如何给变量分配寄存器?无线交换设备的波长分配.有n台设备和k个发射波长,要给每一台设备分配一个波长.如果两台设备靠得太近,则不能给它们分配相同的波长,以防止干扰.如何分配波长?55例3例3学生会下设6个委员会,第一委员会={张,李,王},第二委员会={李,赵,刘},第三委员会={张,刘,王},第四委员会={赵,刘,孙},第五委员会={张,王},第六委员会={李,刘,王}.每个月每个委员会都要开一次会,为了确保每个人都能参加他所在的委员会会议,这6个会议至少要安排在几个不同时间段?56v6v5v4v3v2v1123412至少要4个时段第1时段:一,四第2时段:二,五第3时段:三第4时段:六边着色定义

设无向图G无环,对G的每条边涂一种颜色，使相邻的边涂不同的颜色，称为图G的一种边着色．若能用k种颜色给G的边着色，则称G是k-可着色的．图的边着色问题:用尽可能少的颜色给图边着色.57例4112223111223112233例5例5假设有四位老师要在同一天给五个班级上课，甲老师给一班上2节课，给二班上1节课，乙老师给二、三、四班各上1节课，丙老师给三、四班各上1节课，丁老师给三、四班各上1节课，给五班上2节课。每位老师在同一课时只能给一个班上课。

（1）当天至少要上几节课？

（2）在最少节数下至少需要几个教室？

（3）给出一个节数最少同时最省教室的课表。58例5（授课关系表示成二部图）例5假设有四位老师要在同一天给五个班级上课，甲老师给一班上2节课，给二班上1节课，乙老师给二、三、四班各上1节课，丙老师给三、四班各上1节课，丁老师给三、四班各上1节课，给五班上2节课。每位老师在同一课时只能给一个班上课。

59甲丁乙丙二三一四五例5（边着色和课表）例560甲丁乙丙二三一四五节甲乙丙丁1没课四班三班五班2二班没课四班五班3一班二班没课三班4一班三班没课四班例5（最终结果）例5假设有四位老师要在同一天给五个班级上课，甲老师给一班上2节课，给二班上1节课，乙老师给二、三、四班各上1节课，丙老师给三、四班各上1节课，丁老师给三、四班各上1节课，给五班上2节课。每位老师在同一课时只能给一个班上课。

（1）当天至少要上几节课？

（2）在最少节数下至少需要几个教室？

（3）给出一个节数最少同时最省教室的课表。（1）当天至少要上4节课（4-边着色）

（2）至少需要3个教室（总共12条边，4-边着色某种颜色至少染3边，存在着每种颜色至多染3边的4-边着色）

（3）对应的课表见上页6162第6章特殊的图6.1二部图6.2欧拉图6.3哈密顿图6.4平面图636.1二部图

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

64二部图

定义设无向图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阶零图为二部图.65二部图(续)

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

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

不是66匹配

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

1

例极大匹配最大匹配

1=367匹配(续)设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是完美匹配M1M268二部图中的匹配

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

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

定理(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的完备匹配.70一个应用实例例某课题组要从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

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

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

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

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

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

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

定理

设无向图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是半哈密顿图.84实例例设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证(1)设v为割点,则p(G

v)

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

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

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

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

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

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

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

1)

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

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

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

8国际象棋盘上,跳马问题是否有解?不满足必要条件判断是否为哈密顿图是NP完全的88应用实例例某次国际会议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队.89ABCD竞赛图(续)定理

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

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

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

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

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

G,若G为平面图,则G

也是平面图;若G

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

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

4)阶极大平面图G均有

(G)

3.定理

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

99实例例是否是极大平面图?不是不是是100极小非平面图

定义若G是非平面图,并且任意删除一条边所得图都是平面图,则称G为极小非平面图.极小非平面图必为简单图例如,K5,K3,3是极小非平面图101欧拉公式定理(欧拉公式)设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时结论也成立.102欧拉公式(续)推论(欧拉公式的推广)设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+1103平面图的性质定理设G为n阶m条边的连通平面图,每个面的次数不小于l(l

3),则

设G为有p(p

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

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

2m

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

对

p(p

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

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

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

矛盾.K5K3,3105同胚与收缩

消去2度顶点v

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

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

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

G是平面图

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

G是平面图

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

收缩2条边

K3,3

取子图K5

取子图108平面图的对偶图

定义设平面图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}.109平面图的对偶图的实例例黑色实线为原平面图,红色虚线为其对偶图

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

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

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

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

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

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

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

定理

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

2(n-1)

x+2(n-x)

解得x

2.120例题例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棵非同构的无向树.121例题例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棵非同构的无向树122生成树

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

定理

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

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

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

n

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

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

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

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

k

n

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

对无向图或有向图的每一条边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).141例求图的一棵最小生成树

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

有向树:基图为无向树的有向图根树:有一个顶点入度为0,其余的入度均为1的非平凡的有向树树根:有向树中入度为0的顶点树叶:有向树中入度为1,出度为0的顶点内点:有向树中入度为1,