当前位置:首页 >> 其它 >>

运筹学11-图与网络


内容简介
?

?

?

?

是近几十年来运筹学领域中发展迅速、而且 十分活跃的一个分支. 对实际问题的描述具有直观性 广泛应用于物理学、化学、信息论、控制论、 计算机科学、社会科学以及现代经济管理科 学等许多科学领域. 图与网络分析的内容十分丰富.本章只介绍 图与网络的基本概念以及图论在路径问题、 网络流问题等领域中的应用.重点讲明方法 的物理概念、基本原理及计算步骤.

11.1 图与网络的基本概念
?

图的理论研究已有200多年的历史了.早期 图论与“数学游戏”有着密切关系.所谓 “哥尼斯堡七桥”问题就是其中之一.
200多年前的东普鲁士有一座 哥尼斯堡城,城中有一条河叫 普雷格尔河,河中有两个岛屿 共建七座桥.平时城中居民大 都喜欢来这里散步,并提出这 样一个问题:一个散步者能否 经过每座桥恰恰一次再回到原 出发点.

11.1 图与网络的基本概念

? ?

当时有许多人都探讨了这个问题,但不得其解. 著名数学家欧拉(Euler)将这个问题简化为一 个如右图所示图形.图4个点A、B、C、D表示 两岸和小岛.两两点间连线表示桥.

11.1 图与网络的基本概念
?

?

?
?

于是问题转化为一笔画问题,即能否从某一点开 始一笔画出这个图形,不许重复,最后回到原出 发点. 欧拉否定了这种可能性. 原因是图中与每一个点相关联的线都是奇数条. 为此他写下了被公认为世界第一篇有关图论方面 的论文(1736年)

11.1 图与网络的基本概念
?

1859年哈密尔顿提出了 另一种游戏:在一个实 心的12面体(见图)的 20个顶点上标以世界上 著名的城市名称,要求 游戏者从某一城市出发, 遍历各城市恰恰一次而 返回原地,这就是所谓 “绕行世界问题”.

11.1 图与网络的基本概念
?

?

?

作图,此问题变成在从某 一点出发寻找一条路径, 过所有20个点仅仅一次, 再回到出发点. 解决这个问题可以按序号 1—2—3—4一…一20—1 所形成的一个闭合路径, 并称此路径为哈密尔顿 圈. 具有哈密尔顿圈的图称为 哈密尔顿图.

11.1 图与网络的基本概念
?

?

?

?

由此可见,图论中所研究的图是由实际问题抽 象出来的逻辑关系图. 这种图与几何中的图形和函数论中所研究的图 形是不相同的. 这种图的画法具有一定的随意性,在保持相对 位置和相互关系不变的前提下,点的位置不一 定要按实际要求画,线的长度也不一定表示实 际的长度.而且画成直线或曲线都可以. 通俗地说,这种图是一种关系示意图.

11.1 图与网络的基本概念
? ?

图的概念 所谓图,就是顶点和边的集合,点的集合记为V, 边的集合记为E,则图可以表示为:G=(V,E), 点代表被研究的事物,边代表事物之间的联系, 因此,边不能离开点而独立存在,每条边都有两 个端点。 在画图时,顶点的位置、边和长短形状都是无关 紧要的,只要两个图的顶点及边是对应相同的, 则两个图相同。

?

图的表示
? ? (?1 ,? 2 ,?3 ,? 4 ,?5 ,? 6 ), E ? (e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 )

e1 ? [?1 ,? 2 ]
e3 ? [?1 ,? 4 ] e5 ? [?1 ,? 3 ]
e7 ? [? 3 ,? 4 ]

e2 ? [?1 ,? 2 ]

v1
e1 e2 e 3 e4 e5

e4 ? [?1 ,? 3 ]
e6 ? [? 2 ,? 4 ]

v2
e6 e7 e9

v3 v4
e8 v5 v6

e8 ? [?4 ,?4 ]

e9 ? [? 4 ,? 5 ]

点与边
?

