当前位置：文档之家 › 图与网络(4)

图与网络(4)

  • 格式：ppt
  • 大小：684.00 KB
  • 文档页数：97

下载文档原格式

  / 97

合集下载

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

运筹学第八章--图与网络分析-胡运权
运筹学
赵明霞山西大学经济与管理学院
2
第八章 图与网络分析
图与网络的基本概念 树 最短路问题 最大流问题 最小费用最大流问题
3
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题哈密尔顿回路：经过每点且仅一次 货郎担问题、快递送货问题
例8-9
28
基本步骤标号T(j)→P(j)

29
2017/10/26
30
最长路问题例8-10（7-9）设某台新设备的年效益及年均维修费、更新净费用如表。试确定今后5年内的更新策略，使总收益最大。
役龄项目
0
1
2
3
4
5
效益vk(t)
5
4.5
4
3.75
3
2.5
14
15
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题 充要条件：无向图中无奇点，有向图每个顶点出次等于入次
16
第二节 树
树是图论中的重要概念，所谓树就是一个无圈的连通图。
图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。
7
G=(V,E)关联边(m)：ei端（顶）点(n)：vi, vj点相邻(同一条边)： v1, v3边相邻(同一个端点)：e2, e3环：e1多重边： e4, e5
8
简单图：无环无多重边
多重图：多重边
9
完全图：每一对顶点间都有边（弧）相连的简单图
10
次（d）：结点的关联边数目d(v3)=4，偶点d(v2)=3，奇点d(v1)=4d(v4)=1，悬挂点e6, 悬挂边d(v5)=0，孤立点
（一）线性(整数)规划法

第五章 图与网络PPT课件

第五章 图与网络PPT课件
26
解 将所有顶点都放入集合 S{v1,v2,v3,v4,v5,v6,v7}
集合 S 暂时为空集
第一步：
在 v 1 处标号0，记 S {v1} ，此时
S{v2,v3,v4,v5,v6,v7}
第二步：
d ( v 1 ,v 2 ) d ( v 1 ) ( v 1 ,v 2 ) 0 1 1 d ( v 1 ,v 3 ) d ( v 1 ) ( v 1 ,v 3 ) 0 4 4
或用边的两个顶点记为( v i , v j ) 圈：某一条边的两个顶点相同，则称 v 1
e1
这条边为圈（或环）
e5 e3
v
平行边（或多重边）：若两点之间有多条边，
3
则称这些边为平行边（或多重边）
e4 v2 e2
8
引例【生产流程】
在“西气东输”工程中，天然气管道从 甲
城市经乙城或丙城都可到达丁城市，而且 乙城和丙城之间也有管道相通，如下图所 示，试将城市间的管道连接用图表示
在v 6 处标号4，记d(v6) 4，此时 S{v1,v2,v3,v6}
S {v4,v5,v7}
29
第五步：
d ( v 2 ,v 4 ) d ( v 2 ) ( v 2 ,v 4 ) 1 4 5 d ( v 2 ,v 5 ) d ( v 2 ) ( v 2 ,v 5 ) 1 7 8 d ( v 6 ,v 5 ) d ( v 6 ) ( v 6 ,v 5 ) 4 3 7 d ( v 6 ,v 7 ) d ( v 6 ) ( v 6 ,v 7 ) 4 6 1 0 m i n { d ( v 2 , v 4 ) ， d ( v 2 , v 5 ) ， d ( v 6 , v 5 ) , d ( v 6 , v 7 ) } 5

《图与网络分析》课件

《图与网络分析》课件

