山大《运筹学》课件06图与网络分析

1、第一节 图与子图图与网络 无向图的基本概念 有向图和网络关联矩阵和邻接矩阵 关联矩阵 邻接矩阵 主要结论子图 无向图的基本概念无向图G：一个有序二元组(N,E)，记为G=(N,E)G的点集合：N=n1,n2, ,nnG的边集合：E=eij，且eij是一个无序二元组ni,nj，记为eij= ni,njeij的端点：若eij= ni,nj，则称eij连接ni和nj，点ni和nj称为eij的端点环：两个端点重合为一点的边孤立点：不与任何边关联的点例无向图的基本概念关联：一条边的端点称为与这条边关联邻接：与同一条边关联的端点称为是邻接的，同时如果有两条边有一个公共端点，则称这两条边是邻接的有限图：任何

2、图G=(N,E)若N和E都是有限集合,则称G为有限图空图：没有任何边的图平凡图：只有一个点的图简单图：一个图，即没有环，也没有重边。例如(a)是简单图，但(b)就不是简单图。续一无向图的基本概念完全图：每一对点之间均有一条边相连的图（如图一）二分图G=(S,T,E) ：存在一个二分划(S,T)，使得G的每一条边有一个端点在S中，另一个端点在T中完全二分图：S中的每一个点和T中的每一个点都相连的简单二分图（如图二）简单图G的补图 :与G有相同顶点集合的简单图，且补图中的两个点邻接当且仅当它们在G中不邻接（如图三）续二图二图一图三有向图有向图G：一个有序二元组(N,A)，记为G=(N,A)G的点集

3、合： N=n1,n2, ,nnG的弧集合：A=aij且aij是一个有序二元组(ni,nj)记为aij= (ni,nj) 下图就是个有向图若aij= (ni,nj)，则称aij从ni连向nj，ni称为aij的尾，nj称为aij的头。 ni称为nj的前继，称nj为ni的后继基本图：去掉有向图的每条弧上的方向所得到的无向图。网络设G是一个图（有向图），若对G的每条边（弧）都赋予一个实数，并称为这条边（弧）的权，则G连同它边（弧）上的权称为一个（有向）网络或赋权（有向）图，记为G=(N,E,W)。无向完全图：在无向图中，如果任意两个顶点之间存在边。有向完全图：在有向图中，如果任意两顶点之间都有存在方向

4、互为相反的两条弧。含有n个顶点的无向完全图有多少条边含有n个顶点的有向完全图有多少条弧？n(n-1)/2n(n-1)关联矩阵简单图G=(N,E)的关联矩阵：一个|N|E|阶的矩阵B=(bik)，其中简单有向图G=(N,A)的关联矩阵：一个|N|A|阶的矩阵B=(bik)，其中关联矩阵右图的关联矩阵是续邻接矩阵简单图G=(N,E)的邻接矩阵：一个|N|E|阶的矩阵A=(aij)，其中简单有向图G=(N,A)的邻接矩阵：一个|N|A|阶的矩阵A=(aik)，其中邻接矩阵右图的邻接矩阵是续几个基本结论定理6.1.1 G是二分图当且仅当G的邻接矩阵可以表示成如下形式一个简单有向图G=(N,A)的点i的

5、入次是指G中以点i为头的弧数，记为di-；点i的出次是指G中以点i为尾的弧数，记为di+子图图G的支撑子图G：G是G的子图，且N=N点导出子图GN ：以N的一个非空子集N 作为点集，以两端点均在N中的所有边为边集的子图边导出子图GE ：以E的一个非空子集E 作为边集，以E中边的所有端点作为点集的子图子图图G的不相交子图G1和G2：G1和G2没有公共点图G的边不重子图G1和G2：G1和G2没有公共边子图G1和G2的并G1G2：以G1和G2的点集的并为点集，以G1和G2的边集的并为边集的子图子图G1和G2的交G1G2：以G1和G2的点集的交为点集，以G1和G2的边集的交为边集的子图续第二节 图的连

