1。4 图与网络流相关知识

1。4。1 图的概念

   定义 1。4。1。1 一个图定义为一个偶对,记作,其中

   (1)是一个非空集合,其中的元素称为顶点;

   (2)是无序积中的一个子集合,其中的元素称为边或弧;

注:集合中的元素可以在子集合中出现不止一次。

    我们分别用和表示图的顶点集合与边的集合。如果和都是有限集合,则称为有限图;否则称为无限图。

定义 1。4。1。2 一个有向图定义为一个偶对,其中

   (1)是个非空集合,其元素称为顶点;

   (2)是有序积的一个子集合,其中的元素称为边或弧。

 根据有向图的定义可以得出,在有向图中与一条弧相连的两个端点(即图的顶点)存在次序关系,即弧是顶点和的有序对。我们称为弧的起点,为终点。如果对有向图的每一条弧表示从起点到终点作一条矢线,方向是从指向,即有向图的每一条弧都有确定的方向。因此,有向图就是每条边都有一定方向的图。

1。4。2 网络与流

    定义 1。4。2。1  给定一个有向图,在中指定了一点为发点(记为),而另外一点为收点(记为),其余的点都称为中间点。对于有向图中的每一条弧,都会相对应跟着一个(或简写为),我们称其为弧的容量。通常我们就把这样的叫做一个网络。记作

所谓图论网络上的流,就是定义在弧集合上的一个函数,我们称为弧上的流量(有时也简记作)。

1。4。3可行流与最大流

    观察交通运输网络中不同类型的实际问题,我们可以发现对于流的特性有两个明显且必须的要求:一是网络中每条弧上的流量都不能大于该弧的容量;二是所有中间点的流量必须为零。因为对于每一个点,进入该点的流量与离开该点的流量之差,就是该点的净输出量,简称为该点的流量;但是由于中间点的作用只是传送,显然每个中间点的流量必为零。由此可以总结出,发点的净流出量必需等于收点的净流入量,也是该网络中此方案的总输送量。因此有:

   定义 1。4。3。1  满足下述条件所诉的流可称之为可行流:

  (1)容量限制条件:对每一弧

  (2)平衡条件:

    对于中间点:流入量和流出量相等,即对每一个有

    对于发点,记

    对于收点,记

    式中,称为该网络可行流的流量,其流量值为发点的净输出量(即收点的净输入量)。

    可行流总是存在的。比如最简单地,我们令所有弧的流量都为零,即,就可以得到一个可行流,称为零流。其流量。

    然而本文我们研究的最大流是什么呢,其实最大流问题就是寻求一个流使其流量达到最大,并且满足下列条件:

                                                   ①

                                       ②

可以看出,最大流问题本质上是一个特殊的线性规划问题。即求一组,在满足条件①和②下使达到极大。在第二章的第二节中将会看到,我们采取了图论的优势,解决这个问题的方法较之线性规划的一般方法要简单、直观得多。

  (3)增广链

若给定一个可行流,我们可将网络中的弧分为两类。

上一篇:交通运输网路的最短路算法的优劣讨论
下一篇:C#+sqlserver安卓系统性能测试工具的设计与实现

基于Apriori算法的电影推荐

PHP+IOS的会议管理系统的设计+ER图

数据挖掘在电子商务中的应用

数据挖掘的主题标绘数据获取技术与实现

基于PageRank算法的网络数据分析

基于神经网络的验证码识别算法

基于网络的通用试题库系...

安康汉江网讯

老年2型糖尿病患者运动疗...

ASP.net+sqlserver企业设备管理系统设计与开发

我国风险投资的发展现状问题及对策分析

网络语言“XX体”研究

新課改下小學语文洧效阅...

互联网教育”变革路径研究进展【7972字】

麦秸秆还田和沼液灌溉对...

LiMn1-xFexPO4正极材料合成及充放电性能研究

张洁小说《无字》中的女性意识