广度优先搜索
2
历图中的节点。
通过按逐层扩展的方式，搜索和遍历图 中的节点。
最短路径算法
1
Dijkstra算法
寻找两个节点之间最短路径的一种算法，适用于无负权重边的情况。
2
Floyd算法
寻找所有节点之间最短路径的一种算法，适用于有向图和无向图。
最小生成树算法
1
Prim算法
找出连接所有节点的最小成本树的算法。
Kruskal算法
2
找出连接所有节点的最小成本树的另一 种算法。
应用案例
1 社交网络分析
通过图与网络分析方法， 揭示社交网络中的关键人 物和社群结构。
2 物流网络优化
使用图与网络分析技术来 优化物流网络的路径和资 源分配。
3 路网分析
通过图与网络分析，提高 交通规划和城市布局的效 率。
网络分析的思路
顶点
网络中的数据节点或实体。
边
连接顶点的关系或连接。
权重
边的属性或度量，用于表示连接的强度或重要性。
图的分类与存储结构
有向图
边具有方向性，表ห้องสมุดไป่ตู้顶点之间 的单向关系。
无向图
边没有方向性，表示无序关系。
加权图
边具有权重，表示连接的强度 或重要性。
图搜索算法
1
深度优先搜索
通过探索尽可能深入的路径，搜索和遍
网络分析的思路是通过对网络结构和属性的分析，揭示出潜在的模式、关系和洞察力，帮助我们洞悉复杂系统 的运作。
《图与网络分析》PPT课 件
欢迎来到《图与网络分析》PPT课件！本课程将帮助您深入了解图网络分析的 概念和应用。准备好探索各种令人兴奋的网络分析方法和工具了吗？让我们 开始吧！

图与网络分析(GraphTheoryandNetworkAnalysis)

图与网络分析(GraphTheoryandNetworkAnalysis)

e9
e5 {v1 , v3 } e6 {v3 , v5 }
e7 {v3 , v5 } e8 {v5 , v6 }
e9 {v6 , v6 } e10 {v1 , v6 }
e1
e2
v2
e5 e3 e4 v4
e8
e6
v5 e7 v3
图1
2、如果一个图是由点和边所构成的，则称其为无向图，记作
X={1}, w1=0
p1=0
2
6
1
2
3
1
10
p4=1
5
9
3
4
7
5
6
5
2
3
4
6
7
4
8 8
min {c12,c14,c16}=min {0+2,0+1,0+3}=min {2,1,3}=1 X={1,4}, p4=1
（9） T (v6 ) min[ T (v6 ), P(v5 ) l56 ] min[ , 5 2] 7 （10） P(v6 ) 7
反向追踪得v1到v6的最短路为：v1 v2 v5 v6
求从1到8的最短路径
2
6
1
2
3
1
10
5
9
3
4
7
5
6
5
2
3
4
6
7
4
8 8
v2
v5
v2
v4
v3
v4
v3
一个图G 有生成树的充要条件是G 是连通图。
用破圈法求出下图的一个生成树。
v2
e1 v1
e4 e7 e3 v4 e8

运筹学：第2章 图与网络分析 第4节 最大流

运筹学：第2章 图与网络分析 第4节 最大流

v2
13 (5)
6(3)
v5
9 (5)
5 (2)
v1
4 (1) 5 (2)
v4
9 (3)
v3
5 (0)
4 (2) 4 (1)
v6
v7
10 (1)
设 V1 v1 , v2 , v5 ，V2 v3 , v4 , v6 , v7 则截集为
(V1,V2 ) (v1v3 ), (v2 , v4 ), (v5 , v7 ) 截量为24
凡与u方向相同的称为正向弧； 凡与u方向相反的称为反向弧； 其集合分别用u+和u-表示。 f 是一个可行流，如果满足：
0 fi j ci j 0 fi j ci j
(vi , vj ) 即μ+中的每一条弧都是非饱和弧 (vi , vj ) 即μ-中的每一条弧都是非零流弧
则称 u为从vs到vt 的关于f 的一条增广链。
是一个（V，A，C），vs为始点，vt为终点。如 果把V分成两个非空集合V1 ,V2(V1 V2 ,V1 V2 V )
使vs V1 ,vt V2 ，则所有始点属于V1 ，而终点属于 V2的 弧的集合，称为D的截集,记作 (V1 ,V2。) 截集(V1 ,V2)中所有弧的 容量之和，称为这个截集的截量，记为C(V1,V2) 。
2 ．把节点集V分成VA ：已标号点集
VB ：未标号点集
3．考虑所有这样的弧(vi ，vj) 或(vj，vi ) ，其中vi VA，v j VB
若该弧为
（1）流出未饱弧，那么给vj标号(θj, vi) ，其中： θj=cij-fij
（2）流入非零弧，那么给vj标号(θj, -vi) ，其中： θj=fij 4．重复步骤2，3，直到vt被标号或标号过程无法进行下去 ，则标号结束。

