第六章 图论及网络模型.doc

图论及网络1、基本概念一个图是指由点集和中元素的无序对的一个集合所构成的二元组，记为，中的元素叫做顶点，中的元素叫做边。两个点、属于，如果边，则称和两点相邻。和称为边的端点。两条边、属于，如果它们有一个公共端点，则称、相邻。称边、为的关联边。用表示图中的边数，用表示图中的顶点个数。在不引起混淆情况下简记为，。当，为有限集合时，称为有限图，否则，称为无限图。我们只讨论有限图。对于任一条边属于，如果边端点无序，则称它是无向边，此时图称为无向图。如果边的端点有序，即它表示以为始点，为终点的有向弧（或称弧），这时图称为有向图。一条边的两个端点如果相同，称此边为环（自回路）。两个点之间多于一条边，称为多重边。不含环和多重边的图称为简单图，含有多重边的图称为多重图。我们只讨论简单图有向图中两点之间有不同方向的两条边，不是多重边。每一对顶点间都有边相连的无向简单图称为完全图。有个顶点的无向完全图记为。有向完全图则指每一对顶点间有且仅有一条有向边的简单图。图的顶点集可以分解为两个非空子集和，即，使得每条边的两个端点必有一个端点在中，另一个端点在中，则称为二部图（偶图），记作。以点为端点的边数叫做点的度（次），记作，简记。注意的是每个环算着两条边。次为1的点称为悬挂点，连接悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。定理 任何图中，顶点次数的总和等于边数的二倍。定理 任何图中，次为奇数的顶点必为偶数。有向图中，以为始点的边数称为点的出次，用表示，以为终点的边数称为点的入次，用表示。点的出次与点的入次之和就是该点的次。所有顶点的入次之和等于所有顶点的出次之和。图，若是的子集，是的子集，且中的边仅与中的顶点相关联，则称是的一个子图。特别地，若，则称是的生成子图（支撑子图）。网络在实际问题中，往往只用图来描述所研究的对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，通常称之为“权”，权可以代表如距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图称为网络（赋权图）。与无向图和有向图相对应，网络又分为无向网络和有向网络。实际问题要求我们计算最短路和最大流。无向图，若图中某些点与边的交替序列可以排成的形式，且（），则称这个点边序列为连接与的一条链，链长为。点边列中只有重复的点而无重复的边者为简单链。点边列中没有重复的点和重复边者为初等链。无向图中，连结与的一条链，当与是同一个点时，称此链为圈。圈中只有重复点而无重复边者为简单圈，既无重复点又无重复边者为初等圈。对于有向图可以类似于无向图定义链和圈，初等链、圈，简单链、圈，此时不考虑边的方向。而当链（圈）上的边方向相同时，称为道路（回路）。对于无向图来说，道路与链、回路与圈意义相同。一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图。用矩阵表示图对研究图的性质及应用是比较方便的。图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵、割集矩阵等。我们只介绍其中两种常用矩阵。网络（赋权图），其边有权，构造矩阵，其中：称矩阵为网络的权矩阵。对于图，构造矩阵，其中：则称矩阵为网络的邻接矩阵。当为无向图时，邻接矩阵是对称矩阵。连通图中，若存在一条道路，经过每边一次且仅一次，则称这条路为Euler道路。若存在一条回路，经过每边一次且仅一次，则称这条路为Euler回路。具有Euler回路的图称为Euler图。定理 无向连通图是Euler图，当且仅当中无奇点。推论 无向连通图是Euler图，当且仅当的边集可划分为若干个初等回路。推论 无向连通图是有Euler道路，当且仅当中恰好有两个奇点。定理 连通有向图是Euler图，当且仅当它每个顶点的出次等于入次。连通有向图是有Euler道路，当且仅当这个图中除去两个顶点外，其余每个顶点的出次等于入次，且这两个顶点中，一个顶点的入次比出次多1，另一个顶点的入次比出次少1。连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。定理 图，则下列关于树的说法是等价的：（1）是一棵树。（2）无圈，且。（3）连通，且。（4）无圈，但每加一条边即得唯一一个圈。（5）连通，但每舍去一边就不连通。（6）中任意两点，有唯一链相连。若图的生成子图是一棵树，则称该树为的生成树（支撑树），或简称为图的树。图中属于生成树的边称为树枝，不在生成树中的边称为弦。图有生成树的充分必要条件是连通。显然，生成树不唯一。寻找生成树的方法有：避圈法或加边法（又分为：深探法和广探法），破圈法等。连通图，每条边上有非负权。一棵生成树所有树枝上权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树（最小支撑树）简称最小树。许多网络问题都可以归结为最小树问题。寻找生成树的方法有：Kruskal算法和破圈法。有向树中的根树在计算机科学、决策论中有重要作用。若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。有向树，恰有一个结点入次为0，其余各点入次为1，则称为根树（又称外向树）。根树中入次为0的点称为根。根树中出次为0的点称为叶，其他顶点称为分枝点。由根到某一顶点的道路长度（设每边长为1），称为点的层次。在根树中，若每个顶点的出次小于或等于，称这棵树为叉树。若每个顶点的出次恰好等于或零，称这棵树为完全叉树。当时，称为二叉树。Dijkstra算法（Dijkstra于1959年提出的，用于求解两点间的最短路）：（1）给以标号，其余各点均给标号，。（2）若点为刚得到标号的点，考虑这样的点：，且为标号。对的标号进行如下的更改：（3）比较所有具有标号的点，把最小者改为标号，即：当存在两个一上最小者时，可同时改为标号。若全部点均为标号则停止。否则用代转回（2）。Floyd算法（1962年Floyd提出，用于求任意两点间的最短路）：为计算方便，令网络的权矩阵为，其中为到的距离。其中 算法基本步骤为：（1）输入权矩阵。（2）计算（）其中（3）中元素就是到的最短路长。设有向连通图，的每条边上有非负数称为边的容量，仅有一个入次为0的点称为发点（源），一个入次为0的点称为收点（汇），其余点为中间点，这样的网络称为容量网络，常记做。对任一中的边有流量，称集合为网络上的一个流。称满足下列条件的流为可行流：（1）容量限制条件：对中每条边，有。（2）平衡条件：对中间点，有（即中间点的物资的输入量与输出量相等）（3）对收、发点、，有(即从点发出的物资总量等于点输入的量)为网络流的总流量。可行流总是存在的。所谓最大流问题就是在容量网络中，寻找流量最大的可行流。若给一个可行流，我们把网络中使的弧称为饱和弧，使的弧称为非饱和弧。把的弧称为零流弧，的弧称为非零流弧。最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。容量网络，、为发点、收点，若有边集为的子集，将分为两个子图，其顶点集合分别为，分属，满足：不连通；为的真子集，而仍连通，则称为的割集，记。割集中所有始点在，终点在的边的容量之和，称为的割集容量，记为。容量网络的割集有多个，其中割集容量最小者称为网络的最小割集容量（简称最小割）。若是网络中联结发点和收点的一条链，我们定义链的方向是从到，则链上的弧被分为两类：一类是弧的方向与链的方向一致，叫做前向弧，前向弧的全体记为。另一类是弧与链的方向相反，叫做后向弧，后向弧的全体记为。设是一个可行流，是从到的一条链，若满足下列条件，称之为（关于可行流的）一条增广链：在弧上，即中每一弧是非饱和弧；在弧上，即中每一弧是非零和弧。设，我们把始点在，终点在中的所有弧构成的集合，记为。给网络，若点集被剖分为两个非空集合和，使，则把弧集称为是（分离和的）截集。给一截集，把截集中所有弧的容量称为这个截集的容量（简称为截量），记为，即.任何一个