网络最优化讲义武汉大学

《网络最优化讲义武汉大学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《网络最优化》讲义黄崇超2009-12-2143第一章图的基本概念§1.1图与网络一、图的基本概念定义1.1图是由非空有限集合及中某些元素的无序对的集合所构成的二元组，记为。中元素称为顶点，可用平面上的点表示。中的元素均为中元素的无序偶对，任取，若，则将点与之间连一条边，这样中元素就可用连接中相应点的边表示，故称为边集。这样，一个图（数学结构）就可借助点与边的直观图形表示出来。这种表示是如此的方便，以至于在很多情况下，就将该数学结构等同于这种图形表示，而把这种数学结构称为图，图论也因此而得名。若，也

2、就是在与之间存在一条边，则称与相邻，而与分别称为边的两个端点，又称边与顶点、关联。若某个顶点同时与边、关联，则称边与相邻。下面给出了图论中的若干术语：环：边的两个端点重合；重边：某两条边的端点是同一对顶点；简单图：不含环和重边的图称为简单图；图的阶数：（中所含顶点的个数）；顶点的度数：与相关联的边的数目，记为定理1.1设是一个图，则奇顶点与偶顶点：度数为奇的顶点称为奇点；为偶的成为偶点。推论任何图中奇点的个数必为偶数。下面给出子图的概念定义1.2设，是两个图。若，，则称是的子图，记为。若，，则称是的

3、由顶点集导出的子图，简称导出子图；若，，则称是的生成子图（或称支撑子图）。几类特殊图：完全图，二分图（二部图或偶图），完全二分图。二分图：当且仅当不包含奇圈。Euler图：存在包含图中一切边的闭迹（Euler闭迹）。43Hamilton图：存在包含中一切点的圈（Hamilton圈）。二、连通性途径（Walk）：图中点、边交错序列称为一个途径。迹（Trail）：若一个途径中，没有相同的边，则称为迹。路（Path）：若一个途径中，没有相同的顶点，则称为路。注：在简单图中，途径既可用顶点序列表示，也可用边

4、序列表示。闭途径（ClosedWalk）：回路闭迹（ClosedTrail）：圈（ClosedPath）：奇圈、偶圈定义1.3若图中任意一对顶点之间，都存在一条路，则称图是连通的，否则称为不连通的。若不连通，那么的最大连通子图称为的连通分支。三、有向图定义1.4有向图是由非空有限集合及中某些元素的有序对的集合构成的二元组，记为。和无向图类似，中元素也可用平面上的点来表示，故称为顶点集。而中元素均为中元素的有序对，设，若，则用从出发，终止于的有向边（弧）来表示。因此，有向图可用点与弧的图形来直观表示。

5、若，且，那么称与相邻，称为的起点，称为的终点，并称与、相关联。若两条弧、关联于同一顶点，则称、两条弧相邻。顶点出弧：以顶点为起点的弧；顶点入弧：以顶点为终点的弧；出度：以顶点为起点的弧的条数；入度：以顶点为终点的弧的条数；定理1.2设是一个有向图，则简单图：无环、无重边的图称为简单图。途径（Walk）：和无向图一致；有向途径（DirectedWalk）：所有弧都指向同一方向；43路（Path）：不包含重复顶点的途径；前向弧：与路从起点到终点的方向一致的弧称为前向弧、正向弧；反向弧：与路从起点到终点的

6、方向相反的弧称为后向弧、或反向弧；有向路：路中所有弧的方向都一致，则称为有向路；连通：有向图的任两点间均存在一条路；强连通：有向图的任两点，间存在一条从到的有向路。有向图与无向图的关系：若将无向图的一条边视为两条方向相反的弧，则无向图可视为一种特殊的有向图。而若忽略有向图的所有弧的方向，则得到一个无向图，称为该有向图的基础图。四、图的矩阵表示1.邻接矩阵①称是无向图的邻接矩阵，其中由于无向图中顶点的邻接关系是对称的，故邻接矩阵是一个对称矩阵，有因为元素均为0，1，故它是一个对称的布尔矩阵。注：邻接矩

7、阵每行元素之和恰为该行所对应顶点的度数。②称是有向图的邻接矩阵，其中可见，有向图的邻接矩阵一般不对称。注：有向图的邻接矩阵每行元素之和等于该行所对应顶点的出度；而矩阵每列元素之和等于该列所对应顶点的入度。2.关联矩阵①称为无向图的关联矩阵，其中注：每行元素之和为对应的顶点的度数，而每列恰有两个为1的元素。②称为有向图的关联矩阵，其中43注：每一行对应一个顶点，每一列对应一条弧；每一行中的-1的个数等于该点的入度，而1的个数等于该点的出度；每一列中恰有两个元素非零：一个为1，一个为-1。五、网络定义1

8、.5如果对图中的每条弧（边）都赋予一个或多个实数，则得一个有向网络（无向网络）。网络实际上就是一个赋权图。§1.2网络最优化问题一、最小生成树问题在无向网络中求一棵权最小的生成树。二、最短路问题给定无向网络中的两点，求两点间的一条最短路，或在有向网络中，给定一个起点，一个终点，求一条由起点到终点的最短路。三、最大流问题给定一个有向图，对于中的每段弧，定义一个实数，称为的容量。在中指定两点与，求到的最大流量。四、最小费用流问题五、最小费用循环流问题六、匹配问题七、中国邮