六、图与网络分析 今图论 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
第1节图的基本概念 令例3某单位储存八种化学药品,其中某些药品是不能存 放在同一个库房里的。用点n,n2,n2,,n,V,,别代表这 八种药品,若药品v和药品v是不能存放在同一个库房的, 则在v和之间联一条线 从这个图中可以看到,至少要有四个库房,因为v1,v2,v3,3 必须存放在不同的库房里 事实上,四个库房就足够了。例如{v},{2,V,v(y,n3},{,n 各 存放在一个库房里(这一类寻求库房的最少个数问题,属于图论中 的所谓染色问题,一般情况下是尚未解决的)。 药品存放图 清华大学出版社
第1节 图的基本概念 v 例3 某单位储存八种化学药品，其中某些药品是不能存 放在同一个库房里的。用点 分别代表这 八种药品，若药品vi和药品vj是不能存放在同一个库房的， 则在vi和vj之间联一条线。 ¢ 从这个图中可以看到，至少要有四个库房，因为 必须存放在不同的库房里。 ¢ 事实上，四个库房就足够了。例如 各 存放在一个库房里(这一类寻求库房的最少个数问题，属于图论中 的所谓染色问题，一般情况下是尚未解决的)。 6 7 8 , 1 2 3 4 5 v ,v ,v ,v ,v v ,v ,v 1 2 5 8 v ,v ,v ,v 7 6 8 { },{ },{ },{ } 1 2 4 3 5 v v ,v ,v v ,v v ,v 药品存放图 清华大学出版社 7
第1节图的基本概念 图:由点及点与点的连线构成,反映了实际生活中某些对 象之间的某些特定关系 o点:代表研究的对象; o连线:表示两个对象之间特定的关系。 图:是反映对象之间关系的一种抽象 o一般情况下,图中点的相对位置如何,点与点之间连线的长短曲 直,对反映对象之间的关系并不重要。 口如例2,也可以用图10-5所示的图去反映五个球队的比赛情况,与图 10-3没有本质区别。 比赛情况图 清华大学出版105
第1节 图的基本概念 v 图：由点及点与点的连线构成，反映了实际生活中某些对 象之间的某些特定关系 ¢ 点：代表研究的对象； ¢ 连线：表示两个对象之间特定的关系。 v 图：是反映对象之间关系的一种抽象 ¢ 一般情况下，图中点的相对位置如何，点与点之间连线的长短曲 直，对反映对象之间的关系并不重要。 o 如例2，也可以用图10-5所示的图去反映五个球队的比赛情况，与图 10-3没有本质区别。 比赛情况图 清华大学出版社图10-5 8
第1节图的基本概念 冷关系的对称性和非对称性: o几个例子中涉及到的对象之间的“关系”具有“对称性”,就是说, 如果甲与乙有这种关系,那么同时乙与甲也有这种关系。 o实际生活中,有许多关系不具有这种对称性。 口如例2,如果人们关心的是五个球队比赛的胜负情况,那么从图10-3中就 看不出来了。为了反映这一类关系,可以用一条带箭头的连线表示 口例如,如果球队v胜了球队v2,可以从v引一条带箭头的连线到v2 口类似胜负这种非对称性的关系,在生产和生活中是常见的,如交通运输 中的“单行线”,部门之间的领导与被领导的关系,一项工程中各工序 之间的先后关系等。 比赛胜负图 清华大学出版社
第1节 图的基本概念 v 关系的对称性和非对称性： ¢ 几个例子中涉及到的对象之间的“关系”具有“对称性” ，就是说， 如果甲与乙有这种关系，那么同时乙与甲也有这种关系。 ¢ 实际生活中，有许多关系不具有这种对称性。 o 如例2，如果人们关心的是五个球队比赛的胜负情况，那么从图10-3中就 看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。 o 例如，如果球队v1胜了球队v2，可以从v1引一条带箭头的连线到v2 o 类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运输 中的“单行线” ，部门之间的领导与被领导的关系，一项工程中各工序 之间的先后关系等。 比赛胜负图 清华大学出版社 9
第1节图的基本概念 今图的概念 o图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形 o两点之间不带箭头的连线称为边,带箭头的连线称为弧。 o如果一个图G由点及边所构成,则称之为无向图(也简称为图),记 为G=1E),式中V,E分别是G的点集合和边集合。一条连结点v,"∈V 的边记为[",](或[V,V) o如果一个图D由点及弧所构成,则称为有向图,记为D=(V,A),式中V, A分别表示D的点集合和弧集合。一条方向是从v指向v的弧,记为 清华大学出版社
第1节 图的基本概念 v 图的概念 ¢ 图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形。 ¢ 两点之间不带箭头的连线称为边，带箭头的连线称为弧。 ¢ 如果一个图G由点及边所构成，则称之为无向图(也简称为图)，记 为 ，式中V，E分别是G的点集合和边集合。一条连结点 的边记为［ ］(或［ ］)。 ¢ 如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V， A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为 ( )。 G =(V,E) i j v ,v j i v ,v i j v ,v i j v ,v V 清华大学出版社 10
第1节图的基本概念 无向图的例子 V={v1,"2ny,} E=er, e,, e3, e4, es,e6, e7 其中 e=v,"2],e2=v,v2」,e3=v2,V3],e;=[v3,小, e=[v,]e。=[v,n]e=[v,] 无向图 e3 图10-7 清华大学出版社
第1节 图的基本概念 v 无向图的例子 其中 V=v1 ,v2 ,v3 ,v4 E e1 ,e2 ,e3 ,e4 ,e5 ,e6 ,e7 1 1 2 2 1 2 3 2 3 4 3 4 5 1 4 6 1 3 7 4 4 e = v ,v , e = v ,v , e = v ,v , e = v ,v , e = v ,v , , e = v ,v , e v ,v 无向图 图10-7 清华大学出版社 11