图与网络分析

图与网络分析
图与网络分析
引言 第一节 图与网络的基本概念 第二节 树 第三节 最短路径问题 第四节 网络最大流问题 第五节 最小费用最大流问题
引言
图论(Graph Theory)是研究图的理论, 是运筹学中一重要 的分支. 有200多年历史, 大体可划分为三个阶段.
图论发展的三个阶段
第一阶段
第二阶段
第三阶段
从十八世纪中叶 到十九世纪中叶
e1
v1
e2
v2
v6
e5
e6
e3
v4
e8
e4
图－9
v3 e7 v5
定义4: 若图G=(V,E)的点集V可分为两个非空子集X, Y, 满 足: XY=V, XY=, 使得E中的每条边的两上顶点必有 一个端点属于X,而另一个端点Y,则称G为二部图(偶图)
v1
e1
v2
v1
U1
e4
e2
v2
v3
U2
v4
C
River
7
5
3
D
2
B 图－1
Euler在1736年发表了一篇题为“依据几何位置的解题 方法”论文,有效解决了Konigsber七桥难题,这是有记 载的第一篇图论论文,Euler也被公认为图论的创始人.
A
C
D
B
例2: Hamilton回路是19世纪英国数学家Hamilton提出
给出一个正12面体图形,共有20个顶点,分别表示全球20个主 要城市,要求从某个城市出发沿着棱线寻找一条经过每个城 市一次而且仅一次,最后回到原处的周游世界线路(并不要求 经过每条边).－环球旅行问题.
定义9 无向图G=(V, E), 连接 vi0与vik 的一条链是同一 个点时, 称为圈(circle). 若圈中没有重复的点与重复边者称为初等圈

《图与网络》课件


学习图与网络的意义
学习图和网络的基础概念和算法有助于提高编程能 力和数据处理能力，同时也对多种应用领域产生启 发作用。
2 算法
最短路径算法，网络流量算法，欧拉路径算法等。
五、图与网络的区别与联系
图与网络的区别
• 节点的关系 • 数据表示方式
图与网络的联系
• 共同的算法和应用场景 • 都能够通过节点与边的关系来描述对象间的关系
六、结语
图与网络的未来
未来图和网络将在数据挖掘，机器学习，人工智能 等领域发挥越来越大的作用。
图与网络
图与网络是计算机科学中基础的数据结构，它们被广泛应用于算法，人工智 能，机器学习等领域。
一、什么是图
图的定义
图是由节点和边组成的数据结构，节点表示对象，边表示对象间的关系。
图的种类
有无向图、有向图、加权图、无向加权图和有向加权图等几种。
图的表示方法
邻接矩阵和邻接表是常用的表示方法。
二、图的应用
应用场景
社交网络，交通网络，电成树算法，网络流算法等。
三、什么是网络
1
网络的定义
网络是由节点和边（或链路）组成的连通结构。
2
网络的种类
计算机网络、社会网络、交通网络等不同的种类。
3
网络的表示方法
邻接矩阵、邻接表等方式。
四、网络的应用
1 应用场景
物流、城市规划、社会网络、通信网络等。

第十一章图与网络分析