顶点数 集合V中元素的个数, 记作p(G)。

v1

?

边数 集合E中元素的个数,记 作q(G)。
若e=[u,v]∈E,则称u和v为e的 端点,而称e为u和v的关联边, 也称u,v与边e相关联。 例如图中的图G,p(G)=6, q(G)=9, v1,v2是e1和e2的端点,e1和e2都 是v1和v2的关联边。

e1 e2 e 3 e4 e5
v2 v3

?

e6
v4

e7

e9

v5

?

?

e8

v6

点边关系 若点 u和 v与同一条边相 关联,则u和 v为相邻点; e1 e2 e3 e4 e5 若两条边ei和ej有同一个 v3 端点,则称ei与ej为相邻 v2 边。 e6 e7 例如在图中v1和v2为相 邻点, v1和v5不相邻; e1与e5为相邻边,e1和e7 不相邻。

v1

?

?

e9

v4 e8

v5

v6

简单图
?

若一条边的两个端点是同一 个顶点,则称该边为环;又 若两上端点之间有多于一条 e1 边,则称为多重边或平行边。 例如图的 e8为环, e1 , e2 为两 重边,e4,e5也是两重边。 无环也无多重边的图称作简 单图。

v1

e2 e 3 e4 e5
v3 e6 v4 e8 e7 e9 v5 v6

?

v2

? ?

含有多重边的图称作多重图。

图的次
?

次 点v作为边的端点的 次数,记作d(v),如图中, d(v1)=5, d(v4)=6等 端点次为奇数的点称作 奇点;次为偶数的点称 作偶点。

v1

?

e1 e2 e3 e4 e5
v2 e6 v4 e8 e7 e9 v3 v5 v6

?

次为 1的点称为悬挂点, 与悬挂点连接的边称作 悬挂边;
次为0的点称为孤立点。

?

?

图中的点 v5 即为悬挂点, 边e9即为悬挂边,而点v6 则是弧立点。

定理
?

若图G中所有点都是孤 立点,则称图G为空图。 定理1 所有顶点的次的 和,等于所有边数的2 倍。即

v1 e1 e2 e3 e4 e5 v3 e6 v4 e8 e7 e9 v5 v6

?

v2

??V

? d (? ) ? 2q

?

定理2 在任一图中, 奇点的个数必为偶数。

v1

?

设V1和V2分别是图G 中次数为奇数和偶数 v2 的顶点集合。由定理 1有

e1 e2 e3 e 4 e5
v3

e6
v4 e8

e7

e9

v5

d (? ) ? ? d (? ) ? 2q ? ? ?
?V1 ?V2

v6



?0 , e1 ,?1 , e2 ,? 2 ?,? n?1 , en ,? n
由两两相邻的点及 其相关联的边构成 的点边序列称为链。 v0称为链的起点, vn称为链的终点。
若v0 ≠vn则称该链为 开链,反之称为闭 链或回路。

?

v1 e1 e2 e3 e4 e5

?

v2
e6 e7 e9

v3 v4
e8 v5 v6

?

简单链
?

若链中所含的边均不 相同,则称为简单链; 若点均不相同,则称 为初等链或通路。 除起点和终点外点均 不相同的闭链,称为 初等回路或称为圈。 例如图中

v1 e1 e2 e3 e4 e5 v2 e6 v4 e7 v3

?

e9

v5
v6

?

?1 , e1 ,? 2 , e2 ,?1 , e3 ,? 4

e8

是一条链,且是开链,也是简单链,但不是初等链,因 为v1出现两次。


?

若链中所含的边均不 相同,则称为简单链; 若点均不相同,则称 为初等链或通路。除 起点和终点外点均不 相同的闭链,称为初 等回路或称为圈。 例如图中

v1

e1 e2 e3 e4 e5
v2 v3

e6
v4 e8

e7

?

e9

v5

?1 , e1 ,? 2 , e6 ,? 4 , e7 ,?3 , e4 ,?1
是一个圈。

v6

连通性
?

