《离散数学》图的基本概念ppt课件.ppt

《《离散数学》图的基本概念ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.2通路、回路与图的连通性简单通(回)路,初级通(回)路,复杂通(回)路无向连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥)1通路与回路定义给定图G=（无向或有向的），设G中顶点与边的交替序列=v0e1v1e2…elvl：若i(1il),vi1和vi是ei的端点(对于有向图,要求vi1是始点,vi是终点),则称为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称为回路.理解：通路或回路是点与边的交替序列，边的端点恰好是前后的两个点长度＝边数2若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通

2、路(初级回路).初级通路又称作路径,初级回路又称作圈.路上各点不重复若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).路上各边不重复3通路与回路(续)说明:在无向图中，环是长度为1的圈,两条平行边构成长度为2的圈.无向简单图中,所有圈的长度3在有向图中，环是长度为1的圈,两条方向相反边构成长度为2的圈.在有向简单图中,所有圈的长度2.4通路与回路(续)定理在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的通路.推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的初

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

4、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)=16短程线与距离u与v之间的短程线:u与v之间

5、长度最短的通路u与v之间的距离d(u,v):u与v之间短程线的长度若u与v不连通,规定d(u,v)=∞.性质：d(u,v)0,且d(u,v)=0u=vd(u,v)=d(v,u)（对称性）d(u,v)+d(v,w)d(u,w)（三角不等式)7点割集（v－点；V’－点集；e－边；E’－变集）记Gv:从G中删除v及关联的边GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边定义设无向图G=,如果存在顶点子集VV,使p(GV)>p(G)，而且删除V的任何真子集V后（VV），p(GV)=p(G),则称V为G

6、的点割集.若{v}为点割集,则称v为割点.理解：删除点后连通分支数可能增加，会减少吗？8点割集(续)例{v1,v4},{v6}是点割集,v6是割点.{v2,v5}是点割集吗？9边割集定义设无向图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}是边割集吗？10几点说明：Kn无点割集（完全图）n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2若G连通，V为

7、点割集，则p(GV)211有向图的连通性设有向图D=u可达v:u到v有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通(也称连通):基图为无向连通图有向边改为无向边后是连通图D单向连通:u,vV，u可达v或v可达uD强连通:u,vV，u与v相互可达强连通单向连通弱连通12有向图的连通性(续)(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通每个顶点有进有出部分顶点有进有出13有向图的短程线与距离u到v的短程线:u到v长度最短的通路(u可达v)u与v之间的距离d:u到v的短程线的长度若u不可达v,规定d=∞.性质：d

8、,v>0,且d=0u=vd+dd注意:没有对称性147.3图的矩阵表示无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵15无向图的关联矩阵定义设无向图G=,V={v1,v2,…,vn},E={e1,e2,…,em},令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).性质16v1v2v4v3e1e2e3e4e5