第6章 网络优化

山东财经大学运筹学网络分析图与子图图的连通与割集树与支撑树最小树最短有向路最大流最小费用流图与子图图与网络

无向图的基本概念

有向图与网络图的表示方法

关联矩阵

邻接矩阵

主要结论子图问题的背景实际网络--交通网络、通信网络、Internet网络关系网络—人际关系网络、工作关系网络、先后关系网络等抽象网络—描述研究对象之间是否存在关系无向图的基本概念无向图G：一个有序二元组(N,E),记为G=(N,E)G的点集合：

N=（1，2，3，4）是一个无向图的点的集合G的边集合：E={eij}且eij={ni,nj}为无序二元组称ni和nj为eij的端点，且称eij

连接点ni和nj

3412abcde34512afedbcg圈（环）：两个端点重合为一点的边（例如图（1）中的d）孤立点：不与任何边关联的点（例如图（1）中的顶点5）重边：端点重合的边f和g点边关系关联：一条边的端点称为这条边的关联点，顶点1与边a和b邻接：与同一条边关联的端点称为是邻接的，如点1和2，同时如果两条边有一个公共端点，则称这两条边是邻接的，如边a和b。

3412abcde特殊图类有限图：点和边都是有限集合的图空图：没有任何边的图平凡图：只有一个点的图简单图：既没有环也没有两条边连接同一对点的图空图平凡图简单图完全图：每一对点之间均有一条边相连的图二分图G=(N,E)：存在的一个二分划(S,T)，使得G的每条边有一个端点在S中，另一个端点在T中完全二分图G=(S,T,E)：S中的每个点与T中的每个点都相连的简单二分图简单图G的补图:与G有相同顶点集合的简单图，且中的两个点相邻当且仅当它们在G中不相邻返回完全图完全二分图补图有向图与网络♂有向图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的每条边（弧）都赋予一个实数，并称为边（弧）的权，则连同它边（弧）上的权称为（有向）网络关联矩阵关联矩阵示例134521342返回邻接矩阵邻接矩阵示例返回134521342主要结论♂子图♂Scilab中输入图命令：g=make_graph(name,directed,n,tail,head)其中：

name：图的名称，字符串‘graph1’directes：有向无向，0-无向图，1-有向图

n：顶点个数

tail向量，各边的尾部

head向量，各边的头部例子123456abcdefghiabcdefghi121133445254346566边尾点头点常用函数g1=add_edge(i,j,g)//加边g1=add_node(g,[xy,name])//加点g1=delete_arcs(ij,g)//删除边g1=delete_nodes(v,g)//删除点ma=edge_number(g)//边数g2=graph_union(g,g1)//图的并g1=line_graph(g)//反图n=node_number(g)//点数关联矩阵和邻接矩阵a=graph_2_mat(g,mat)其中g:图mat:字符串,'node-arc'or'node-node'a:点边关联矩阵或点点邻接矩阵g=mat_2_graph(a,directed,[mat])其中a:点边关联矩阵或点点邻接矩阵directed:integer,0(无向)or1(有向)mat:字符串,'node-arc'or'node-node'g:graphlist图的连通与割集

图的连通

无向图

有向图图的割集

概念

主要结论♂无向图的路135426图G中路：一个点和边交替序列(ni,eij,nj,…,nk,ekl,nl)，简单路：边不重的路初级路：点不重的路回路：在G中，一条至少包含一个边并且ni=nl的{ni,nl}路简单回路：边不重的回路初级回路：点不重的回路连通性点i和j点是连通的：G中存在一条（i，j）路G是连通的：G中任意两点都是连通的连通分支：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的极大连通子图返回强连通性p=find_path(i,j,g)割集♂割集的性质♂树与支撑树树及其基本性质

概念及符号

基本性质支撑树及其基本性质

概念及符号

基本性质概念及符号最少用多少边可把下列点连起来？♂树的基本性质概念及符号♂支撑树的基本性质最小树最小树及其性质求最小树的Kruskal算法

算法步骤

算例

算法复杂性Dijkstra算法

算法步骤

算例

算法复杂性

Scilab实现最小支撑树算法步骤

算例

1452312432214迭代过程

1452312432214145231243221414523124322141452312432214算法复杂性

♂算法步骤

算例

1452312432214迭代过程

1452312432214145231243221414523124322141452312432214算法复杂性

Scilab实现用Scilab语句求解下列网络的最小树t=min_weight_tree(g)

1452312432214Scilab命令及结果最短有向路最短有向路问题数学规划模型最短有向路方程Dijkstral算法

Scilab实现最短有向路问题12345652332426179数学规划模型最短有向路方程通过求解方程组求出最短有向路需要解决的问题1.方程组的解是否唯一？由于最短路长度是唯一的，如果方程组的解不唯一，就无法处理。2.方程组的解是否容易求解？求解的难点在哪里？算法步骤

算例

12345652332426179计算的迭代过程

123456523324261705∞9∞31234565233242617051095399123456523324261705695391234565233242617056853912345652332426170568539算法复杂性

Scilab实现结果最大流最大流问题数学规划模型最大流最小割定理最大流算法Scilab实现最大流问题1234565233242617数学规划模型主要定理算法步骤

算例

1234565233242617迭代过程

1234565,22,23,23,22,2426,21712345632,2112,2426,217-∞+1,3+2,1+1,1算法复杂性

结果扩展多发点多收点流边有损耗的问题多阶段流问题最小费用流最小费用流问题

规划模型与对偶理论

算法步骤

算例

算法复杂性运输问题Scilab实现最小费用流问题2,32,13,21,33,11,24,25,21,22,32,13,21,33,11,24,25,21,22,32,13,21,33,11,24,25,21,22222222223211V=4，费用为32V=4，费用为25线性规划形式对偶规划原可行对偶可行互补松弛基本思路给定一组pj在满足互补条件的边上找最大流停止最大流值是否大于v修改pj算法步骤

算例

1,21,21,23,13,4迭代过程1,2,01,2,01,2,03,1,03,4,000001,2,01,2,01,2,03,1,03,4,011102,01,2,21,2,21,2,23,1,03,4,013201,2,01,2,01,2,03,1,03,4,012202,02,02,02,22,22,21,2,21,2,21,2,23,1,03,4,024302,22,22,21,01,2,21,2,21,2,23,1,03,4,025302,22,22,21,04,01,2,21,2,11,2,23,1,13,4,12530算法复杂性

♂Scilab实现用Scilab语言求解以上算例所示网络的最小费用流Scilab语句：cleartail=[11223];head=[23344];

g=make_graph('g'