若一个图G的任意两点 之间均至少有一条通 路(初等链)连接起 来,则称这个图G是一 个连通图,否则称作 不连通图。 例如图中,v1和v6之间 没有通路,因此它不 是连通图,而如果去 掉v6,则构成一个连通 图。

v1

e1 e2 e3 e4 e5
v2 v3

e6
v4 e8

e7

?

e9

v5

v6

连通的意义
?

连通是一个很重要的 概念,如果一个问题 所对应的图是一个不 连通图,则该问题一 定可以分解成互不相 关的子问题来加以研 究,即可以把不连通 图分解成连通的子图 来研究。

v1

e1 e2 e3 e 4 e5
v2 v3

e6
v4 e8

e7

e9

v5

v6

子图
?

v1 e1 e2 e3 e4 e5

子图的定义 设, G1=(V1,E1), G2=(V2,E2), 如果V1?V2 ,又E1?E2 , 则称G1是G2的子图。
必须指出,并不是从图 G2中任选一些顶点和边 在一起就组成G2的子图 G1,而只有在G2中的一 条边以及连接该边的两 个端点均选入G1时,G1 才是G2的子图。

v2

v1

v3

e1 e2 e 3 e4 e5 v2 e6 v4 e7 e9 v3

v5
v6

e8

特殊子图
?

v1 e1 e2 e3 e4 e5

当G1中不包含G2中所有 的顶点和边,则称G1是 G2的真子图。 部分图 若V1=V2, E1?E2 ,则称G1为G2的 一个部分图。 若V1?V2 , E1={ [u,v] | u∈V1, v∈V1},则称G1是G2中 由V1导出的导出子图。

v2 v2
e6

v1

v3 v3
e7 e9

?

e1 e2 e3 e4 e5

? ?

v4
e8

v5 v6

有向图
?

在有些图中,边是没有方向的,即[u,v]=[v,u],这 种图称为无向图。 而有些关系是不对称的,例如父子关系、上下级 关系、加工工序的先后顺序等都具有单向性,用 图来表示这些关系时,得到的边是具有方向的, 用带箭头的线来表示,称为弧。 从顶点u指向υ的弧a,记作a=(u,v),(u,v)≠(v,u),其 中u称为a的起点,v称为a的终点,这样的图称为 有向图。仍以V表示点的集合,以A表示弧的集合, 则有向图表示为D=(V,A)

?

?

有向图例

v1

e1 e2 e 3 e4 e5
v2 e6 v4 e8 e7 e9 v3 v5 v6

有向图的链路
?

有向图中,在不考虑边的方向 时,也可以相同地定义链,若 有向图D=(V,A)中,P是一 个从u到v的链,且对P中每一条 弧而言,在序列中位于该弧前 面的点恰好是其起点,而位于 该弧后面的点恰好是其终点, 这个链P就称为是D中从u到v的 一条路。 当路的起点与终点相同,即u=v 时,称作一条回路。 顶点全不相同的路称为初等路。 除起点和终点外点均不相同的 回路称为初等回路。

v1

e1 e2 e3 e4 e5
v2 v3

e6
v4 e8

e7

e9

v5

?

? ?

v6

树及最小树问题
1

2

3 5

■任何树至少有一个悬挂节点 ■如果树的节点个数为m,则 边的个数为m-1 ■树中任意两个节点之间只有 唯一的一条链
2 2 1

4
3 5 4 3 5

■在树的任意两个不相邻的节 点之间增加一条边,则形成唯 一的圈

1

4

树及最小树问题
? 一个没有圈的图称为一个无圈图或称为林。 ? 一个连通的无圈图则称为树,一个林的每个连通子图都 是一个树。 定理 以下关于树的六种不同描述是等价的: 1. 2. 3. 4. 5. 6. 无圈连通图。 无圈,q=p-1。 连通,q=p-1。 无圈,但若任意增加一条边,则可得到一个且仅一个圈。 连通,但若任意舍弃一条边,图便不连通。 每一对顶点之间有一条且仅有一条链。

