图论II图的基本概念

1、11.2 路、回路、图的连通性路、回路、图的连通性 路路,通路通路,迹迹无向图的连通性无向图的连通性 无向连通图无向连通图, 连通分支连通分支有向连通图有向连通图 弱连通图弱连通图, 单向连通图单向连通图, 强连通图强连通图点割集与割点点割集与割点边割集与割边边割集与割边(桥桥) 2路与回路路与回路 定义定义 给定图给定图G=（无向或有向的），（无向或有向的），G中顶点与边的交中顶点与边的交替序列替序列 =v0e1v1e2elvl，(1) 若若 i(1 i l), vi 1, vi是是ei的端点的端点(对于有向图对于有向图, 要求要求vi 1是始点是始点, vi是终点是终点), 则称则称 为为

2、路路, v0是是路的起点路的起点, vl是是路的终点路的终点, l为为路的路的长度长度. 又若又若v0=vl，则称，则称 为为回路回路.(2) 若路若路(回路回路)中所有顶点中所有顶点(对于回路对于回路, 允许允许v0=vl)各异，则称为各异，则称为通路通路(圈圈). (3) 若路若路(回路回路)中所有边各异中所有边各异, 则称为则称为迹迹(闭迹闭迹).路中不含重复顶点，则一定不含重复边。通路一定是迹。路中不含重复顶点，则一定不含重复边。通路一定是迹。按通畅性要求由高到低：按通畅性要求由高到低： 通路通路 迹迹 路路按可能的复杂或曲折程度由高到低：路按可能的复杂或曲折程度由高到低：路 迹迹 通

3、路通路路与回路路与回路n试分别画出：一条通路一条非通路的迹一条非迹的路从中直观感受一下路、迹和通路对通畅程度的不同要求路与回路实例路与回路实例45路与回路路与回路( (续续) )说明说明:n表示方法表示方法 用顶点和边的交替序列用顶点和边的交替序列(定义定义), 如如 =v0e1v1e2elvl 用边的序列用边的序列, 如如 =e1e2el 简单图中简单图中, 用顶点的序列用顶点的序列, 如如 =v0v1vl 非简单图中非简单图中,可用混合表示法可用混合表示法,如如 =v0v1e2v2e5v3v4v5n环是长度为环是长度为1的圈的圈, 两条平行边构成长度为两条平行边构成长度为2的圈的圈.n在无

4、向简单图中在无向简单图中, 所有圈的长度所有圈的长度 3; 在有向简单图在有向简单图中中, 所有圈的长度所有圈的长度 2. 6路与回路路与回路( (续续) )n在两种意义下计算圈的个数在两种意义下计算圈的个数 定义意义下定义意义下 在无向图中在无向图中, 一个长度为一个长度为l(l 3)的圈看作的圈看作2l个不同的个不同的圈圈. 如如v0v1v2v0 , v1v2v0v1 , v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作看作6个不同的圈个不同的圈. 在有向图中在有向图中, 一个长度为一个长度为l(l 3)的圈看作的圈看作l个不同的个不同的圈圈. 同构意义

5、下同构意义下 所有长度相同的圈都是同构的所有长度相同的圈都是同构的, 因而是因而是1个圈个圈. 7路与回路路与回路( (续续) ) 定理定理 在在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的回路的回路

6、.推论推论 在一个在一个n阶图阶图G中，若存在中，若存在v到自身的回路，则到自身的回路，则存在存在v到自身长度小于等于到自身长度小于等于n的圈的圈. 8无向图的连通性无向图的连通性 设无向图设无向图G=,u与与v连通连通: u与与v间有路，记为间有路，记为u v. 规定规定u与自身总连与自身总连通通.连通关系连通关系 R=| u,v V且且u v是是V上的等价关系上的等价关系连通图连通图:任意两点都连通的图任意两点都连通的图. 平凡图是连通图平凡图是连通图.连通分支连通分支: V关于连通关系关于连通关系R的等价类的导出子图的等价类的导出子图设设V/R=V1,V2,Vk, GV1, GV2, ,

7、GVk是是G的连的连通分支通分支, 其个数记作其个数记作p(G)=k.G是连通图是连通图 p(G)=1例例9点割集点割集 记记 G v: 从从G中删除中删除v及关联的边及关联的边 G V : 从从G中删除中删除V 中所有的顶点及关联的边中所有的顶点及关联的边 G e : 从从G中删除中删除e G E : 从从G中删除中删除E 中所有边中所有边定义定义 设无向图设无向图G=, V V, 若若p(G V )p(G)且且 V V , p(G V )=p(G), 则称则称V 为为G的的点割集点割集. 若若v为点割集为点割集, 则称则称v为为割点割点.10点割集实例点割集实例例例 v1,v4, v6是点

8、割集是点割集, v6是割点是割点. v2,v5不是点割集不是点割集 11边割集边割集定义定义 设无向图设无向图G=, 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

9、)=2若若G连通，连通，V 为点割集，则为点割集，则p(G V ) 2 12有向图的连通性有向图的连通性 设有向图设有向图D=u可达可达v: u到到v有路有路. 规定规定u到自身总是可达的到自身总是可达的.可达具有自反性和传递性可达具有自反性和传递性D弱连通弱连通(连通连通): 基图为无向连通图基图为无向连通图D单向连通单向连通: u,v V，u可达可达v 或或v可达可达u D强连通强连通: u,v V，u与与v相互可达相互可达强连通强连通单向连通单向连通弱连通弱连通 13有向图的连通性有向图的连通性( (续续) ) 定理定理(强连通判别法强连通判别法) D强连通当且仅当强连通当且仅当D中存在

10、经中存在经过每个顶点至少一次的回路过每个顶点至少一次的回路定理定理(单向连通判别法单向连通判别法) D单向连通当且仅当单向连通当且仅当D中存中存在经过每个顶点至少一次的路在经过每个顶点至少一次的路 例例 强连通强连通单向连通单向连通弱连通弱连通141.3 带权图、最短路径、图着色带权图、最短路径、图着色n带权图与最短路径带权图与最短路径n图着色问题图着色问题15最短路径最短路径带权图带权图G=, 其中其中w:ER. e E, w(e)称作称作e的的权权. 若若e=(vi,vj), 记记w(e)=wij . 若若vi,vj不相邻不相邻, 记记wij = . 路路L的的权权: L的所有边的权之和的

11、所有边的权之和, 记作记作w(L).u和和v之间的之间的最短路径最短路径: u和和v之间权最小的路之间权最小的路.例例 L1=v0v1v3v5, w(L1)=10, L2=v0v1v4v5, w(L2)=12, L3=v0v2v4v5, w(L3)=11.着色着色定义定义 设无向图设无向图G无环无环, 对对G的每个顶点涂一种颜色，的每个顶点涂一种颜色，使相邻的顶点涂不同的颜色，称为图使相邻的顶点涂不同的颜色，称为图G的一种的一种点着点着色色,简称简称着色着色若能用若能用k种颜色给种颜色给G的顶点着色，的顶点着色， 则则称称G是是k-可着色可着色的的图的着色问题图的着色问题: 用尽可能少的颜色给图着色用尽可能少的颜色给图着色.16例例121222111111222322221111311122234例例例例2171122221112123213321232314例例例例3 学生会下设学生会下设6个委员会个委员会, 第一委员会第一委员会=张张, 李李, 王王, 第二委第二委员会员会=李李, 赵赵, 刘刘, 第三委员会第三委员会=张张, 刘刘, 王王, 第四委员会第四委员会=赵赵, 刘刘, 孙孙, 第五委员会第五委员会=张张, 王王, 第六委员会第六委员会=李