环境系统第3讲剖析.ppt

2005-8-3 环 境 系 统 分 析 第 3 讲 主讲: 李明俊 教授 2006.5.8 三、图与网络方法 1、图的概念 定义：无向图G=（V、E、φ），包含有顶点集合V，边的集合E，以及顶点与边之间的关系φ，有时无向图直接写成G=（V、E） 这样做便于将图用数学集合形式表达出来，反之亦然。环境问题中河网、管网、工艺路线等均可通过这些图的集合表达方式来描述，以便进一步分析处理。 例：右图中，G=（V、E、φ） 其中：V={V1、V2、V3、V4} E={e1、e2、e3、e4、e5、e6} φ：e1=＜V1、V2＞ e2=＜V1、V4＞ e3=＜V2、V3＞ e4=＜V3、V4＞ e5=＜V1、V3＞ e6=＜V2、V4＞ 此处＜Vi、Vj＞表示以Vi、Vj为两端的无向边。 定义：有向图G=（V、E、ψ）,与无向图的区别在于ψ与φ ψ：ek=（Vi、Vj），以Vi为起点，Vj为终点. φ：ek= ＜Vi、Vj ＞ ，无始终点之说。 有向图的边带箭头，（对应于实际中的河流水流方向，管道中水流方向等） 2、点与边的关联关系 定义：设G=（V、E）是无向图，若顶点Vk是G的一个顶点，且不存在自身回路，则Vk点的线度是G中以Vk为端点的边数，记为d (Vk),若存在自身回路，则自身回路的顶点Vk，其线度d (Vk)也包括自身回路的边，且记两次。 例：左图中 d (V2)=3 d (V3)=3 d (V1)=4 (存在自身回路e3) 例：右图中 d+ (V1)=1 d- (V1)=1 d (V1)=2 特别对V3，有： d+ (V3)=2 ，d- (V3)=2 d (V3)=4 自身回路以V3为始点，又以V3为终点。 3、图的矩阵表示法 矩阵是研究图论的一种有力工具，特别是利用计算机来研究有关图的算法时，首先遇到的问题是如何让计算机来识图，这不得不借助矩阵。 我们暂且不讨论两顶点之间存在平行的两条边的情况。 （1）邻接矩阵 定义：对于有向图G=（V、E），构造矩阵 A=(aij)nxn 其中 ：n为图G的顶点数，称矩阵A为图G的邻接矩阵。 那么，邻接矩阵运算的含义是什么呢？ 先看：A2=A·A = 其中a ij (2) =∑aik·akj 当且仅当aik=akj=1时，aik· akj≠0，即从Vi到Vj 有“道路”相通（Vi→Vk → Vj），因此，a ij (2)的值表示从V i出发经过某一中间站Vk然后到达Vj的路径数目，形象地说，a ij (2)是从Vi出发两步到达Vj的路径数目。 同样地，A3= A2·A=A·A2=（aij(3)） 其中： （aij(3)）=∑aik(2)·akj 表示从Vi出发三步到达Vj的路径数目。 一般地， aij(k)表示从Vi出发k步到达Vj的道路数目。 不难理解，从Vi点出发不超过k步（包括1步、2步……k步）到达Vj点的道路数共有： B=（bij）=A+A2+ A3+……+ Ak=∑AL  要想弄清楚一个图中任意两点间有无道路相通,只须计算： Bn=（bij(n)）nxn=A+A2+ A3+……+ An 若bij(n)=0， 则从Vi点到Vj点无路，否则有路。 邻接矩阵描述图G中顶点与顶点的关系，而后讨论的关联矩阵将描述图G中顶点与边的关系。 （2）关联矩阵（衔接矩阵） 定义：图G=（V、E）是有向图，其中 V={V1、V2、……、Vn},E={e1、e2、……em} 令B=(bij)nxm bij是第i个顶点与第j条边的关系，则称矩阵B为有向图G的关联矩阵。 用n个节点将河网分成m个河段，一般将符合下列条件之一者，可视为节点： (1)点源排放口 (2)汇流、分流点 （3）取水口 （4）人工曝气点 图（b）所示河网网络图中，节点数n=8，边（河段）数m=9，其关联矩阵为8×9阶的矩阵，即： 讨论： ①关联矩阵表示图的节点与边的衔接关系，因此某一行的非零元素的数目就是与相应的节点所衔接的边数。 ②关联矩阵中每一列只有+1和-1两个非零元素，因此，其各个行向量总和必为零，这表明关联矩阵B的秩小于节点数n，即B是奇异阵或者说关联矩阵的行向量是线性相关的。