网络概念
? 图只能用来研究事物之间有没有某种关系,而不能 研究这种关系的强弱程度。 ? 网络 ?权 赋权的图 程度的度量,数量描述。 v2 2 8 9 5 1 v4 3

v1
6

3

v6 3 v5

v3

网络概念

■ 网络由节点和边组成
?

2 1 3 4

节点与(有向)边 每一条边和两个节点关联, 一条边可以用两个节点的标 号表示(i,j)
i j

2 1 3 4

■ 路径(Path)
前后相继并且方向相同的边序列

P={(1,2),(2,3),(3,4)}

网络概念 ■ 链(Chain)
前后相继并且方向不一定相同的边 序列称为链 C={(1,2),(3,2),(3,4)}
1 3 2 4

■ 回路(Circuit)
起点和终点重合的路径称为回路 μ={(1,2),(2,4),(4,1)} 回路中各条边方向相同
1

2 4 3

网络概念 ■ 圈(Cycle)
起点和终点重合的链称为圈 ρ ={(1,2),(2,4),(3,4),(1,3)} 圈中各条边方向不一定相同
1
3 2 4

■ 连通图
任意两个节点之间至少有一条 链的图称为连通图
2 1

■ 树(Tree)
无圈的连通图称为树 树中只与一条边关联的节点称 为悬挂节点

3 5 4

网络概念
?

?

? ?

平面图(planar graph),若在平面上可以画 出该图而没有任何边相交 走过图中所有边且每条边仅走一次的闭行走 称为欧拉回路 定理 :偶图一定存在欧拉回路(一笔画定理) 图中都是偶点的图称为偶图(even graph)

哈密尔顿回路( Hamiltonian circuit)问题
?

?

? ? ? ? ? ? ? ?

连通图G(V,E)中的回路称为哈密尔顿回路,若该回路包括 图中所有的点。显然哈密尔顿回路有且只有 n 条边,若 |V|=n 连通图具有哈密尔顿回路的充分必要条件是什么?这个问 题是由爱尔兰数学家哈密尔顿1859年提出的,但至今仍未 解决 欧拉回路是对边进行访问的问题,哈密尔顿回路是对点进 行访问的问题 搜索哈密尔顿回路的难度是 NP-complete 任两点间都有边的图称为完全图(或全连接图) 完全图中有多少个不同的哈密尔顿回路? (n–1)!/2 完全图中有多少个边不相交的哈密尔顿回路? (n–1)/2 最小哈密尔顿回路问题 (NP-complete) 哈密尔顿路径:包含图中所有点的路径 为什么说找两点间的最长路是非常困难的问题?

中国邮递员问题
中国邮递员问题(Chinese Postman Problem, CPP)是 由我国管梅谷教授于1962年首先提出并发表的 ? 问题是从邮局出发,走遍邮区的所有街道至少一次再 回到邮局,走什么路由才能使总的路程最短? ? 如果街区图是一个偶图,根据定理 3,一定有欧拉回 路,CPP问题也就迎刃而解了 ? 若街区图不是偶图,则必然有一些街道要被重复走过 才能回到原出发点 ? 显然要在奇次点间加重复边 A ? 如何使所加的边长度最少 C ? 归结为求奇次点间的最小 匹配( minimum weighted match) B — 由Edmons 给出多项式算法(1965)
?

D

旅行推销员问题(Traveling Salesman Problem)
?

TSP:设v1, v2, ...,vn 为 n 个已知城市,城市之间的 旅程也是已知的,要求推销员从 v1出发,走遍所有城市
一次且仅一次又回到出发点,并使总旅程最短 这种不允许点重复的旅行推销员问题就是最小哈密尔顿 回路问题 一般旅行推销员问题(GTSP):允许点重复的TSP 典型的应用: 乡邮员的投递路线 邮递员开邮箱取信的路线问题 邮车到各支局的转趟问题 运钞 送奶、送水 ….

?

?
? ? ? ? ? ? ?

网络最短树问题
?