6、通性图的连通 路和回路 连通分支 有向路 强连通图的割集 割集的基本概念 割集的性质路和回路路：一个点和边的交替序列(ni,eij, ,ekl,nl)，记为ni,nl 路简单路：边不重的路初级路：点不重的路回路：在G中，一条至少包含一个边并且ni=nl的ni,nl路简单回路：边不重的回路初级回路：点不重的回路例连通分支点i和j点是连通的：G中存在一条i,j路G是连通的：G中任意两点都是连通的 连通分支：G的极大连通子图 下图中(a)是连通图，(b)是一个具有三个连通分支的非连通图。 (a) (b)连通分支定理6.2.1 设G有p个连通分支，则G的邻接矩阵可以表示成如下形式： 续有向路有向图G中

7、的一条有向路：一个点和弧的交错序列 (ni,aij,nj,nk,akl,nl)，记为(ni,nl)有向路 简单有向路：弧不重的有向路 初级有向路：点不重的有向路 有向回路：至少包含一条弧且ni=nj的(ni,nj)有向路 简单有向回路：弧不重的有向回路 初级有向回路：点不重的有向回路例强连通点i和点j是强连通的：G中存在一条(i,j)有向路,也存在一条(j,i)有向路G是强连通的：G中任意两点都是强连通的 G的强连通分支：G的极大强连通子图下图中，(a)是一个强连通分支，(b)是一个具有三个强连通分支的非强连通图。强连通定理6.2.2 设G有p个强连通分支，则的邻接矩阵可以表示成如下形式：续割

8、集的基本概念割集的基本概念续例割集的性质定理6.2.3 任何边割都是不相交割集的并。定理6.2.4 任给图G，设C是G的一条简单回路=S,T 是G的一个割集，并用E(C)，E()分别表示C,所包含的边集合。若E(C)E()，则|E(C)E()|2。第三节 树与支撑树树及其基本性质支撑树及其基本性质树及其基本性质树：一个连通且无回路的图（除非特别声明，以后所说的回路皆指初级回路）森林：一个无回路的图H1H2：子图H1和子图H2的边的并集H1H2：子图H1和子图H2的边的交集H1H2：在子图H1中但不在子图H2中的边的集合G+e：在图G中加连边eG-e：在图G中去掉边eG-i：在图G去掉点i及与点

9、i关联的所有边树及其基本性质定理6.3.1 设T=(N,E)是|N|3的一个图，则下列六个定义是等价的: (1)T连通且无回路 (2)T有|N|-1条边且无回路 (3)T连通且有|N|-1条边 (4)T连通且每条边都是割边 (5)T的任两点间都有唯一的路相连 (6)T无回路，但在任一对不相邻的点间加连一条边，则构成唯一的一个回路证明树及其基本性质定理6.3.2 每个树至少有两个次为1的点续证明支撑树及其基本性质图G的支撑树：G的一个是树的支撑子图G的反树：T*=GT，其中T=(N,E )是G=(N,E)的一个支撑树(e)：割集S1,S2，其中S1,S2为T-e的两个连通分支的点集合支撑树及其基

10、本性质定理6.3.3 G有支撑树当且仅当G是连通的。 定理6.3.4 任给图G，设T是G的支撑树，e是T的一条边，则存在唯一的一个割集(e)包含于T*+e中。 定理6.3.5 设T1和T2是G的两个支撑树，且|T1T2|=k，则T2经过k次迭代后就得到T1。 续证明证明提示第四节 最小树问题最小树及其性质求最小树的Kruskal算法 算法步骤 算法复杂性 求最小树的Dijkstra算法 算法步骤 算法复杂性最小树及其性质支撑树T的权（或长）：最小树：G中权最小的支撑树定理6.4.1 设T是G的一个支撑树，则T是G的最小树当且仅当对任意边eT*有证明最小树及其性质续定理6.4.3 设T是G的支撑

11、树，则T是G的唯一最小树当且仅当对任意边eGT，e是C(e)中的唯一最大边。定理6.4.4 设T是G的支撑树，则T是G的唯一最小树当且仅当对任意边eT ，e是(e)中的唯一最小边。证明Kruskal算法的步骤第1步 开始把边按权的大小由小到大排列，即将图的边排序为a1,a2, ,am，使W(a1) W(a2)W(am) 置S=，i=0，j=1。第2步 若|S|=i=n-1，则停止。这时GS=T即为所求；否则，转向第3步。第3步 若GSaj不构成回路，则置ei+1=aj，S=Sei+1 ，i:=i+1，j:=j+1，转向第2步；否则，置j:=j+1，转向第2步。例Kruskal算法的复杂性首先，

