六、图与网络分析 今图论 o运筹学的重要分支 主要应用领域 口物理学、化学、控制论、信息论、科学管理、电子计算机等 o图论理论和方法应用实例 口在组织生产中,为完成某项生产任务,各工序之间怎样衔接,才能使生 产任务完成得既快又好。 口一个邮递员送信,要走完他负责投递的全部街道,完成任务后回到邮局, 应该按照怎样的路线走,所走的路程最短。 口各种通信网络的合理架设,交通网络的合理分布等问题,应用图论的方 法求解都很简便。 清华大学出版社
六、图与网络分析 v 图论 ¢ 运筹学的重要分支 ¢ 主要应用领域 o 物理学、化学、控制论、信息论、科学管理、电子计算机等 ¢ 图论理论和方法应用实例 o 在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生 产任务完成得既快又好。 o 一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局， 应该按照怎样的路线走，所走的路程最短。 o 各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方 法求解都很简便。 清华大学出版社 2
六、图与网络分析 图论的起源与发展 o欧拉在1736年发表了图论方面的第一篇论文,解决了著名的哥尼 斯堡七桥问题 七桥问题: 口哥尼斯堡城中有二条河叫普雷格尔河,该河中有两个岛,河上有七座 桥。当时那里的居民热衷于这样的问题:一个散步者能否走过七座桥, 且每座桥只走过一次,最后回到出发点。图10-1(a) o欧拉将此间题归结为如图10-1()所示图形的一笔画问题。即能否 从某一点开始,不重复地一笔画出这个图形,最后回到出发点。 欧拉证明了这是不可能的,因为图10-1(b)中的每个点都只与奇数 条线相关联,不可能将这个图不重复地一笔画成。 图10-1 清华大学出版社
六、图与网络分析 v 图论的起源与发展 ¢ 欧拉在1736年发表了图论方面的第一篇论文，解决了著名的哥尼 斯堡七桥问题。 ¢ 七桥问题： o 哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座 桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥， 且每座桥只走过一次，最后回到出发点。图10-1(a) ¢ 欧拉将此问题归结为如图10-1(b)所示图形的一笔画问题。即能否 从某一点开始，不重复地一笔画出这个图形，最后回到出发点。 欧拉证明了这是不可能的，因为图10-1(b)中的每个点都只与奇数 条线相关联，不可能将这个图不重复地一笔画成。 图10-1 清华大学出版社 3
第11章图与网络优化 第1节图的基本概念 ■第2节树 ■第3节最短路问题 第4节网络最大流问题 第5节最小费用最大流问题 ■第6节中国邮递员问题 清华大学出版社
清华大学出版社 第11章 图与网络优化 n第1节 图的基本概念 n第2节 树 n第3节 最短路问题 n第4节 网络最大流问题 n第5节 最小费用最大流问题 n第6节 中国邮递员问题 4
第1节图的基本概念 人们为反映一些对象之间关系铁路交通图 时,常会用示意图。 北京 天津 o例1下图是我国北京、上海等十 个城市间的铁路交通图,反映了 这十个城市间的铁路分布情况。 济南·青岛 这里用点代表城市,用点和点之 间的连线代表这两个城市之间的 铁路线。 郑州 徐州·连云港 o其他示意图的例子 口电话线分布图、煤气管道图、航 上海 空线图等。 南京 武汉 清华大学出版社
第1节 图的基本概念 v 人们为反映一些对象之间关系 时，常会用示意图。 ¢ 例1 下图是我国北京、上海等十 个城市间的铁路交通图，反映了 这十个城市间的铁路分布情况。 这里用点代表城市，用点和点之 间的连线代表这两个城市之间的 铁路线。 ¢ 其他示意图的例子 o 电话线分布图、煤气管道图、航 空线图等。 铁路交通图 清华大学出版社 5
第1节图的基本概念 例2有甲、乙、丙、丁、戊五个球队,它们之间比赛的 情况用图表示出来。 o已知甲队和其他各队都比赛过一次,乙队和甲、丙队比赛过,丙 队和甲、乙、丁队比赛过,丁队和甲、丙、戊队比赛过,戊队和 甲、丁队比赛过。为了反映这个情况,可以用点分别代表这五个 队, ,某两个队之间比赛过,就在这两个队所相应的点之间联一条 线,这条线不过其他的点,如图103所示 比赛情况图 图10-3 清华大学出版社
第1节 图的基本概念 v 例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的 情况用图表示出来。 ¢ 已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙 队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和 甲、丁队比赛过。为了反映这个情况，可以用点 分别代表这五个 队，某两个队之间比赛过，就在这两个队所相应的点之间联一条 线，这条线不过其他的点，如图10-3所示。 比赛情况图 图10-3 清华大学出版社 6