最短树问题的一般提法是:选取网络中的部分图, 使得网络连通,且使总权数最短。 在实际应用中,经常碰到需要求一个赋权连通图的 最短树的问题。例如,用节点表示城市,用边表示 可以在两个城市之间架设光缆,边上的权表示光缆 的长度,试求应如何架设光缆,才能使任意两城市 之间均由光缆相通,且使光缆的总长度最短。 求最短树的方法,依据的是树的特点,即无圈和连 通,加上最短的要求,方法主要有两种:一种称为 破圈法,一种称为避圈法

?

?

11.2 最短路问题
?

?

最短路问题的一般提法是:欲寻找网络中从 起点υ1 到终点υn 的最短路线,即寻求连接 这两点的边的总长度为最小的通路,最短路 线中的网络大都是有向网络,也可以是无向 网络。 最短路问题是网络分析中的一个基本问题, 它不仅可以直接应用于解决生产实际的许多 问题,如管道铺设、线路安排、厂区布局等, 而且经常被作为一个基本工具,用于解决其 它的优化问题。

最短路问题的Dijkstra算法(双标号法)
步骤: 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I,没标号的点的集合J以及弧的集合 3.如果上述弧的集合是空集,则计算结束。如果vt已标号 (lt,kt),则 vs到vt的距离为lt,而从 vs到vt的最短路径, 则可以从kt反向追踪到起点vs 而得到。如果vt 未标号,则 可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不 是空集,则转下一步。 4. 对上述弧的集合中的每一条弧,计算 sij=li+cij 。在所 有的 sij中,找到其值为最小的弧。不妨设此弧为(Vc,Vd), 则给此弧的终点以双标号(scd,c),返回步骤2。

?

例1 求下图中v1到v6的最短路 3 v1 2 v2 5 2 1 7

v4 5
5 3 1

v6

? ?

v5 v3 解:采用Dijkstra算法,可解得最短路径为v1 各点的标号图如下:
3
V1 (0,s) 2 (3,1) v2 5 7 (3,3) 5 v4 3 5 (8,4) v6

v3

v4

v6

2
1

1 v5

(2,1) v3

?

例2 电信公司准备在甲、乙两地沿路架设一条光缆线,问如何架设使 其光缆线路最短?下图给出了甲乙两地间的交通图。权数表示两地间 公路的长度(单位:公里)。

V7 (乙地)
17 v2 15
(甲地)

6

5 v4 4 2 v5

6

V1

43

10
?

4

v6

v3 解:这是一个求无向图的最短路的问题。可以把无向图的每一边 (vi,vj)都用方向相反的两条弧(vi,vj)和(vj,vi)代替,就化为有 向图,即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算 法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改 成已标号的点到未标号的点的边的集合即可。

? ?

例2最终解得: 最短路径v1 v3

v5

v6

v7,每点的标号见下图

(22,6) V7 (乙地) (13,3) v2 15 (0,s) V1 (甲地) 10 3 4 V3 (10,1) 6 V4 (18,5) 4 V5 (14,3) 17 5

6
2 V6 (16,5)

?

?

例3 设备更新问题。某公司使用一台设备,在每年年初,公司就要决 定是购买新的设备还是继续使用旧设备。如果购置新设备,就要支付 一定的购置费,当然新设备的维修费用就低。如果继续使用旧设备, 可以省去购置费,但维修费用就高了。请设计一个五年之内的更新设 备的计划,使得五年内购置费用和维修费用总的支付费用最小。 已知:设备每年年初的价格表 年份 年初价格 1 11 2 11 3 12 4 12 5 13

?

设备维修费如下表 使用年数 每年维修 费用 0-1 5 1-2 6 2-3 8 3-4 11 4-5 18

例3的解:将问题转化为最短路问题,如下图: 用vi表示“第i年年初购进一台新设备”,弧(vi,vj)表示第i年年初购进的 设备一直使用到第j年年初。
?

v1
?

v2

v3

v4

v5

v6