12、在第1步中把边按权的大小由小到大排列起来，这约需mlog2m次比较(m为此网络的边数)其次，第2步最多循环n次在第3步中，判定加边后是否构成回路总共约需m次比较，而加边后点的重新标号最多需n(n-1)次比较所以，总的计算量为mlog2m+n+m+n(n-1)O(n2log2n)Dijkstra算法的步骤第1步 置uj=w1j，T=，R=1，S=2,3, ,n例Dijkstra算法的复杂性执行第2步时，第一次是(n-2)次比较， 第二次为(n-3)次比较， 第三次为(n-4)次比较， 因此总的比较为(n-1)(n-2)/2次执行第3步时，第一次是(n-2)次比较， 第二次为(n-3)次比较， 第

13、三次为(n-4)次比较， 因此总的比较为(n-1)(n-2)次所以，总的计算量约为O(n2)第五节 最短有向路问题最短有向路方程求最短有向路的Dijkstra算法 算法步骤 算法复杂性最短有向路方程问题：寻求有向网络中中自某一指定点i 到另一指定点j间的最短有向路 最短有向路方程定理6.5.3 设G=(N,A,W)是一个弧权为正值的有向网络，则在G中，任意一条最短有向路的长都大于它的真子有向路的长。G中自点1到其他各最短有向路的长可按大小排列如下0=u1u2un续Dijkstra算法的步骤第1步(开始) 置u1=0，uj=w1j，j=2,3,n，P=1，T=2,3,n。第3步(修改临时标号)对

14、T中每一点j，置uj=minuj,uk+wkj，然后返回第1步。 例Dijkstra算法的复杂性这个算法经过n-1次循环必结束在第2步中要做(n-2)(n-1)/2次比较在第3步中要做(n-2)(n-1)/2次加法和(n-2)(n-1)/2次比较所以，总的计算量约为O(n2)第六节 最大流问题最大流最小割定理 基本概念 主要定理最大流算法 算法步骤 算法复杂性基本概念给定有向网络G=(N,A,C)，cij表示弧(i,j)A的容量，G有一个发点s和一个收点t (s,t N)。令xij=通过弧(i,j)的流量 (6.6.1)显然有0 xijcij (6.6.2)另外，流x=(xij)要遵守点守恒规

15、则，即可行流：满足(6.6.1)和守恒方程(6.6.2)的流，简称为(s,t)-流基本概念设P是G中从s到t的无向路，则P的前向弧(i,j)是指其方向从s到t的弧；否则称为P的后向弧流x=(xij)的增广路P：P的每个前向弧(i,j)有xij0(s,t)-割：弧割(S,T)，其中sS，tT割(S,T)的容量：续主要定理定理6.6.1(增广路定理) 一个可行流是最大流当且仅当不存在关于它的从s到t的增广路。 定理6.6.2(整流定理) 如果网络中所有弧容量是整数，则存在值为整数的最大流。 定理6.6.3(最大流最小割定理) 一个(s,t)-流的最大值等于(s,t)-割的最小容量。 证明证明提示最

