运筹学第八章-图与网络分析.pptx

运筹学运筹学赵明霞明霞山西大学山西大学经济与管理学院与管理学院2 第八章第八章图与网与网络分析分析 图与网与网络的基本概念的基本概念 树 最短路最短路问题 最大流最大流问题 最小最小费用最大流用最大流问题2024/5/26 周日3 柯尼斯堡七柯尼斯堡七桥问题欧拉回路欧拉回路：经过每每边且且仅一次一次 厄尼斯堡七厄尼斯堡七桥问题、邮路路问题哈密哈密尔顿回路回路：经过每点且每点且仅一次一次 货郎担郎担问题、快、快递送送货问题4第一第一节图与网与网络的基本概念的基本概念图是由点和是由点和边构成，可以反映一些构成，可以反映一些对象之象之间的关系。的关系。例如：在一个人群中，例如：在一个人群中，对相互相互认识这个关系我个关系我们可以用可以用图来来表示，表示，图8.18.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 如果我如果我们把上面例子中的把上面例子中的“相互相互认识”关系改关系改为“认识”的关系，那么只用两点之的关系，那么只用两点之间的的联线就很就很难刻画他刻画他们之之间的的关系了，关系了，这是我是我们引入一个引入一个带箭箭头的的联线，称，称为弧弧。p无向无向图：由点和：由点和边构成的构成的图，记作作G=G=（V V，E E）。p有向有向图：由点和弧构成的：由点和弧构成的图，记作作D=D=（V V，A A）。无向无向图是有向是有向图的的基基础图G(DG(D)u有限有限图u无限无限图2024/5/26 周日.-线性规划7G=(V,E)关关联边(m)：ei端（端（顶）点）点(n)：vi,vj点相点相邻(同一条同一条边)：v1,v3边相相邻(同一个端点同一个端点)：e2,e3 环：e1 多重多重边：e4,e58简单图：无无环无多无多重重边多重多重图：多多重重边2024/5/26 周日.-线性规划9完全完全图：每一：每一对顶点点间都有都有边（弧）相（弧）相连的的简单图2024/5/26 周日.-线性规划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 1 顶点次数点次数总和等于和等于边数的两倍。数的两倍。定理定理2 2 次次为奇数的奇数的顶点必点必为偶数个。偶数个。11若若 ,则GG是是G G的的子子图，G G是是GG的的母母图若若 ,则GG是是G G的的真子真子图，若若 ,则GG是是G G的的支撑（生成）支撑（生成）图。链：点：点边交替序列交替序列 闭链：v1 v2 v3 v4 v1 开开链：v1 v2 v3 u边不同，不同，简单链：v3 v4 v5v1v6v5u边不同且不同且结点不同，点不同，初等初等链：v1 v2 v3 v4 v5v6 圈：圈：闭链，且至少有，且至少有3个不同个不同结点点，v2 v3 v4 v2 初等圈：初等圈：初等初等闭链，v1 v2 v3 v4 v112路路：有向：有向图：弧的方向与弧的方向与链的方向一致的方向一致开路开路:v1v2v4v5回路回路：第一个点和最后一个点相同：第一个点和最后一个点相同。v1v2v4v5v113 连通通图：若任何两个不同的点之：若任何两个不同的点之间，至少存在一条，至少存在一条链，则G G为连通通图。赋权图：对一个一个图的每一条的每一条边（弧）（弧）(vi,vj)，相，相应地有一个地有一个数数wij，则称称图G G为赋权图，wij称称为边(vi,vj)上的上的权。网网络：赋权连通通图无向无向图：开开链即开路，即开路，闭链即回路即回路有向有向图：弧的方向与弧的方向与链的方向一致的方向一致。2024/5/26 周日.-线性规划142024/5/26 周日15 柯尼斯堡七柯尼斯堡七桥问题欧拉回路欧拉回路：经过每每边且且仅一次一次 厄尼斯堡七厄尼斯堡七桥问题、邮路路问题 充要条件：充要条件：无向无向图中无奇点，有向中无奇点，有向图每个每个顶点出次等于入次点出次等于入次16第二第二节树 树是是图论中的重要概念，所中的重要概念，所谓树就是一个就是一个无圈的无圈的连通通图。图8-4中，中，(a)就是一个就是一个树，而，而(b)因因为图中有圈所以就不是中有圈所以就不是树，(c)因因为不不连通所以也不是通所以也不是树。图8-4v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)树的基本性的基本性质1.1.任意两点任意两点间有且有且仅有一条有一条链2.2.不相不相邻两点两点间添加一条添加一条边，有且，有且仅有一个圈有一个圈3.3.任意去掉一条任意去掉一条边，得不，得不连通通图.4.4.存在存在悬挂点挂点5.5.m=n-1m=n-11718 (a)(b)(c)生成（支撑）生成（支撑）树若若 ,则GG是是G G的的支撑（生成支撑（生成）树。191 1、破圈算法、破圈算法步步骤：（1 1）在）在给定的定的赋权的的连通通图上任找一个圈。上任找一个圈。（2 2）在所找的圈中去掉一个）在所找的圈中去掉一个权数最大的数最大的边（如果有两条或两（如果有两条或两条以上的条以上的边都是都是权数最大的数最大的边，则任意去掉其中一条）。任意去掉其中一条）。（3 3）如果所余下的）如果所余下的图已不包含圈，已不包含圈，则计算算结束，所余下的束，所余下的图即即为最小最小树，否，否则返回第返回第1 1步。步。最小生成最小生成树问题就是指在一个就是指在一个赋权的的连通的无向通的无向图G G中找出一中找出一个生成个生成树，并使得，并使得这个生成个生成树的所有的所有边的的权数之和数之和为最小。最小。20例例8.12、避圈、避圈算法算法 步步骤：（1 1）任）任找一找一个点个点S S，其余各点就是，其余各点就是 。（2 2）在在连接接S S与与 的所有的所有边中，中，选择权数最小的数最小的边(i,k)；（3 3）将最小）将最小边(i,k)的另一个端点移入的另一个端点移入S S；（4 4）若）若 则停止，否停止，否则返回（返回（2 2）。）。2122例例8.1 有向有向树：不考不考虑方向方向时是是树 根根树（外向（外向树）：只有一个：只有一个顶点入次点入次为0 0，其余，其余顶点入次点入次为1 1根根：入：入次次为0 0的的顶点点叶叶：出次：出次为0 0的的顶点点分支点分支点层次次：根到：根到顶点的点的长度度2024/5/26 周日.-线性规划23 m m叉叉树：每个：每个顶点的出次小于等于点的出次小于等于m m 完全完全m m叉叉树：每个：每个顶点的出点的出次等次等于于m m或或0 02024/5/26 周日.-线性规划242024/5/26 周日.-线性规划25 霍夫曼霍夫曼树：最最优二叉二叉树26第三第三节最短路最短路问题最短路最短路问题：对一个一个赋权的有向的有向图D D中的指定的两个点中的指定的两个点V Vs s(起点起点)和和V Vt t（终点）找到一条从点）找到一条从 V Vs s 到到 V Vt t 的路，使得的路，使得这条路上条路上所有弧的所有弧的权数的数的总和最小和最小，这条路被称之条路被称之为从从V Vs s到到V Vt t的最短路。的最短路。这条条路上所有弧的路上所有弧的权数的数的总和被称和被称为从从V Vs s到到V Vt t的距离。的距离。27 适用于适用于：每条弧（：每条弧（边）的）的赋权数数wij 0 优点点：能：能够求出某点至各点的最短路求出某点至各点的最短路 基本思想基本思想：T(j)（tentative label）从始点从始点s到到j点的点的最短路最短路长上界上界，称称为试探性探性标号号;P(j)（permanent label）从始点从始点s到到j点的点的最短路最短路长，称称为永久性永久性标号号.一、狄氏一、狄氏标号法（号法（Dijkstra算法）算法）例例8-98-92024/5/26 周日.-线性规划28基本步基本步骤标号号T(j)P(j)2024/5/26 周日.-线性规划292024/5/26 周日30 最最长路路问题 例例8-108-10（7-97-9）设某台新某台新设备的年效益及年均的年效益及年均维修修费、更新、更新净费用如表。用如表。试确定今后确定今后5 5年内的更新策略，使年内的更新策略，使总收益最大收益最大。役役龄项目目012345效益效益vk(t)54.543.7532.5维修修费uk(t)0.511.522.53更新更新费ck(t)-1.52.22.533.52024/5/26 周日.-线性规划31网网络中心（中心（r r点）点）32例例8-11 8-11 某某连锁企企业有有6 6个个销售点，售点，问仓库应建在哪个地点，建在哪个地点，可使各可使各销售点离售点离仓库较近？近？2024/5/26 周日.-线性规划33各点各点间的最短距离的最短距离34二、二、Floyd算法算法2024/5/26 周日35例例8-12 8-12 求任意两点求任意两点间的最短路的最短路2024/5/26 周日362024/5/26 周日372024/5/26 周日.-线性规划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-108-10：网：网络任一可行流的流量恒不超任一可行流的流量恒不超过任一割集任一割集的容量。的容量。定理定理8-118-11：最大最大流流 =最小最小割割2024/5/26 周日.-线性规划41 增广（增广（容容）链：为从从发点点s s到收点到收点t t的一条的一条链，且前向，且前向弧均非弧均非饱和，后向弧均非零流。和，后向弧均非零流。最大最大流流：流量最大的可行流。：流量最大的可行流。可行可行流流为最大流的最大流的充要条件充要条件：不存在从：不存在从s s到到t t的增广的增广链2024/5/26 周日.-线性规划42（一）（一）线性性(整数整数)规划法划法 例例8-132024/5/26 周日44（二）网（二）网络分析法分析法增广增广链调整法整法45FordFulkerson标号法号法 基本思想基本思想：先确定一个初始可行流，再找增容：先确定一个初始可行流，再找增容链，调整流量，直到找不到增容整流量，直到找不到增容链为止。止。双双标号（号（i,b(j)），），b(j)当前最大可当前最大可调容量容量 运算步运算步骤：1.1.发点点s标号（号（0,）；）；2.2.给所有相所有相邻点点标号号正向弧正向弧且且 ，则 j 标号（号（i,b(j)），则 j 不不标号号逆向弧逆向弧且且 ，则 j 标号（号（-i,b(j)）3.3.检查标号号4.4.调整量整量47 例例8-138-13（1 1）计算机算机编程程48（2 2）手算）手算f*=112024/5/26 周日492024/5/26 周日50 最小最小费用最大流用最大流问题：给了一个了一个带收收发点的网点的网络N N=(=(V V,A A,c c,d d)，对每一条弧（每一条弧（i，j），除了），除了给出容量出容量cij外，外，还给出了出了这条弧条弧的的单位流量的位流量的费用用dij，要求一个最大流，要求一个最大流f，并使得，并使得总运送运送费用用最小。最小。511.1.先先求出此网求出此网络图中的最大中的最大流量流量f f。2.2.在在最大最大流量流量f f的的所有解中，找出一个最小所有解中，找出一个最小费用的用的解解（一）（一）线性性(整数整数)规划法划法第五第五节最小最小费用最大流用最大流问题2024/5/26 周日52例例8-158-15第一步第一步第第二二步步53 对偶网偶网络法法：N=(V,A)，N=(V,A,w)xij=0,0 xij cij,xij=cij，（二）网（二）网络分析法分析法 定理定理8-78-7：对偶网偶网络中的最短路必是原网中的最短路必是原网络的最小的最小费用增容用增容链。定理定理8-88-8：在流量：在流量为f f的最小的最小费用流上，按最小用流上，按最小费用增容用增容链调整整流量后，仍流量后，仍为新流量上的最小新流量上的最小费用流。用流。基本思想基本思想：找出：找出对偶网偶网络的最短路的最短路，沿此路，沿此路调整流量，直到最整流量，直到最大流量。大流量。运算步运算步骤542024/5/26 周日5556作作 业u8.18.1u8.68.6u8.88.8u8.108.10u8.178.17