- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
v1 图7.5(a) v1 a3 v3 图7.5(b)
2015年4月11日星期六 管理运筹学课件
a1 a2
v2
7.1.2 图的基本概念
承【例7-2】这是一个染色问题,其方法:
找出次数最大的点,将其与不 相邻的点组成新的点集;再从其余的子图中找出次数最大的点,将其与不 相邻的点组成新的点集,直到子图的点集为空.
2015年4月11日星期六 管理运筹学课件
7.3.3 求网络各点之间最短路的矩阵计算法*
【例7.9】 求各点间最短路矩阵 (2)计算经过1个中间点的可达矩阵
A 2 S 3 3 B 2 C 4 F 4 D 6 4 E 3 3 2 2 2 T
(1) (0) (0) (0) (0) (0) (0) (0) (0) d SB min{d SS d SB , d SA d AB , d SB d BB , d SC dCB , (0) (0) (0) (0) (0) (0) (0) (0) d SD d DB , d SE d EB , d SF d FB , d ST dTB }
【例7.6】 2
2 S 0
A 3
4 6
D
6 结论：最短路径SADT，或 SCFT；最短路长：9
3
5 B 2
4
4
3
C
3 2 8 2 E 3 2 F 7
T 9
2015年4月11日星期六
管理运筹学课件
7.3.1 求两点间最短路的Dijkstra标号算法
【例7.7】 用Dijkstra方法求点S到点T的最短路及路长。 最短路线:SACT 0 6 13 6 7 或:SAT S A T 最短路长:13 3 2 5 6 5 WinQSB演示 B C Excel演示 5 8 Lingo演示 (1)给S标号0 (2)V={S},补集CV={A,B,C,T},min{LSS+DSB,LSS+DSA}={0+5,0+6}=5 给B标号5,[S,B]加粗 (2)V={S,B},CV={A,C,T},min{LSS+DSA,LSB+DBC}={0+6,5+8}=6 给A标号6,[S,A]加粗 (3)V={S,B,A},CV={C,T},min{LSA+DAC,LSA+DAT,LSB+DBC}={6+2,6+7,5+6}=8 给C标号8,[A,C]加粗 (3)V={S,B,A,C},CV={T},min{LSA+DAT,LSC+DCT}={6+7,8+5}=13 给T标号13,[A,C]或[A,T]加粗
2015年4月11日星期六
管理运筹学课件
本章主要内容
7.1 图的基本概念 7.2 树图及图的最小支撑树 7.2.1 树图的基本性质 7.2.2 最小支撑树的求法:避圈 法和破圈法 案例7-1 印第安那州公路规划 问题 7.3 最短路问题 7.3.1 两点间最短路的 Dijkstra标号算法 7.3.3 各点间最短路的矩阵算 法* 案例7-2 设备更新问题
v1
v2
v8
{
v7 v3
,
}
{
,
} {
,
,
} {
}
v6 v5
2015年4月11日星期六
v4
至少需要3个库房
管理运筹学课件
7.2.1 树图的概念和性质
树图，简称树，记作T(V,E)：是一类简单而十分有用的图， 其定义是无圈的联通图。现实生活中树图随处可见，如管 理组织机构图、决策树图、聚类分析的“龙骨图”、磁盘 文件存放路径图、家族族谱图、经济管理中的因果分析图 （鱼刺图）等等，因其与大自然中的树的特征相似而得名。 下面不加证明地给出树的一些重要性质。 性质1 任何树图必存在悬挂点。如图7.8有3个悬挂点。 性质2 具有p个点的树图的边数恰好为p-1条边。如图7.8有4 个点、3条边。 性质3 任何具有p个点条边的联通图是树图。 性质4 树图中任意两点之间恰有一条链。 性质5 树图中任意两点之间添加一条边正好构成一个圈。 如果图T=(V,E’)是图G=(V,E)的支撑图，又是树图，则称T 是G的一个支撑树（或称为部分树）。例如图7.8是图7.6(a) 的一个支撑树。
图的基本概念 最小支撑树 排课等匹配问题 各种网络优化 规划论 多服务设施布点 单服务设施布点 回到始点最佳路线
图 与 网 络 模 型
最大流问题 最小费用流 最短路问题 中国邮路问题
2015年4月11日星期六
管理运筹学课件
导入案例——七桥问题
18世纪德国哥尼斯堡如图（a）七座桥，能否不重复一次走完并回到 出发地？
第7章 图与网络模型
重庆三峡学院 关文忠 /guanwenzhong
教学目标与要求
【教学目标】 通过对本章的学习，理解图的基本概念；掌握最小支撑树、最短路、 最大流、中国邮路问题的求法；会利用相关模型解决合理组织人力、 物力、财力的优化问题。 【知识结构】
2015年4月11日星期六
管理运筹学课件
导入案例
运筹学中把一些研究对象用节点表示，对象之间的关系用 连线边表示。用点、边的集合构成图。图论是研究有节点 和边所组成图形的数学理论和方法。图是网络分析的基础， 根据具体研究的网络对象（如：铁路网、电力网、通信网 等），赋予图中各边某个具体的参数，如时间、流量、费 用、距离等，规定图中各节点代表具体网络中任何一种流 动的起点，中转点或终点，然后利用图论方法来研究各类 网络结构和流量的优化分析。图论广泛地应用于物理学、 化学、信息论、科学管理、电子计算机等各个领域。如在 管理中网络合理架设、网络承载能力分析、服务设施布点、 匹配问题等。
（a）七桥问题示意图
B C D
A
1736年，欧拉在圣彼得堡科 学院作了一次学术报告。在 报告中，他证明了鉴别任一 图形能否一笔画出的准则， 即欧拉定理。
管理月11日星期六
导入案例——四色问题
各省用点表示 这张地图有几种颜色 ,有边界接壤的用连线表示 ?能区分各省的边界吗 ,则: ? “任何一张地图只用四种颜色 就能使有共同边界的国家着 上不同的颜色。” 1852年，英国搞地图着色工 作的格思里，首先提出了四 色问题。 1872年，英国数学家凯利正 式向伦敦数学学会提出这个 问题，于是四色猜想成了世 界数学界关注的问题。 美国数学教授哈肯和阿佩尔 于1976年6月,使用伊利诺斯 大学的电子计算机计算了 1200个小时，作了100亿个判 断，终于完成了四色定理的 证明。 不过不少数学家认为应该有 一种简捷明快的书面证明方 法。
2015年4月11日星期六
管理运筹学课件
7.1.2 图的基本概念
v3 e3 v5
v2 e1 e2
e4 v4
e5
e6
v1 图7.5(a) v1 a3 v3 图7.5(b)
2015年4月11日星期六
a1 a2
v2
图（Graph）由点（Vertex）和点之间的连线所构 成的集合。不带箭头的连线称为边（Edge）；带 前头的连线称为弧（Arc）。点和边的集合称为无 向图（Undirected graph），如图7.5(a)，简称图， 用G={V，E}表示；点和弧的集合称为有向图 （Directed graph），如图7.5(b)，用D={V，A}表 示。有向图去掉箭头所形成的无向图称为该有向 图的基础图（underlying graph）。 端点，关联边，相邻 若边 e=[u,v]∈E，则称 u,v 是e 的端点，称e 是点u或v的关联边。有公共关联 边的点称为点相邻；公共端点的边称为边相邻。 环，多重边，简单图，多重图 两个端点重合的边 称为环；若两个点之间有多于一条的边，称为多 重边；一个无环、无多重边的图称为简单图；一 个无环，但允许有多重边的图称为多重图。
2015年4月11日星期六
管理运筹学课件
7.1.1 图的若干示例
A
【例7.1】 有A、B、 C、D、E5个球队， 已比赛过，就在这 两队相应的点之间 连一条线.
E D
B
【例7.2】 8种化学药品， 不能存放在同一个库房里 的用连线表示。
C
【例7.3】若在五 支球队比赛中， 甲胜乙表示为 “甲→乙”，则 右图表明A三胜 一负，B和E一胜 一负，C和D一胜 两负。
{0 , 2 3, 0,3 2, , 4, , } 3
管理运筹学课件
7.1.2 图的基本概念
v3 e3 v5
v2 e1 e2
e4 v4
e5
e6
v1 图7.5(a) v1 a3 v3 图7.5(b)
2015年4月11日星期六
a1 a2
v2
次，奇点，偶点，孤立点，悬挂点，悬挂边 点的关联边的数目称为的次(也称度或线度)， 记为d(v)(环在计算时算作两次，称为入次和 出次)；次为奇数的点称为奇点；次为偶数的 点称为偶点；次为0的点称为孤立点；次为1 的点称为悬挂点；与悬挂点相边关联的边称 为悬挂边。 【定理7.1】 图中，所有顶点的次之和是边数 的2倍。 【定理7.2】 任一个图中，奇点的个数为偶数。 链，圈，路，回路，连通图 点和边的交错序 列中，若边各不相同称为链；封闭的链称为 圈；在链中如果点也各不相同称为路；起点 与终点重合的路称为回路；任意两点之间至 少能找到一条链的图称为连通图。
因政治原因不能建造连接(1)和(2)的公路以及连接(3)和(5)的公路.如何 建造可使总施工长度最短? W(T*)=414 WinQSB演示 Excel演示 1 5 58 196 164 217
管理运筹学课件
79 4 113 3 201 2
Lingo演示
2015年4月11日星期六
