离散数学图的基本概念PPT讲稿.ppt
《离散数学图的基本概念PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《离散数学图的基本概念PPT讲稿.ppt(48页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1第1页,共48页,编辑于2022年,星期日通路与回路通路与回路 n定义定义 n给给定定图图G=(无无向向或或有有向向的的),设设G中中顶顶点点与与边边的的交交替序列替序列=v0e1v1e2elvl:若若 i(1 i l),vi 1 和和 vi是是ei的的端端点点(对对于于有有向向图图,要要求求vi 1是是始始点点,vi是是终终点点),则则称称 为为通通路路,v0是是通通路路的的起起点点,vl是是通通路的终点路的终点,l为为通路的长度通路的长度.又若又若v0=vl,则称,则称 为为回路回路.n理理解解:通通路路或或回回路路是是点点与与边边的的交交替替序序列列,边边的的端端点点恰好是前后的两个点
2、恰好是前后的两个点n长度边数长度边数2第2页,共48页,编辑于2022年,星期日若若通通路路(回回路路)中中所所有有顶顶点点(对对于于回回路路,除除v0=vl)各各异异,则则称称为为初初级级通通路路(初初级级回回路路).初初级级通通路路又又称称作作路路径径,初初级级回回路路又称作又称作圈圈.n路上各点不重复路上各点不重复若若通通路路(回回路路)中中所所有有边边各各异异,则则称称为为简简单单通通路路(简简单单回回路路),否则称为否则称为复杂通路复杂通路(复杂回路复杂回路).n路上各边不重复路上各边不重复3第3页,共48页,编辑于2022年,星期日通路与回路通路与回路(续续)说明说明:n在无向图中
3、,环是长度为在无向图中,环是长度为1 1的圈的圈,两条平行边构成长度为两条平行边构成长度为2 2的圈的圈.无向简单图中无向简单图中,所有圈的长度所有圈的长度 3 3n在有向图中,环是长度为在有向图中,环是长度为1 1的圈的圈,两条方向相反边构成长度两条方向相反边构成长度为为2 2的圈的圈.在有向简单图中在有向简单图中,所有圈的长度所有圈的长度 2.2.4第4页,共48页,编辑于2022年,星期日通路与回路通路与回路(续续)n定理定理 在在n阶阶图图G中中,若若从从顶顶点点vi到到vj(vi vj)存存在在通通路路,则则从从vi到到vj存在长度小于等于存在长度小于等于n 1的的通路通路.n推论推
4、论 在在n阶图阶图G中,若从顶点中,若从顶点vi到到vj(vi vj)存在通路,则从)存在通路,则从vi到到vj存在长度小于等于存在长度小于等于n 1的的初级通路初级通路.n定理定理 在一个在一个n阶图阶图G中,若存在中,若存在vi到自身的回路,则一定存在到自身的回路,则一定存在vi到自身长度小于等于到自身长度小于等于n的回路的回路.n推论推论 在一个在一个n阶图阶图G中,若存在中,若存在vi到自身的简单回路,则一定到自身的简单回路,则一定存在长度小于等于存在长度小于等于n的初级回路的初级回路.5第5页,共48页,编辑于2022年,星期日无向图的连通性无向图的连通性 n设无向图设无向图G G=
5、,u u与与v v连通连通:u u与与v v之间有通路之间有通路.n规定规定u u与自身总连通与自身总连通.连通关系:连通关系:R R=|u u,v v V V且且u u v v 是是V V上的等价关系上的等价关系连通图连通图:平凡图平凡图,或者任意两点都连通的图或者任意两点都连通的图连连 通通 分分 支支:V V关关 于于R R的的 等等 价价 类类 的的 导导 出出 子子 图图 设设V V/R R=V V1 1,V V2 2,V Vk k,G G V V1 1,G G V V2 2,G G V Vk k 是是G G的的连连通分支通分支,n连通分支个数记作连通分支个数记作p p(G G)=)
6、=k.k.nG G是连通图是连通图 p p(G G)=1)=16第6页,共48页,编辑于2022年,星期日短程线与距离短程线与距离nu与与v之间的短程线之间的短程线:u与与v之间长度最短的通路之间长度最短的通路nu与与v之间的距离之间的距离d(u,v):u与与v之间短程线的长度之间短程线的长度若若u与与v不连通不连通,规定规定d(u,v)=.性质:性质:n d(u,v)0,且且d(u,v)=0 u=vn d(u,v)=d(v,u)(对称性)(对称性)n d(u,v)+d(v,w)d(u,w)(三角不等式(三角不等式)7第7页,共48页,编辑于2022年,星期日点割集(点割集(v v点;点;V
7、V点集;点集;e e边;边;E E变集)变集)n记 Gv:从G中删除v及关联的边 GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边n定义 设 无 向 图 G=,如 果 存 在 顶 点 子 集 VV,使p(GV)p(G),而且删除V的任何真子集V后(VV),p(GV)=p(G),则称V为G的点割集.若v为点割集,则称v为割点.理解:删除点后连通分支数可能增加,会减少吗?8第8页,共48页,编辑于2022年,星期日点割集点割集(续续)例例 v1,v4,v6是点割集是点割集,v6是割点是割点.v2,v5是点割集吗?是点割集吗?9第9页,共48页,编辑于2022年,
8、星期日边割集边割集n定义定义 设设 无无 向向 图图 G=,EE,若若 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第10页,共48页,编辑于2022年,星期日n几点说明:几点说明:Kn无点割集(完全图)无点割集(完全图)n阶零图既无点割集,也无边割集阶零图既无点割集,也无边割集.若若G连通,连通,E 为边割集,则为边割集,则p(G E)=2若若G连
9、通,连通,V 为点割集,则为点割集,则p(G V)211第11页,共48页,编辑于2022年,星期日有向图的连通性有向图的连通性 n设有向图设有向图D=u可达可达v:nu到到v有通路有通路.规定规定u到自身总是可达的到自身总是可达的.n可达具有自反性和传递性可达具有自反性和传递性D弱连通弱连通(也称连通也称连通):n基图为无向连通图基图为无向连通图n有向边改为无向边后是连通图有向边改为无向边后是连通图D单向连通单向连通:n u,v V,u可达可达v 或或v可达可达u D强连通强连通:n u,v V,u与与v相互可达相互可达n强连通强连通单向连通单向连通弱连通弱连通 12第12页,共48页,编辑
10、于2022年,星期日有向图的连通性有向图的连通性(续续)(1)(2)(3)例例 下图下图(1)强连通强连通,(2)单连通单连通,(3)弱弱连通连通每个顶点有进有出部分顶点有进有出13第13页,共48页,编辑于2022年,星期日有向图的有向图的短程线与距离短程线与距离nu到v的短程线:u到v长度最短的通路(u可达v)nu与v之间的距离d:u到v的短程线的长度若u不可达v,规定d=.性质:n d0,且d=0 u=vn d+d d 注意:没有对称性14第14页,共48页,编辑于2022年,星期日7.3 图的矩阵表示图的矩阵表示 无向图的关联矩阵无向图的关联矩阵有向图的关联矩阵有向图的关联矩阵有向图的
11、邻接矩阵有向图的邻接矩阵有向图的可达矩阵有向图的可达矩阵 15第15页,共48页,编辑于2022年,星期日无向图的关联矩阵无向图的关联矩阵定定义义 设设无无向向图图G=,V=v1,v2,vn,E=e1,e2,em,令令mij为为vi与与ej的的关关联联次次数数,称称(mij)n m为为G的关联矩阵的关联矩阵,记为,记为M(G).性质性质16第16页,共48页,编辑于2022年,星期日v1v2v4v3e1e2e3e4e5关联次数为可能取值为关联次数为可能取值为0,1,217第17页,共48页,编辑于2022年,星期日无向图的相邻矩阵无向图的相邻矩阵v1v2v4v3e1e2e3e4e5(1)相邻矩
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 基本概念 PPT 讲稿
限制150内