《图与网络理论》.ppt

该【《图与网络理论》 】是由【相惜】上传分享，文档一共【84】页，该文档可以免费在线阅读，需要了解更多关于【《图与网络理论》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第七章图与网络理论例1哥尼斯堡七桥问题ABCDABCD哥尼斯堡七桥问题哥尼斯堡城中有一条河,河上有七座连结着两岸和河中的两个小岛,。问题是一个人能否从一点出发,经过每座桥一次且仅一次,回到原出发点。,就是顶点和边的集合,点的集合记为V={v1,v2…,vn},边的集合记为E={e1,e2…,em},vi称为图的顶点,ej称为图的边,假设边ej联结vs和vt,那么记为(vs,vt),即ej=(vs,vt)。那么图可以表示为:G=(V,E),点代表被研究的事物,边代表事物之间的联系,因此,边不能离开点而独立存在,每条边都有两个端点。在画图时,顶点的位置、边和长短形状都是无关紧要的,只要两个图的顶点及边是对应相同的,那么两个图相同。2精选课件有些图的边带有方向,这样的图称为有向图。而边不带方向的图称为无向图。。。,假设e=(u,v),那么称u,,〔v及点〕的关联边。假设边ei,ej有一个公共的端点u,称边ei,ej相邻。假设边e的两个端点是同一顶点,那么称此边为环。假设两顶点之间有多于一条的边,那么这些边称为多重边。,e7是环,e1,e2是多重边。一个不含环和多重边的图称为简单图。含有多重边的图称为多重图。我们这里所说的图,如不特别指明,都是简单图。4精选课件以点v为端点的边的条数称为点v的度,记作d(v),(v1)=3,d(v3)=1。度为零的点称为弧立点,度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点,度为偶数的点称为偶点。不难证明:在一个图中,顶点度数的总和等于边数的2倍,奇顶点的个数必为偶数。链:由两两相邻的点及其相关联的边构成的点边序列;如:v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vn;v0,vn分别为链的起点和终点;简单链:链中所含的边均不相同;初等链:链中所含的点均不相同;圈:在链中,假设v0=vn那么称该链为圈;连通图:图中任意两点之间均至少有一条链相连,5精选课件第二节树树是一类结构简单而又十分有用的图。一个不含圈的连通图称为树。设图T=(V,E),含有n个顶点,那么以下命题是等价的。〔1〕T是树。〔2〕T的任意两顶点之间,有唯一的链相连。〔3〕T连通且有n-1条边。〔4〕T无圈且有n-1条边。〔5〕T无圈但添加一条边得唯一一圈。〔6〕T连通但去掉一条边那么不连通。6精选课件给定图G=(V,E),假设V’?V,E’?E,并且E’中的边的端点都属于V’,那么称G’=(V’,E’)是G的一个子图。特别地,假设V’=V,那么称G’为G的支撑子图。设T是图G的一个支撑子图,假设T是一树,那么称T是G的一个支撑树。给定图G=(V,E),对于G的每一条边,可赋以一个实数w(e),称为边e的权,图G连同它边上的权称为赋权图。赋权图在图论的应用中经常出现。根据实际问题的需要,权可以有不同的实际含义,它可以表示距离、流量、时间、费用等。7精选课件给定图G=(V,E),设T=(V,E’)是G的一个支撑树,定义树T的权为即支撑树T上所有边的权的总和。图G的最小支撑树就是图G中权最小的支撑树。求图G的最小支撑树的方法是建立在求图G的支撑树根底上,只需在求图G的支撑树的算法再加适当限制。因此,求最小支撑树方法也有相应的破圈法;避圈法。8精选课件例2 分别用破圈法,。