§11.2 图与网络的基本概念
图的矩阵表示 一个图非常直观，但是不容易计算，
特别不容易在计算机上进行计算，一个有 效的解决办法是将图表示成矩阵形式，通 常采用的矩阵是邻接矩阵、边长邻接矩阵、 弧长矩阵和关联矩阵。
§11.2 图与网络的基本概念
邻接矩阵
表示图 G 的顶点之间的邻接关
系，它是一个 n x n 的矩阵，
§11.3 最短路问题
一、求解最短路的Dijkstra算法 (迪科斯彻，双标号法）
e4
e7 v4
e8
v2
v3
e2
e6
链： v3,e2,v2,e4,v4
v5
§11.2 图与网络的基本概念
v1 e1
e5 e3
e4
e7 v4
e8
v2
v3
e2
e6
链： v3,e2,v2,e4,v4,e3,v1
v5
§11.2 图与网络的基本概念
v1 e1
e5 e3
e4
e7 v4
e8
v2
v3
e2
e6
链： v3,e2,v2,e4,v4,e7,v5
如果两个顶点之间有边相联时，
记为1，否则为0。
v2
v1
v3
v4
§11.2 图与网络的基本概念
v1 v2 v3 v4
v1 0 1 1 1
v2 1 1 1 0
v3 1 1 0 1
v2
v4 1 0 1 0
v1
v3
v4
§11.2 图与网络的基本概念
v1 v2 v3 v4 v5
v1 0 0 0 1 1
v2 1 0 0 1 0
e1 = （v1， v2） e2= （v1， v2） e7= （v3， v5） e8= （v4， v4） 称为自回路(环)；

《图与网络分析》课件


网络的定义与分类
总结词
网络的定义与分类是理解图与网络分析的关键。
详细描述
网络是由节点和边构成的集合，用于描述系统中各个组成部分之间的关系。根据 不同的分类标准，网络可以分为多种类型，如无向网络和有向网络、单层网络和 多层网络等。
图与网络的应用领域
总结词
图与网络的应用领域广泛，包括计算机科学、交通运输、生物信息学等。
从任意一个顶点开始，每次选择一条与已选顶点集合相连的边中权 重最小的边，将其加入最小生成树中。
最短路径算法
Dijkstra算法
01
用于求解图中从一个顶点到其他所有顶点的最短路径。
Bellman-Ford算法
02
用于求解图中所有顶点之间的最短路径。
Floyd-Warshall算法
03
用于求解图中所有顶点之间的最短路径，时间复杂度较低。
网络流算法
01
Ford-Fulkerson算法
用于求解最大网络流问题，通过不断寻找增广路径来增加网络的流量。
02
Dinic算法
基于层次搜索和增广路径的算法，用于求解最大网络流问题。
03
Edmonds-Karp算法
基于广度优先搜索的算法，用于求解最大网络流问题。
03
网络分析与应用
网络中心性分析
节点中心性
社区结构特征
包括社区大小、社区密度、社区连通性等。
社区结构分析的应用
在社交网络中识别用户群体，在组织结构中划分部门和团队等。
网络动态分析
网络动态模型
常见的网络动态模型有随机游走、马尔科夫链和自组 织映射等。
网络动态特征
包括节点的活跃度、网络的演化规律和网络的鲁棒性 等。
网络动态分析的应用

04图和网络分析共195页

J），划去第J列； （4）把第J行标上T标号，重复（3），直到所
有列都被划去。
最小树问题—矩阵法
V2
1 V1
4
2 V4
2
V3
3
3
2
V6
5
2
V5
概述
在研究某些现实系统时，如果系统中含有有限个待 研究的对象，除了关心这些对象本身的特性，同时还 要考虑对象之间的相互关系，一个比较简单并且是常 用的方法就是画一张图（生物链），用点表示系统中 的对象，用点之间的连线表示对象之间的相互关系。 通过对图的研究，达到研究系统的目的。
用图来表达和研究一个系统往往具有直观、简洁和 方便等特点。
v1 v2 v3 v4 v5
v2
3
v1
5
v4
v1 0 3 2 ∞ ∞
4
v2 3 0 ∞ 5 4
2
v3 2 ∞ 0 ∞ 8
2 v3
8
v5
v4 ∞ 5 ∞ 0 2
v5 ∞ 4 8 2 0
基本概念—图的矩阵表示
赋权有向图的矩阵表示：
v2
3
v1 2v3
v1 v2 v3 v4 v5
5
v4
v1 0 3 2 ∞ ∞
基本概念—图
子图： 图中每个连通的部分称为此图的子图。 支撑子图：包含原图中所有点的子图。 支撑树： 为树的支撑子图。（生成树）
基本概念—图
权：与边有关的数量指标
从公路网图中可以得到的信息是各城镇之间有无公路相连。
在公路网中，不仅要知道城镇之间有无公路相连，还要知道公
路的里程（长度），这样的图称为赋权图。边 [vi , v j ] 的权记 为 w ij 。根据实际问题的不同，权的含义也可以不一样。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

费用斜率K
例11-2：某一个工作正常时间为7 天，费用为360元，最短时间为4 天，费用450元，则
K=（450-360）/（7-4）=30元/天
直接费用优化原理
核心：力求以最小的费用去缩 短工期，最后求出一个费用最 低的最快进度。
i
K TN-TM
j 5
例：任务如图
1400 5-3 700 5-3
5 3 0 0 1 5 10
26
令D=T=40
10 2 10
4 5 10 4 20 20
30 5
30
40
40 6
10
10
逆向计算最迟时间LT
5 3 0 0 1 5 10
26
10 2 10
4 5 10 4 20 20
30 5
30
40
40 6
10
10
确定关键线路（ET=LT）
5 3 0 0 1 5 10
11
18
6 5
23 7
8
4
第二步：令最快进度为指令工期D=16天。 求出正常时间，计算工期T=23天。
结点的最迟必须实现时间（LT）
工作的最迟必须开始时间（LS） 工作的最迟必须结束时间（LF）
网络计划的时间参数计算 二、协调性参数 工作的总机动时间（TF）
工作的局部机动时间（FF）
第一类局部机动时间（FF’） 第二类局部机动时间（FF’’）
网络计划的时间参数计算公式 最早时间： ETS=0
ETj=max（ETi+tij）
定义（虚工作）延续时间为零的假定 工作，称为虚工作。用虚箭线表示。 定义（紧前工作）紧接在该工作前面 的工作，称为该工作的紧前工作。 定义（紧后工作）紧接在该工作后面 的工作，称为该工作的紧后工作。
定义（结点）紧前工作与紧后工作 的交接点称为结点（节点、事项）。 结点功能——衔接前后工作和控制 工作进程。 结点特征——瞬时性。结点实现不
工作项目： （甲部队） 到影院A： 放上集B： 放下集C： 返 回D：
30分钟 50分钟 50分钟 30分钟
工作项目： （传片人） 送上集E： 返回甲部队F： 送下集G：
40分钟 40分钟 40分钟
工作项目： （乙部队） 到影院H： 放上集I： 放下集J： 返 回 K：
30分钟 50分钟 50分钟 30分钟
F
40
10
30
目标目标就是为完成预定的任务所 要达到的根据客观实际而确定的主 要任务（或综合）功能数量指标。 大多数情况下，是以完成任务 的时限作为目标。 任务实现的目的只有一个，而其目 标可能有多个（时间,成本,资源等）
相互关系
逻辑关系——两件工作之间相互联系 是客观固有的，不能随意改变的。 （如电影的上下集之间） 组织关系——工作之间关系是人为的 关系。它体现了人的主观能动作用， 它的确定主要考虑到效果,时间，资源 和经济原则等因素。（如甲乙部队之 间）
1
2-2
2
5-2 1000 700 500 1000 4-2 2-1 7-4 400 1000 800 3 4 5-4 4-3 7-4 1600 8-5 900 4-2
6
7
第一步：按工作的最快时间求出最快进度。 假定所有工作按最短时间完成。
5 2 4 1 2 2 4 3 3 1 4 4 2 6 3 7 3
10
逆向计算最迟时间LT
5 3 0 1 5 10 2 10 4 20 20 10 4 5
令D=T=40
30 5 10
30
40
40 6
10
10
逆向计算最迟时间LT
5 3 0 1 5 10
26
令D=T=40
10 2 10
4 5 10 4 20 20
30 5
30
40
40 6
10
10
逆向计算最迟时间LT
30 5
30
40
40 6
10
10
确定关键线路（ET=LT）
5 3 0 0 1 5 10
26 21 10 2 10 4 5
TF35=30 - 5 - 4 = 21
30 5 10 4 20 20
30
40
40 6
10
10
计算总机动时间TF=LTj-Eti-tij
5 3 0 0 1 5 10
26 21 10 2 10 4 15 5
FF’’ij=LTj -LTi - tij TF FF
凡是TF=0的工作便是关键工作， 组成的线路便是关键线路。
关键线路上的关键结点必有ET=LT， 但不充分。
唯一的判断是TF=0。
图算法——一种简单有效的方法 步骤： 1 计算结点最早实现时间（顺向计算） 2 计算结点最迟实现时间（逆向计算） 3 确定关键线路（ET=LT）
令D=T=40
30 5 10
40
40 6
10
10
逆向计算最迟时间LT
5 3 0 1 5 10 2 10 4 20 4 5
令D=T=40
30 5 10
30
40
40 6
10
10
逆向计算最迟时间LT
5 3 0 1 5 10 2 10 4 20 20 4 5
令D=T=40
30 5 10
30
40
40 6
10
ESij=ETi EFij=ETi+tij
网络计划的时间参数计算公式 最迟时间： LTT=D（指令工期，通常D=T）
LTi=min（LTj+tij）
LFij=LTi LSij=LTj - tij
网络计划的时间参数计算公式 协调性参数： TFij=LTj -ETi - tij
FF’ij=ETj -ETi - tij
2 A 1 30
B 50 H 30
3 40
E 4 5
C 50
6
D 30 7 G 40 8 J 50 K 9
F
40 I 50
10
30
2 A 1 30
B 50 H 30
3 40
E 4 5
C 50
6
D 30 7 G 40 8 J 50 K 9
F
40 I 50
10
30
2 A 1 30
B 50 H 30
网络计划的费用优化 一般任务的直接费用是随着工 期的缩短而增加
一般任务的间接费用是随着工 期的缩短而减少。 总存在一个总费用最少的最优 工期。
费 用
总费用曲线
CP
直接费用曲线
间接费用曲线
TP
时间
费用斜率K
在线性假定下，工作延续时 间每缩短一个单位时间所增加的 费用称为费用斜率K
K=（CM-CN）/（TN-TM）
4 计算工作的总机动时间（非关键线路）
3 0 1 5 4 2 10 4 5 10 5
10
10
6
顺向计算最早时间ET
5 3 0 1 5 10 2 10 4 4 5 10 5
10
10
6
顺向计算最早时间ET
5 3 0 1 5 10 2 10 4 20 4 5 10 5
10
10
6
顺向计算最早时间ET
5 3 0 1 5 10 2 10 4 20 4 5 10 30 5
10
10
6
顺向计算最早时间ET
5 3 0 1 5 10 2 10 4 20 4 5
计算工期T=40
30 5 10
40
10
10
6
顺向计算最早时间ET
5 3 0 1 5 10 2 10 4 20 4 5
令D=T=40
30 5 10
40
10
10
6
逆向计算最迟时间LT
5 3 0 1 5 10 2 10 4 20 4 5
占用时间。
结点分类——一般性结点和强制性 结点。 强制性结点——对整个任务具有生 命价值，且它的实现因受外界因素 的影响而有一个限制时间结点。
（如修水库的堤坝合拢；渡江河时 间；大桥合拢时间等）
定义（线路）从最初结点到最终结 点连贯的工作序列称为线路。 定义（线路的长度）线路上各工作 的延续时间之和，称为线路的长度。 定义（关键线路）网络中所有线路 中最长的线路称为关键线路。 关键线路有着特别重要的地位，正 是它控制着整个计划的工期。
2Hale Waihona Puke 5最快进度（直接费用最多）T=16天
第二步：令最快进度为指令工期D=16天。 求出正常时间，计算工期T=23天。
5 5 0 1 2 2 5 7 3 4 2 4 7 4 6 5 7 5
8
4
第二步：令最快进度为指令工期D=16天。 求出正常时间，计算工期T=23天。
16 5 5 0 1 2 2 2 5 7 7 3 2 4 5 4 4 7
网络计划的编制（建模）步骤：
1 将任务细化
2
3 4
确定工作项目及其关系
估计工作的延续时间 绘制网络图
5
简化或合并网络图
网络计划的时间参数计算 一、控制性参数 最早时间：
结点的最早可能实现时间（ET）
工作的最早可能开始时间（ES） 工作的最早可能结束时间（EF）
网络计划的时间参数计算 一、控制性参数 最迟时间：
F
40 I 50
10
30
2 A 1 30
B 50 H 30
3 40
E 4 5
C 50
6
D 30 7 G 40 8 J 50 K 9
F
40 I 50
10
30
关键线路：1-2-3-4-7-8-9-10
关键线路长度=280
2 A 1 30 H 30 B 50 3 40 E 4 5 C 50 6 D 30 7 I 50 40 8 G J 50 K 9