运筹学第八章-图与网络分析-胡运权

运筹学赵明霞山西大学经济与管理学院2

第八章图与网络分析图与网络的基本概念树最短路问题最大流问题最小费用最大流问题2024/8/163柯尼斯堡七桥问题欧拉回路：经过每边且仅一次厄尼斯堡七桥问题、邮路问题哈密尔顿回路：经过每点且仅一次货郎担问题、快递送货问题4第一节图与网络的基本概念图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图8.1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图8.15描述对象之间关系，研究特定关系之间的内在规律，图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图8.26a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图8.3

如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。无向图是有向图的基础图G(D)有限图无限图2024/8/16运筹学--线性规划7G=(V,E)关联边(m)：ei端（顶）点(n)：vi,vj点相邻(同一条边)：

v1,v3边相邻(同一个端点)：e2,e3环：e1多重边：

e4,e58简单图：无环无多重边

多重图：多重边2024/8/16运筹学--线性规划9完全图：每一对顶点间都有边（弧）相连的简单图2024/8/16运筹学--线性规划10次（d）：结点的关联边数目d(v3)=4，偶点d(v2)=3，奇点d(v1)=4d(v4)=1，悬挂点e6,悬挂边d(v5)=0，孤立点出次：d+(vi)入次：d-(vi)d

(vi)=d+(vi)+d-(vi)定理1顶点次数总和等于边数的两倍。定理2次为奇数的顶点必为偶数个。11若,则G’是G的子图，G是G’的母图若,则G’是G的真子图，若,则G’是G的支撑（生成）图。链：点边交替序列闭链：v1v2v3v4

v1开链：v1v2v3

边不同，简单链：v3v4v5v1v6v5边不同且结点不同，初等链：v1v2v3v4v5v6圈：闭链，且至少有3个不同结点，v2

v3v4

v2初等圈：初等闭链，v1

v2v3v4

v112路：有向图：弧的方向与链的方向一致开路:v1v2v4v5回路：第一个点和最后一个点相同。v1v2v4v5v113连通图：若任何两个不同的点之间，至少存在一条链，则G为连通图。赋权图：对一个图的每一条边（弧）(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：赋权连通图无向图：开链即开路，闭链即回路有向图：弧的方向与链的方向一致。2024/8/16运筹学--线性规划142024/8/1615柯尼斯堡七桥问题欧拉回路：经过每边且仅一次厄尼斯堡七桥问题、邮路问题充要条件：无向图中无奇点，有向图每个顶点出次等于入次16第二节树树是图论中的重要概念，所谓树就是一个无圈的连通图。

图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图8-4v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)树的基本性质任意两点间有且仅有一条链不相邻两点间添加一条边，有且仅有一个圈任意去掉一条边，得不连通图.存在悬挂点m=n-11718

(a)(b)(c)生成（支撑）树若,则G’是G的支撑（生成）树。191、破圈算法步骤：（1）在给定的赋权的连通图上任找一个圈。（2）在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。（3）如果所余下的图已不包含圈，则计算结束，所余下的图即为最小树，否则返回第1步。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。20例8.12、避圈算法步骤：（1）任找一个点S，其余各点就是。（2）在连接S与

的所有边中，选择权数最小的边(i,k)；（3）将最小边(i,k)的另一个端点移入S；（4）若

则停止，否则返回（2）。2122例8.1有向树：不考虑方向时是树根树（外向树）：只有一个顶点入次为0，其余顶点入次为1根：入次为0的顶点叶：出次为0的顶点分支点层次：根到顶点的长度2024/8/16运筹学--线性规划23m叉树：每个顶点的出次小于等于m完全m叉树：每个顶点的出次等于m或02024/8/16运筹学--线性规划242024/8/16运筹学--线性规划25霍夫曼树：最优二叉树26第三节最短路问题最短路问题：对一个赋权的有向图D中的指定的两个点Vs(起点)和Vt（终点）找到一条从Vs

到Vt

的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。27适用于：每条弧（边）的赋权数wij≥0优点：能够求出某点至各点的最短路基本思想：T(j)（tentativelabel）——从始点s到j点的最短路长上界，称为试探性标号;P(j)

（permanentlabel）——从始点s到j点的最短路长，称为永久性标号.一、狄氏标号法（Dijkstra算法）例8-92024/8/16运筹学--线性规划28基本步骤标号T(j)→P(j)2024/8/16运筹学--线性规划292024/8/1630最长路问题例8-10（7-9）设某台新设备的年效益及年均维修费、更新净费用如表。试确定今后5年内的更新策略，使总收益最大。役龄项目012345效益vk(t)54.543.7532.5维修费uk(t)0.511.522.53更新费ck(t)-1.52.22.533.52024/8/16运筹学--线性规划31网络中心（r点）32例8-11某连锁企业有6个销售点，问仓库应建在哪个地点，可使各销售点离仓库较近？2024/8/16运筹学--线性规划33各点间的最短距离34二、Floyd算法2024/8/1635例8-12求任意两点间的最短路2024/8/16362024/8/16372024/8/16运筹学--线性规划38容量网络(网络)：N=(V,A,c)或

N=(V,A)，最大流量cij=c(i,j)网络流：可行流：s发点，t收点可行流流量：39第四节最大流问题割(截)集：S中各点联通，S

中各点联通始点在S，终点在S的集合，称为一个分离发点s和收点t的割集，（S,S）割集容量：最小割：最小的割集容量40定理8-10：网络任一可行流的流量恒不超过任一割集的容量。定理8-11：最大流=最小割2024/8/16运筹学--线性规划41增广（容）链：为从发点s到收点t的一条链，且前向弧均非饱和，后向弧均非零流。最大流：流量最大的可行流。可行流为最大流的充要条件：不存在从s到t的增广链2024/8/16运筹学--线性规划42（一）线性(整数)规划法例8-132024/8/1644（二）网络分析法增广链调整法45Ford—Fulkerson标号法基本思想：先确定一个初始可行流，再找增容链，调整流量，直到找不到增容链为止。双标号（i,b(j)），b(j)—当前最大可调容量运算步骤：发点s标号（0,∞）；给所有相邻点标号正向弧且，则j标号（i,b(j)）

，则j不标号逆向弧且，则j标号（-i,b(j)）检查标号调整量47

例8-13（1）计算机编程48

（2）手算f*=112024/8/16492024/8/1650最小费用最大流问题：给了一个带收发点的网络N=(V,A,c,d)，对每一条弧（i，j），除了给出容量cij外，还给出了这条弧的单位流量的费用dij，要求一个最大流f，并使得总运送费用最小。51先求出此网络图中的最大流量f。在最大流量f的所有解中，找出一个最小费用的解（一）线性(整数)规划法第五节最小费用最大流问题2024/8/1652例8-15第一步第二步53对偶网络