16、大流算法的步骤第1步(开始) 令x=(xij)是任意整数可行流，可能是零流，给s一个永久标号(-,)。 第2步(找增广路)(2.1) 如果所有标号都已经被检查，转到第4步。(2.2) 找一个标号但未检查的点i，并做如下检查，对每一个弧(i,j)，如果xijcij且j未标号，则给j一个标号(+i,(j)，其中(j)=mincij-xij,(i)；对每一个弧(j,i)，如果xij0且j未标号，则给j一个标号(-i,(j)，其中(j)=minxji,(i)。(2.3) 如果t已被标号，转到第3步；否则，转到(2.1)。最大流算法的步骤第3步(增广) 由点t开始，试用指示标号构造一个增广路，指示标号的

17、正负则表示通过增加还是减少弧流量来增大流值。抹去S点以外的所有标号，转到第2步。第4步(构造最小割) 这时现行流是最大的，若把所有标号点的集合记为S，所有未标号点的集合记为T，便得到最小容量割(S,T)，计算完成。 续例最大流算法的复杂性设弧数为m，每找一条增广路最多需要进行2m次弧检查。如果所有弧容量都是整数，则最多需要v次增广，其中v是最大流值。所以，总的计算量为O(mv)。注：此算法的时间复杂性与最大流值v有关，所以说它并不是一个好的算法。如果大家感兴趣，可以查阅相关书籍，有好的算法，如复杂性为O(n3)的算法。第七节 最小费用流问题最小费用流算法 规划形式 算法步骤 算法复杂性运输问题

18、 对偶规划 算法步骤规划形式规划形式续一原始规划P规划形式续二对偶规划D最小费用流算法的步骤第1步(开始) 让所有的流xij=0，所有点对应的数p(i)=0。第2步(决定哪些弧可以改变流量) 用I表示这样的弧集合使p(j)-p(i)=wij，同时xij0 用Q表示不在IR中的弧集合。最小费用流算法的步骤第3步(改变流量)用最大流算法，在IR上找增广路，增加流量。如果从s到t的流量已经是v，那么计算停止，已经得到一个流量是v的最小费用流。如果从s到t不能再增加流量，检查在QIR中是否能找到增广路。如果不能找到增广路，那么该网络的最大流达不到v；如果在QIR中能找到增广路，就转入第4步。第4步(改

19、变顶点的p(i )值)把所有点分成两类：S是标上号的点的集合，T是标不上号的点的集合，让S中的点p(i )值不变，T的点p(i )值全部加1，再转回第2步。续例最小费用流算法的复杂性设网络的点数为n，弧数为m，弧的最大容量为w算法的循环次数取决于点的p(i)值修正的次数，最多进行mw次因此第2步的计算量为O(m2w)如果最大流值为v，则留增广最多进行v次所以第3步的计算量为O(nw)第4步的计算量为O(nmw)所以，总的计算量为O(m2w+nmw)运输问题ai表示发点i可供应的产品数量 bj表示收点j所需的产品数量wij表示从发点i到收点j的单位产品运输费用xij表示从发点i分配给收点j的产品

20、数量对偶规划算法步骤第1步(开始) 任给原始规划的可行解xij第2步(计算对偶解) 对于原始规划的可行解xij，计算出对偶规划的一个解ui,vj第3步(计算检验数) 对于对偶规划的解ui,vj，计算若所有的 均非负，则计算结束，这时得到的xij和ui,vj分别为原始规划和对偶规划的最优解；否则，转第4步算法步骤续第4步(调整原始可行解) 令即选择xst进入基。对应于网络中，即在支撑树上加入弧(s,t)，从而得到一个回路。并选择其流量xst=，使这个回路上的流量通过加 或减 以达到去掉一条弧的目的，从而得到一个新的被改进的原始可行解xst，转第2步例第八节 最大对集问题二分图的对集 基本概念 主

21、要定理二分图的最大基数对集 基本思想 算法步骤 算法复杂性二分网络的最大权对集分派问题 规划形式 算法步骤基本概念图G=(N,E)的对集M：M是E的子集，且M中任意两边均不相邻。M-饱和点i：iN，且i同M的一条边关联。M-非饱和点i：iN，且i不同M的任一条边关联。G的完美对集M：G的每一个点都是M-饱和点。G的最大基数对集M：不存在另外一个对集M,使得|M|M|，其中|M|表示M的基数。基本概念G的一条M-交错路：边在对集M和EM中交错出现的路。G的一条M-增广路：起点和终点都是M非饱和的一条M-交错路。图G=(N,E)的覆盖K：K是N的子集，且G的每条边都至少有一个端点在K中。图G的最小覆盖K：G不存在另外一个覆盖K，使得|K|K|。续主要定理定理6.8.1 图G中的一个对集M是最大基数对集当且仅当G不包含M-增广路。 引理6.8.1 设M是一个对集，K是一个覆盖，它们满足|M|=|K|，则M必定是最大基数对集，而K是最小覆盖。定理6.8.3 在二分图中，最大基数对集的边数等于最小覆盖的点数。证明最大基数对集算法的基本思想从图G的任意一个对集M开始，若M饱和S的所有点，则M是G的最大基数对集；否则，由S的M-非饱和点出发，用一个系统方法搜索一条M