把所有弧的权数计算如下表:
1 1 2 3 4 5 6 2 16 3 22 16 4 30 22 17 5 41 30 23 17 6 59 41 31 23 18

(继上页) 把权数赋到图中,再用Dijkstra算法求最短路。
59
22

30

41
v4 23

23 17 v5
31 18

v1

16

v2

16 v3 17 22 30

v6

41

最终得到下图,可知,v1到v6的距离是53,最短路径有两条: v1 ---v3---v6和 v1---v4---v6
59 22 V1 (0,s) 30 41 (30,1) v4 23 41 17 31 18 (41,1) v5 v6 (53,3) (53,4) 23

16

16 v3 17 V2 (16,1) (22,1) 30

11.4 网络最大流问题
? 所谓最大流问题就是在一定的条件下,要求流过网络 的物流、能量流或信息流等流量为最大的问题,在最 大流问题中一般有如下规定: 1) 网络有一个起点υs和一个终点υt

2) 网络是有向网络,即流有方向性。
3) 在网络各条弧上都有一个权,表示允许流过的最大流 量。若以bij表示由υi到υj的弧上允许流过的最大流量, 以xij表示实际流过该弧的流量,则0≤ xij ≤bij 4) 网络中,除起点 υs 和终点 υt 之外的任何顶点,流入量 总和应该等于流出量的总和。

一、最大流问题的数学模型
Max f ? ?? f ? ? x ? x ? ?? ji ? ij ? 0 j ? j ? f ? ? ?0 ? xij ? bij ?
v2 7 v4

s.t

i?s i ? s,t i?t

15
vs 9 v3 3

4
5 6 v5

11
vt 10

二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向,如下图: (a)和 (b)、(c)和(d)的意义相同。

vi

cij

cij vj vi cij ( d)

0

( a) cij

( b)
cji

vj

vi

(cji) (c)

vj

vi

vj

求最大流的基本算法 (1)找出一条从发点到收点的路,在这条路上的每一条弧顺流方向的容 量都大于零。如果不存在这样的路,则已经求得最大流。 (2)找出这条路上各条弧的最小的顺流的容量pf,通过这条路增加网络 的流量pf。 (3)在这条路上,减少每一条弧的顺流容量pf ,同时增加这些弧的逆 流容量pf,返回步骤(1)。

例6 某石油公司拥有一个管道网络,使用这个网络可以把 石油从采地运送到一些销售点,这个网络的一部分如下图 所示。由于管道的直径的变化,它的各段管道(vi,vj)的 流量cij(容量)也是不一样的。cij的单位为万加仑/小时。 如果使用这个网络系统从采地 v1向销地 v7运送石油,问每 小时能运送多少加仑石油?
v2 6 v1 6 v4 3 2 3 2 5 2 v6 4 v7

v3
1

2

迭代运算步骤请见演示

11.5 最小费用最大流问题
最小费用最大流问题:给了一个带收发点的网络,对每一条弧 (vi,vj),除了给出容量cij外,还给出了这条弧的单位流量的费用bij,要 求一个最大流F,并使得总运送费用最小。 一、最小费用最大流的数学模型 例7 由于输油管道的长短不一,所以在例6中每段管道( vi,vj )除 了有不同的流量限制cij外,还有不同的单位流量的费用bij ,cij的单位为万 加仑/小时, bij的单位为百元/万加仑。如图。从采地 v1向销地 v7运送石 油,怎样运送才能运送最多的石油并使得总的运送费用最小?求出最大流 v5 量和最小费用。 (3,4)
?

v2

(6,6) v1 (6,3)

(2,5) v3 (3,2)

(2,4)

(5,7)

(2,3)
(2,8)

v6 (4,4)

v7

(1,3)

v4

二、最小费用最大流的网络图论解法 对网络上弧(vi,vj)的(cij,bij)的表示作如下改动,用(b)来表示(a)。

vi

(cij,bij )
(a) (cij,bij )

vj

(cij,bij ) (0,-bij ) vi vj (b)
(cij,bij ) (0,-bji) vj vi vj

