文档详情

《离散数学》图的基本概念.pptx

发布:2025-05-15约4.86千字共10页下载文档
文本预览下载声明

7.2通路、回路与图的连通性1简单通(回)路,初级通(回)路,复杂通(回)路01无向连通图,连通分支02弱连通图,单向连通图,强连通图03点割集与割点04边割集与割边(桥)05

通路与回路2定义给定图G=V,E(无向或有向的),设G中顶点与边的交替序列?=v0e1v1e2…elvl:若?i(1?i?l),vi?1和vi是ei的端点(对于有向图,要求vi?1是始点,vi是终点),则称?为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl,则称?为回路.理解:通路或回路是点与边的交替序列,边的端点恰好是前后的两个点长度=边数

若通路(回路)中所有顶点(对于回路,除v0=vl)各异,则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.路上各点不重复若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).路上各边不重复

通路与回路(续)4说明:在无向图中,环是长度为1的圈,两条平行边构成长度为2的圈.无向简单图中,所有圈的长度?3在有向图中,环是长度为1的圈,两条方向相反边构成长度为2的圈.在有向简单图中,所有圈的长度?2.

通路与回路(续)5在n阶图G中,若从顶点vi到vj(vi?vj)存在通路,则从vi到vj存在长度小于等于n?1的通路.定理在n阶图G中,若从顶点vi到vj(vi?vj)存在通路,则从vi到vj存在长度小于等于n?1的初级通路.推论在一个n阶图G中,若存在vi到自身的回路,则一定存在vi到自身长度小于等于n的回路.定理在一个n阶图G中,若存在vi到自身的简单回路,则一定存在长度小于等于n的初级回路.推论

无向图的连通性6设无向图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

短程线与距离7u与v之间的短程线:u与v之间长度最短的通路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)(三角不等式)

点割集(v-点;V’-点集;e-边;E’-变集)G?V?:从G中删除V?中所有的顶点及关联的边G?e:从G中删除eG?E?:从G中删除E?中所有边记G?v:从G中删除v及关联的边01设无向图G=V,E,如果存在顶点子集V??V,使p(G?V?)p(G),而且删除V?的任何真子集V??后(?V???V?),p(G?V??)=p(G),则称V?为G的点割集.若{v}为点割集,则称v为割点.理解:删除点后连通分支数可能增加,会减少吗?定义02

点割集(续)9{v2,v5}是点割集吗?例{v1,v4},{v6}是点割集,v6是割点.

定义边割集10设无向图G=V,E,E??E,若p(G?E?)p(G)且?E???E?,p(G?E??)=p(G),则称E?为G的边割集.01若{e}为边割集,则称e为割边或桥.02下图中,{e1,e2},{e1,e3,e5,e6},{e8}等是边割集,e8是桥,{e7,e9,e5,e6}是边割集吗?03

几点说明:11Kn无点割集(完全图)n阶零图既无点割集,也无边割集.若G连通,E?为边割集,则p(G?E?)=2若G连通,V?为点割集,则p(G?V?)?2

有向图的连通性12设有向图D=V,Eu可达v:u到v有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通(也称连通):基图为无向连通图有向边改为无向边后是连通图D单向连通:?u,v?V,u可达v或v可达uD强连通:?u,v?V,u与v相互可达强连通?单向连通?弱连通

有向图的连通性(续)13(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通每个顶点有进有出部分顶点有进有出

有向图的短程线与距离14u到v的短程线:u到v长度最短的通路(u可达v)u与v之间的距离du,v:u到v的短程线的长度若u不可达v,规定du,v=∞.性质:du,v?0,且du,v=0?u=vdu,v+dv,w?du,w注意:没有对称性

7.3图的矩阵表示15无向图的关联矩阵有向图的关联

显示全部
相似文档