全国研究生数学建模大赛课件资料-网络优化

网络分析运筹学课件网络分析图与子图图的连通与割集树与支撑树最小树最短有向路最大流最小费用流最大对集运筹学课件图与子图图与网络无向图的基本概念网络的基本概念关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图运筹学课件网络分析无向图的基本概念无向图G：一个有序二元组(N,E),记为G=(N,E)G的点集合：（例如：图（1）中的N=（1，2，3，4，5）是一个无向图的点的集合）G的边集合：E={eij}且eij={ni,nj}为图（1）无序二元组eij的端点：有eij={ni,nj}，则称ni和nj为eij的端点，且称eij连接点ni和nj圈：两个端点重合为一点的边（例如图（1）中的e11）孤立点：不与任何边关联的点（例如图（1）中的n5）34512续（1）关联：一条边的端点称为这条边的关联邻接：与同一条边关联的端点称为是邻接的，同时如果两条边有一个公共端点，则称这两条边是邻接的有限图：点和边都是有限集合的图空图：没有任何边的图平凡图：只有一个点的图简单图：既没有圈也没有两条边连接同一对点的图续（2）完全图：每一对点之间均有一条边相连的图二分图G=(N,E)：存在的一个二分划(S,T)，使得G的每条边有一个端点在S中，另一个端点在T中完全二分图G=(S,T,E)：S中的每个点与T中的每个点都相连的简单二分图简单图G的补图:与G有相同顶点集合的简单图，且中的两个点相邻当且仅当它们在G中不相邻GG返回网络的基本概念运筹学课件♂有向图G：一个有序二员组(N,A)，记为G=(N,A)G的弧集合：A={aij}且aij={ni,nj}为有序二元组，若aij={ni,nj}，则称aij从ni连向nj，ni称为aij的尾，nj为aij的头，ni称为nj的先辈，nj称为ni的后继有向图G的基本图：对于G的每条弧用一条边代替后得到的无向图（有向）网络G：对（有向）图G的每条边（弧）都赋予一个实数，并称为边（弧）的权，则连同它边（弧）上的权称为（有向）网络关联矩阵简单图),(ENG的关联矩阵：一个||||EN阶矩阵)(ikbB，其中,0,1否则关联与边当点kibik简单有向图),(ANG的关联矩阵：一个||||AN阶矩阵)(ikbB，其中,0,1,1否则为头以点当弧为尾以点当弧iaiabikikik运筹学课件关联矩阵示例图（7）的关联矩阵是图（8）的关联矩阵是134521342返回110100001010010001101010000110010000011154321110001011001101000114321邻接矩阵邻接矩阵示例图（7）的邻接矩阵是图（8）的邻接矩阵是134521342返回01110101011101110101011105432154321010000001100011043214321主要结论命题6.1.1G是二分图当且仅当G的邻接矩阵可表成如下形式00TAAA命题6.1.2||2Edii其中id表示简单图G中点i的次是指G中与点i关联的边数命题6.1.3iiiidAd||其中id表示简单有向图G中点i的入次是指G中以点i为头的弧数；id表示点i的出次是指G中以点i为尾的弧数运筹学课件网络分析♂子图运筹学课件网络分析♂图),(ENG的子图),(ENG：NN和EE，对E中任意的一条边},{jiijnne，都有Nni和Nnj图G的支撑子图G：G是G的子图，且NN点导出子图][NG：以N的一个非空子集N作为点集、以两端点均在N中的所有边为边集的子图边导出子图][EG：以E的一个非空子集E作为边集、以E中边的所有端点作为点集的子图图G的不相交子图1G和2G：1G和2G没有公共点图G的边不重子图1G和2G：1G和2G没有公共边子图1G和2G的并21GG：以1G和2G的点集的并为点集，以1G和2G的边集的并为边集的子图子图1G和2G的交21GG：以1G和2G的点集的交为点集，以1G和2G的边集的交为边集的子图无向图的路运筹学课件网络分析135426图G中路：一个点和边交替序列(ni,eij,nj,…,nk,ekl,nl)，简单路：边不重的路初级路：点不重的路回路：在G中，一条至少包含一个边并且ni=nl的{ni,nl}路简单回路：边不重的回路初级回路：点不重的回路连通性点i和j点是连通的：G中存在一条（i，j）路G是连通的：G中任意两点都是连通的连通分支：G的极大连通子图命题6.2.1设G有p个连通分支，则G的邻接矩阵可以表示成分块矩阵返回有向路运筹学课件134256有向图G中的一条有向路：个点和弧的交错序列(ni,aij,nj,…,nk,akl,nl)，记为(ni,nl)有向路简单有向路：弧不重的有向路初级有向路：点不重的有向路有向回路：至少包含一条弧且ni=nj的(ni,nj)有向路简单有向回路：弧不重的有向回路初级有向回路：点不重的有向回路点i和点j是强连通的：G中存在一条(i,j)有向路，也存在一条(j,i)有向路G是强连通的：G中任意两点都是强连通的G的强连通分支：G的极大连通子图命题6.2.2设G有p个强连通分支，则G的邻接矩阵可以表示成如下形式：返回强连通性割集运筹学课件图G的割边：如果从G中删去它就使图的连通分支数严格增加的边},{TS割：一个端点在S中，另一个端点在T中的边集合，其中S和T是N的两个不相交子集图G的边割},{SS：从G中删去它就使图的连通分支数严格增加的边集合割集：G的极小边割图G的割边：如果从G中删去它就使图的连通分支数严格增加的边),(TS：有向图),(ANG中尾在S中，头在T中的弧集合有向图G的弧割),(SS：从G中删去它就使图的强连通分支数严格增加的弧集合有向割集：G的极小弧割♂割集的性质命题6.2.3任何边割都是不相交割集的并命题6.2.4任给图G，设C是G的一条简单回路},{TS是G的一个割集，并用)(),(ECE分别表示,C所包含的边集合。若)()(ECE，则2|)()(|ECE运筹学课件网络分析♂树与支撑树树及其基本性质概念及符号基本性质支撑树及其基本性质概念及符号基本性质♂运筹学课件网络分析概念及符号树：一个连通且无回路（除非特别声明，以后皆指初级回路）的图k－树（森林）：有k个连通分支且无回路的图21HH：子图1H和子图2H的边的并集21HH：子图1H和子图2H的边的交集21\HH：在子图1H中但不在子图2H中的边的集合eG：在图G中加连边eeG：在图G中去掉边eiG：在图G去掉点i及与点i关联的所有边♂运筹学课件网络分析树的基本性质定理6.3.1设),(ENT是3||N的一个图，则下列六个定义是等价的：（1）T连通且无回路；（2）T有1||N条边且无回路；（3）T连通且有1||N条边；（4）T连通且每条边都是割边；（5）T的任两点间都有唯一的路相连；（6）T无回路，但在任一对不相邻的点间加连一条边，则构成唯一的一个回路。定理6.3.2每个树至少有两个次为1的点。♂运筹学课件网络分析概念及符号图G的支撑树：G的一个是树的支撑子图G的反树：TGT\*，其中),(ENT是),(ENG的一个支撑树)(e：割集},{21SS，其中21,SS为eT的两个连通分支的点集合♂运筹学课件网络分析支撑树的基本性质定理6.3.3G有支撑树当且仅当G是连通的。定理6.3.4任给图G，设T是G的支撑树，e是T的一条边，则存在唯一的一个割集)(e包含于eT*中。定理6.3.5设1T和2T是G的两个支撑树，且kTT|\|21，则2T经过k次迭代后就得到1T♂运筹学课件网络分析最小树最小树及其性质求最小树的Kruskal算法算法步骤算例算法复杂性Dijkstra算法算法步骤算例算法复杂性Scilab实现♂运筹学课件网络分析最小支撑树支撑树T的权（或长）：EeeWTW)()(最小支撑树：G中权最小的支撑树定理6.4.1设T是G的支撑树，则T是G的最小树当且仅当对任意边*Te有)(max)()(eWeWeCe其中eTeC)(为一个唯一的回路。定理6.4.2设T是G的支撑树，则T是G的最小树当且仅当对任意边Te有)(min)()(eWeWee其中eTe*)(为一个唯一割集。定理6.4.3设T是G的支撑树，则T是G的唯一最小树当且仅当对任意边TGe\，e是)(eC中的唯一最大边。定理6.4.4设T是G的支撑树，则T是G的唯一最小树当且仅当对任意边Te，e是)(e中的唯一最大边。♂运筹学课件算法步骤运筹学课件第1步开始把边按权的大小由小到大排列起来，即maaa,...,,21置S，0i，1j。第2步若1||niS，则停。这时TSG][即为所求；否则，转向第3步。第3步若}]{[jaSG不构成回路，则置jiae1，}{1ieSS，1ii，1jj，转向第2步；否则，置1jj，转向第2步。♂算例运筹学课件网络分析用Kruskal算法求解下图所示网络的最小树，其中每条边上的数表示该边的权值。②143①2④2⑤244③计算的迭代过程运筹学课件网络分析②②11①④⑤①④⑤2③③②②113①④⑤①④2⑤2③③♂算法复杂性运筹学课件网络分析首先，在第1步中把边按权的大小由小到大排列起来，这约需mm2log次比较；其次，第2步最多循环n次；在第3步中，判定加边后是否构成回路总共约需m次比较，而加边后点的重新标号最多需)1(nn次比较。所以，总的计算量为)log(~)1(log222nnOnnmnmm♂算法步骤运筹学课件网络分析第1步置jjwu1，T,}1{R,},...,3,2{nS；第2步取ikjSjkwuu}{min，置}{ikeTT，}{kRR，}{\kSS；第3步若S，则停止；否则，置},{minkjjSjkwuu，Sj，返回第2步。♂算例运筹学课件网络分析用Dijkstra算法求解下图所示网络的最小树，其中每条边上的数表示该边的权值。②143①2④2⑤244③计算的迭代过程运筹学课件网络分析1②②1431433①2④2⑤①2④2⑤244244③③22②②1433143①2④2⑤①2④2⑤244244③③♂算法复杂性运筹学课件网络分析执行第2步时，第一次是2n次比较，第二次为3n次比较，第三次为4n次比较，…，因此总的比较为2)1)(2(nn次。执行第3步时，第一次是2n次比较，第二次为3n次比较，第三次为4n次比较，…因此总的比较为)1)(2(nn次。所以，总的计算量约为)(2nO。♂Scilab实现用Scilab语句求解下列网络的最小树1324242414523Scilab命令及结果cleartail=[11222334];head=[23345455];g=make_graph('g',0,5,tail,head);//制图weight=[12243442];//权向量g('edge_weight')=weight;t=min_weight_tree(g)//用Scilab命令求解t=!1.2.8.5.!//结果返回最短有向路最短有向路方程求最短有向路的Dijkstral算法算法步骤算例算法复杂性Scilab实现♂运筹学课件网络分析最短有向路方程给定有向网络),,(WANG，设P为G中的一条有向路P的权（或长）：PaaWPW)()(问题：寻求有向网络中自某一指定点i到另一指定点j间的最短有向路定理6.5.1设有向网络G中不含非正有向回路，并且从点1到其余点都有有限长度的有向路，那么(6.5.2)有唯一有限解。njwuuukjkjkj,...,3,2},{min01(6.5.