离散数学7.2-3

离散数学7.2-37.2通路、回路与图的连通性简单通(回)路,初级通(回)路,复杂通(回)路无向连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥)智周万物-500强招聘-图问题1、钓鱼：有个人喜欢钓鱼。一天钓鱼归来，路上有人问他钓了多少条鱼，他答到：“有６条没头的，９条没尾的，８条半截的。”你知道他钓了多少条鱼吗？2、感觉：用第一感觉判断8＋8=91这个等式正确吗？说明理由。3、桌子上有2、1、6三张卡片，请问摆成一个什么数字可以让43整除？通路与回路定义给定图G=（无向或有向的），G中顶点与边的交替序列...

7.2通路、回路与图的连通性简单通(回)路,初级通(回)路,复杂通(回)路无向连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥)智周万物-500强招聘-图问题1、钓鱼：有个人喜欢钓鱼。一天钓鱼归来，路上有人问他钓了多少条鱼，他答到：“有６条没头的，９条没尾的，８条半截的。”你知道他钓了多少条鱼吗？2、感觉：用第一感觉判断8＋8=91这个等式正确吗？说明理由。3、桌子上有2、1、6三张卡片，请问摆成一个什么数字可以让43整除？通路与回路定义给定图G=（无向或有向的），G中顶点与边的交替序列=v0e1v1e2…elvl，(1)若i(1il),vi1,vi是ei的端点(对于有向图, 要求 vi1是始点,vi是终点),则称为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称为回路.(2)若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.(3)若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).通路与回路(续)说明: 表示方法①用顶点和边的交替序列(定义),如=v0e1v1e2…elvl②用边的序列,如=e1e2…el③简单图中,用顶点的序列,如=v0v1…vl④非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构成长度为2的圈.在无向简单图中,所有圈的长度3;在有向简单图中,所有圈的长度2.通路与回路(续)在两种意义下计算的圈个数①定义意义下在无向图中,一个长度为l(l3)的圈看作2l个不同的圈.如v0v1v2v0,v1v2v0v1,v2v0v1v2看作3个不同的圈.在有向图中,一个长度为l(l3)的圈看作l个不同的圈.②同构意义下所有长度相同的圈都是同构的,因而是1个圈.通路与回路(续)定理在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的初级回路.无向图的连通性设无向图G=,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R={|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短程线与距离u与v之间的短程线:u与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)点割集记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,p(GV)=p(G),则称V为G的点割集.若{v}为点割集,则称v为割点.点割集(续)例{v1,v4},{v6}是点割集,v6是割点.{v2,v5}是点割集吗？边割集定义设无向图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)=2若G连通，V为点割集，则p(GV)2点连通度κ与边连通度λ点连通度κ：最小的点割集点数；边连通度λ：最小的边割集边数。定理：对任何无向图G，有κ(G)≤λ(G)≤δ(G)有向图的连通性设有向图D=u可达v:u到v有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通(连通):基图为无向连通图D单向连通:u,vV，u可达v或v可达uD强连通:u,vV，u与v相互可达强连通单向连通弱连通有向图的连通性(续)定理(强连通判别法)D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法)D单向连通当且仅当D中存在经过每个顶点至少一次的通路(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通有向图的短程线与距离u到v的短程线:u到v长度最短的通路(u可达v)u与v之间的距离d:u到v的短程线的长度若u不可达v,规定d=∞.性质：d0,且d=0u=vd+dd注意:没有对称性智周万物-500强招聘-图论问题1、画线：在9个点上画10条直线，要求每条直线上至少有三个点？2、栽树：果园里有10棵苹果树，栽成５行，每行４棵。你知道是怎样栽的吗？7.3图的矩阵表示无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵无向图的关联矩阵定义设无向图G=,V={v1,v2,…,vn},E={e1,e2,…,em},令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).性质有向图的关联矩阵定义设无环有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em},令则称(mij)nm为D的关联矩阵，记为M(D).有向图的关联矩阵(续)性质(4)平行边对应的列相同定义设有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.性质有向图的邻接矩阵D中的通路及回路数定理设A为n阶有向图D的邻接矩阵,则Al(l1)中元素为D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.D中的通路及回路数(续)例有向图D如图所示,求A,A2,A3,A4,并回答诸问题：(1)D中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)D中长度小于或等于4的通路为多少条？其中有多少条回路？推论设Bl=A+A2+…+Al(l1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.例(续)长度通路回路合计508181211331414173有向图的可达矩阵定义设D=为有向图,V={v1,v2,…,vn},令称(pij)nn为D的可达矩阵,记作P(D),简记为P.性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.有向图的可达矩阵(续)例右图所示的有向图D的可达矩阵为

                    本文档为【离散数学7.2-3】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

离散数学7.2-3

你可能还喜欢