资源描述：
《《图与网络理论》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章图与网络理论例1哥尼斯堡七桥问题ABCDABCD哥尼斯堡七桥问题 哥尼斯堡城中有一条河，河上有七座连结着两岸和河中的两个小岛，如图7.1所示。问题是一个人能否从一点出发，经过每座桥一次且仅一次，回到原出发点。图7.11第一节 图的基本概念所谓图，就是顶点和边的集合，点的集合记为V={v1,v2…,vn}，边的集合记为E={e1,e2…,em}，vi称为图的顶点，ej称为图的边，若边ej联结vs和vt，则记为(vs,vt)，即ej=(vs,vt)。则图可以表示为：G=(V,E)，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点
2、而独立存在，每条边都有两个端点。在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。2有些图的边带有方向，这样的图称为有向图。而边不带方向的图称为无向图。图7.7是一个无向图。图7.8是一个有向图。v1v5v2v3v4e1e2e3e4e6e5e7图7.7图7.83在一个图中，若e=(u,v)，则称u,v是边e的端点．并u,v称相邻．称e是点u（v及点）的关联边。若边ei,ej有一个公共的端点u，称边ei,ej相邻。若边e的两个端点是同一顶点，则称此边为环。若两顶点之间有多于一条的边，则这些边称为多
3、重边。如图7.7中，e7是环，e1,e2是多重边。一个不含环和多重边的图称为简单图。含有多重边的图称为多重图。我们这里所说的图，如不特别指明，都是简单图。4以点v为端点的边的条数称为点v的度，记作d(v),如图7.7中d(v1)=3,d(v3)=1。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。不难证明：在一个图中，顶点度数的总和等于边数的２倍，奇顶点的个数必为偶数。链：由两两相邻的点及其相关联的边构成的点边序列;如:v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,
4、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’中的边
5、的端点都属于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的最小支撑树的
6、方法是建立在求图G的支撑树基础上，只需在求图G的支撑树的算法再加适当限制。因此，求最小支撑树方法也有相应的破圈法；避圈法。8例2分别用破圈法，避圈法求图7.17的最小支撑树。图7.17v1v5v2v3v42v6v7v834346236645859v1v5v2v3v42v6v7v83434623664585解 破圈法10v1v5v2v3v42v6v7v83434623664585避圈法：11第三节 最短路问题最短路问题，一般来说就是从给定的赋权图中，寻找两点之间权最小的链（链的权即链中所有边的权之和）。许多优化问题都需要求图的最短路，如选址、管
7、道铺设、设备更新、整数规划等问题。由于所求问题不同，需要使用不同的方法。下面我们介绍常用的算法。一、Dijkstra算法Dijkstra算法是求赋权有向图中，某两点之间最短路的算法。实际上，它可以求某一点到其它各点的最短路。它是Dijkstra于1959年提出。目前被认为是求非负权最短路的最好的算法。12Dijkstra算法的基本思想是基于以下原理：若vs,vl,…,vj是vs到vj的最短路，vi是此路中某一点，则vs,vl,…,vi必是从vs到vi的最短路。此算法的基本步骤是采用标号法，给图G每一个顶点一个标号。标号分两种：一种是T标号，一
8、种是P标号。T标号也称临时标号，它表示从vs到这一点的最短路长度的一个上界，P标号也称固定标号，它表示从vs到这一点的最短路的长度（这里最短路长度是指这条路上个边权
