图论论文

图与网络优化期末论文题目：图论在给水调度模拟中的应用学院：信息与管理科学学院学号：1110110031姓名：安苗苗班级：金融数学11-2班指导老师：王亚伟2014年5月31日1图论在给水调度模拟中的应用摘要：本文提出了水厂分界线的表达方法：使用混水节点和混水管来划分水厂的分界线，类比同位素示踪法给出了可行的寻找混水节点和混水管的方法。并通过使用图论的基本原理和算法给出了程序算例并全部给出了证明。通过对大量实测数据的分析，发现了数据的误差并提出了误差分析和处理的方法。给出了通过逻辑操作进行的数据分析方法并给出了分析的结果。对不同时刻的采样数据做了大量的分析并给出了分析结果提出了定性分析的绝对混水节点和混水节点包络线的概念和每个节点在一个周期的混水概率。并进一步给出了定量分析的不同时刻的混水比例。强调了数据可视化的思想并通过MATLAB实现了数据可视化并给出了全部数据的可视化结果。使用虚拟地图的方式标明了混水管的位置和地理信息。利用VC和MATLAB各自的长处，并利用文本文件做VC主程序和MATLAB数据处理、图象显示程序的接口，从而避免了复杂的VC与MATLAB混合编程。本文运用了图论的基本理论并对赋权有向图、代价邻接矩阵、有向图的连通性等概念做了扩展。给出一些新的定义方法和定理并全部给予证明。提出了新的给水网络的定量算法并在对算法的阐述的同时也给出了算法的正确性和健壮性证明，全部算法是作者独立的工作成果。本文得到的结论和程序可以直接供工程实际使用。在对源程序做适当的修改以后可以作为一个子系统嵌入水厂的管理系统，为水厂的调度提供参考数据。关键词：给水管网区域分界线混水管混水节点示踪法模拟图论方法数据可视化图的遍历一、问题的提出随着现代科学技术的快速发展，作为系统工程指标之一的可靠性指标也越来越受到重视，并极大地改善了各种系统的工作性能[1]。在现代的生活和工业给水技术中，人们为了提高管道的可靠性，便于在出现灾害、故障、检修和扩建的时候不至于影响大范围的区域，常常把供水管道布置成网状。甚至在给水管网内还有不止一个水泵、水塔和水厂。所以整个供水区域的网络拓扑模型变得极为复杂。在解决管网的优化，给水调度，为管网的维修和扩建提供原始资料，对水塔、水泵、管道的性能做评测以及对各个水厂的效益、服务质量做评测，往往需要知道在一个时刻不同水厂的供水分界线的问题。二、水和管网的水力学特性建模1、密度：一般情况下水的密度随压强和温度变化的变化量很小，可看作常数。2、粘滞性：水不是理想的牛顿流体，能够由于抵抗内摩擦的缘故而做功耗能，这是水管中水头高度损失的主要原因。3、连续性：对于一个封闭的空间区域和不可压流体，任意时间段流进、流出的体积相同。4、能量守恒方程[2]（伯努利方程）：2lmhgugpzHgugpz2222211125、动量方程[2]：)(1122vvQdtF6、管网的克契霍夫方程[1]：1）节点方程（不可压缩流体的连续性方程在管网的体现）：0iijQq式子中i为节点编号，ijq表示连接节点i的各个管段的流量iQ表示节点i的流量。ijq和iQ都以流进节点为正，否则为负。2）节点方程（不可压缩流体的能量守恒方程在管网中的体现）：0kijHh式子中ijh属于基环k的管段的水头损失；kH属于基环k的闭合压差或者增压、减压装置产生的水压差。三、图论的有关理论：1、向图的定义[3]：有向图),(EVD是由顶点集合V和有向边集合E组成的。有向边（弧）的顶点是有序对ds,，在s至d的有向边ds,中，s称为顶点，d成为终点。2、有向图的表示[3]：表示图的最简单直接的方式就是邻接矩阵。假定图中有向图G的顶点可以以某种方法可以排成序nvvvv3,21,，则G的邻接矩阵是个nn阶的布尔逻辑矩阵。true当iv为起点，jv为终点的时候]][[jiAdjfalse否则3、赋权有向图[3]：在实际的模型中，往往不仅仅要表示出边的方向、边还有其他的属性（譬如在给水管网中，管道还有流量、长度、半径、粗糙系数等信息），即边是有权的。所以我们把邻接矩阵改造一下，把逻辑值改为具体的表达了权的数值，称其为代价邻接矩阵，就可以表达出边或者节点的权数。当然，如果想表达更多的权，就必须采用更加新的表示方法了。4、扩展的代价邻接矩阵：当顶点和边有多种属性的时候，我们可以把每个属性都做成一个代价邻接矩阵。然后按照一种顺序把这些代价邻接矩阵3组成一个三维的数组，该数组的每个切片是一个代价邻接矩阵。在数据结构中，可以更加方便地用结构体实现（代价邻接矩阵的每个元素是一个结构体）。5、有向图的环：如果从一个顶点出发顺着一条有向路径能回到该节点，则这条有向路径称为环。6、有向图的连通性[3]：在对图进行遍历的时候，有向图和无向图的最大的区别就是除非其是强连通的，否则不能保证一次遍历能访问所有的节点。7、完全有向图：对于具有n个节点的有向图，弧数最多可达)1(nn条。具有最大弧数的图称为完全有向图。完全有向图一定有环，证明略。8、有向图的有向连通性[3]：如果把所有没有父节点的节点称为根节点，则如果一个有向图有n个根节点就一定需要且只需要n次遍历就可以访问完所有的节点。证明：充分性：如果一个有向图需要且只需要n次遍历才可以访问所有的节点，则至少该图有n个节点没有父节点，至多也只有n个节点没有父节点。所以该图至少有n个根节点。必要性：如果一个有向图有n个根节点，由于根节点没有父节点，所以至少要有n次从根节点开始的遍历才可以访问所有的根节点。9、子图[3]：如果有两个图),(EVG和),(EVG，且EEVV,，则G是G的子图。四、水力管网的模型的建立：管网的拓扑性质可以用图论的基本原理来分析。图由“弧”和“顶点”两部分组成，给水管网的拓扑模型可以抽象认为是由节点（用户和水厂）以及弧（管段）组成的有向图，并且是无圈无环的有向图（由克契霍夫的环路定律和能量耗散可知不会有圈和环）。边的方向就是水流的方向。由于管道和节点都有很多属性，这样我们就把两个水厂的供水区域管网抽象成了无圈无环的多属性赋权有向图。五、不同水厂的水分界线问题的描述：自然而然我们很容易想到所谓的分界线就可以用混合了两个（或者两个以上）水厂的水的节点和管道来描述。在现代的科学技术中，人们常常用同位素来标识流体进行示踪。我们采用同样的方法假想在水中加入这样的物质，并符合4点假设：假设1、该示踪物质只会随水流的流动而向下游流动，不能逆着水流扩散。假设2、该示踪物质每到一个管道或者一个节点都能和水充分混合，即如果一个节点出现该示踪物质则该节点所有的下游节点都一定有该示踪物质。假设3、这种示踪的物质可以被传感器经济而方便地检测出来，并且该示踪物质对人体没有危害。假设4、这两种示踪物质混合后其性质不会发生变化。我们现在设想这两个水厂的水中各自搀杂了一种符合上面4条假设的物质（我们为了表述的方便不妨称甲水厂搀杂的物质为甲物质，而乙水厂搀杂的物质称为乙物质），那么显然如果一段水管中的水如果全部来自一个水厂，4则只可以检测出一种物质。显然只能检测出甲物质的水管就是甲水厂的供水区域；只能检测出乙物质的水管就是乙水厂的供水区域；而如果有一个区域的水管中同时能检测出这两种物质，显然这段水管同时使用了来自两个水厂的水（这些同时能检测出两种物质的节点我们称为混水节点，能同时检测出两种物质的水管我们称为混水管，且混水管是个矢量（有向边的方向）。显然，由前面的四点假设我们可以得到以下结论：1、所有混水管的终点都是混水节点，所有混水节点都一定至少是一个混水管的终点。2、所有顶点是混水节点的水管都一定是混水管，所有混水管的顶点都一定是混水节点。3、每个节点的所有的流量（包括节点的用水或者供水量）之和为0（水的连续条件）。4、由假设1、2、3我们可以得到混水管的拓扑规律如下：混水管是一定单连通域（相互贯通的），非混水管也一定是单连通域。（直观上也是很容易解释的，因为水是连续流动的）。这样，我们用水管两端的节点来描述水管的方法就可以方便地描述出混水管。所以如果我们想找出一个界线来区分这两个水厂的供水区域，即问题中所提出的“分水线”，最好的就是使用混水管了，混水管就把区域划分成两部分，一边是甲水厂的供水区域，另一端就是乙水厂的供水区域。而混水管和混水管所连接的这些节点就构成了分界线。六、模型的建立当然，我们不可能真的去在自来水中加入类似于前面提到的物质。但是那种方法显然是一种很好的想法。在计算机技术发达的今天，虚拟实验已经成为科学工程实验的主要手段之一，譬如核物理学家们就可以通过数值模拟来减少核试验的次数，极大地减少了投资、工期和对环境的危害。流体力学也用数值模拟部分地代替风洞实验，取得很好的效益。所以我们可以使用计算机模拟来完成上面提到的想法。在计算机上完成我们的虚拟实验。这样我们就不必要真的在水中加入什么物质，而直接地通过传感器来测量一定时间间隔下的采样点的水压强（水头高度H来描述），单位时间的流量Q，和水厂水管布局的地理信息系统信息（用水节点的坐标，各个管段的管半径、长度），运用计算机虚拟技术就可以很方便地动态、实时地计算出分水界线的位置，直观、清晰、代价小。还可以用来作为反馈来控制供水。我们已经通过传感器得到了上面所提到的数据（见附件一），那么现在要做的事情就是运用水的力学特性来利用上面的数据建立寻找混水管的的方法。俗话说：人往高处走，水往低处流，在力学的概念上，这个“高”可以用更加本质的物理量“水头高度”来衡量。显然，用一段水管连接两个不同水头高度的节点水显然会往水头高度低的节点流动。换句话说就是沿着水流动的方向水头高度是逐渐降低的（管道的阻尼造成沿程水头损失）。这样，我们可以认为如果我们真的在水管中加入我们提到的那种物质，则那种物质一定是顺着压强降低的方向扩散（顺水流而下）。这样我们就可以利用我们前面得到的测量数据，让计算机从一个根节点（水厂）开始搜寻所有与该节点相连接的有向边（水管）中方向（水流方向）是向下（流出）的边，然后“顺藤摸瓜”地找到下一个节点，在节点上做个逻辑标志来标识该水厂的水流过该节点，然后继续向下搜寻，并且继续在水流经过的节点上做标志。那么显然当我们遍历了这个图以后就5可以找出所有该水厂的水流经的节点和管道。显然，当我们对甲、乙两个水厂都这样遍历一遍以后就可以把所有的节点做上标志。运用我们前面提到的思想，只有甲厂标志的节点就属于甲厂的供水区域，只有乙厂的标志的节点就属于乙厂的供水区域，而同时拥有两个标志的节点就是同时使用两个水厂的水。以该节点为顶点的水管就一定是混水管。运用本文开头所描述的混水管和混水节点的关系就可以很方便地通过混水节点来找到混水管。这样显然我们就把实际的供水区域的管网抽象成了一个有向图。当我们分别从各个根节点（水厂）遍历一次这个有向图并把是否经过该节点作为逻辑值（真为1，假为0）记录到节点中去。这样，每个节点都有两个逻辑值。然后我们再把每个节点的这两个逻辑值进行与操作，再存入节点。显然，如果这两个逻辑值求与以后的结果还为真的话（两个值都为1），那么这个节点就是混水点。到此为止，我们已经把分界线的寻找转化成了有向图的遍历问题，用计算机建立起该有向图的模型，调用实际测得的数据我们就可以通过模拟的方法找到得到解。七、模型的求解a)、模型的算法分析：电子计算机求解管网问题的时候，首先考虑用哪种形式可以比较方便地将管网图形的信息输入计算机，方法是多种多样的，但是还必须考虑以下条件：1）、在内容上，信息是充分具体的，而在存储上存储量尽可能地小。2）、在形式上，要便于计算机的调用，便于信息的录入，并且同时还便于以后维修、扩建的时候的更改。有向图的计算机描述有很多种方法:有邻接矩阵方法、邻接多重表示方法、边表示法等等。我们为了程序有更好的扩展性，采用了结构体的概念：代价邻接矩阵的每一个元素都是一个结构体，可以有多个成员，每个成员都是该结构体的一种属性，其中有一个成员表达了判断逻辑。这样就可以把代价邻接矩阵扩展到了对具有多个属性的情况，良好的通用