vi

(cji,bji ) ( c)

(0,-bji) (cji,bji ) (d)


相关文章:
运筹学11-图与网络.ppt
运筹学11-图与网络 - 内容简介 ? ? ? ? 是近几十年来运筹学领域中发展
运筹学 第11章 图与网络模型.ppt
运筹学11图与网络模型 - 第十一图与网络模型 §1 图与网络的基本
运筹学11-图与网络.ppt
运筹学11-图与网络 - 第十一章 图与网络规划 11.1 图与网络的基本概念
运筹学 图与网络分析(11-11).ppt
运筹学 图与网络分析(11-11) - 第八章 图与网络分析 引例 哥尼斯堡七桥
运筹学第11章 图与网络论.ppt
运筹学11图与网络论 - ? 引论 哥尼斯堡七桥问题 A C B A 简捷
管理运筹学 第11章 图与网络模型.ppt
管理运筹学11图与网络模型 - 第十一图与网络模型 §1 图与网络的基本概念 §2 最短路问题 §3 最小生成树问题 §4 最大流问题 §5 最小费用...
运筹学11-图与网络-1.pdf
运筹学11-图与网络-1_管理学_高等教育_教育专区。华中科技大学管理学院运筹学
《管理运筹学》第11章 图与网络模型.ppt
《管理运筹学》第11图与网络模型 - 第十一图与网络模型 §1 图与网络的基本概念 §2 最短路问题 §3 最小生成树问题 §4 最大流问题 §5 最小...
第11章__图与网络模型_运筹学.ppt
11章__图与网络模型_运筹学 - 第十一图与网络模型 §1 图与网络的基
管理运筹:第11章图与网络模型.ppt
管理运筹:第11图与网络模型 - 管理运筹学 (11) 1 管理运筹学 南京财经大学工商管理学院 李时椿 第十一图与网络模型 ? 图与网络的基本概念 ? 最短路径...
第11章 图与网络模型 (管理运筹学 第三版 课件 共17章 ....ppt
11图与网络模型 (管理运筹学 第三版 课件 共17章 韩伯棠)_管理学_高等教育_教育专区。(管理运筹学 第三版 课件 共17章 韩伯棠) ...
第11章图与网络模型..ppt
11图与网络模型. - 第十一图与网络模型 管 理 运 筹 学 1 引言
第11章 图与网络模型.ppt
11图与网络模型 - 第十一图与网络模型 §1 图与网络的基本概念 §
第11章 图与网络模型.ppt
11图与网络模型 - 第十一图与网络模型 图与网络分析(Graph Theory and Network Analysis),是近几十年 来运筹学领域中发展迅速、而且十分灵活的一个分...
运筹学第六章图与网络分析.ppt
运筹学第六章图与网络分析 - 第六章 6.1 6.2 6.3 6.4 6.5 6.6 图与网络分析 图的基本概念与数学模型 树图和图的最小部分树 最短路问题 中国邮路问题...
运筹学_图与网络分析.ppt
运筹学_图与网络分析 - 第八章图与网络分析 ? ? ? ? ? 图的基本概念
11第十一章 图与网络模型.ppt
管理运筹学十一图与网络模型 本章内容 1 2 3 4 5 11.1 §1 图与网络的基本概念 图论中图是由点和边构成,可以反映一些对象之间的 关系。例如:一个...
运筹学图与网络.ppt
运筹学图与网络 - 第五章 图与网络模型(Graph and network m
运筹学-图与网络模型以及最小费用最大流分解.ppt
运筹学-图与网络模型以及最小费用最大流分解 - Chapter11 图与网络分析 ( Graph Theory and Network Analysis ) 本章主要内容: 图与网络的基本概念与...
运筹学-图与网络模型以及最小费用最大流.详解.ppt
运筹学-图与网络模型以及最小费用最大流.详解 - Chapter11 图与网络分析 ( Graph Theory and Network Analysis ) 本章主要内容: 图与网络的基本概念...