第六章图与网络分析 本章主要内容： 图的基本概念与模型 兼树图与图的最小部分树 ◆最短路问题 幸网络的最大流 ◆最小费用流（略）》 2014-12-15 1
2014-12-15 1 第六章 图与网络分析 图的基本概念与模型 树图与图的最小部分树 最短路问题 网络的最大流 最小费用流（略） 本章主要内容：
教学目标与要求 ■【教学目标】 ■通过对本章的学习，理解图的基本概念；掌握最小支撑树、最短路、 最大流、中国邮路问题的求法；会利用相关模型解决合理组织人力、 物力、财力的优化问题。 【知识结构】 图的基本概念 排课等匹配问题 最小支撑树 各种网络优化 图与网络模型 最大流问题 规划论 最小费用流 多服务设施布点 最短路问题 单服务设施布点 中国邮路问题 回到始点最佳路线 2014年12月15日星期一
2014年12月15日星期一 教学目标与要求 【教学目标】 通过对本章的学习，理解图的基本概念；掌握最小支撑树、最短路、 最大流、中国邮路问题的求法；会利用相关模型解决合理组织人力、 物力、财力的优化问题。 【知识结构】 图 与 网 络 模 型 图的基本概念 最大流问题 最小支撑树 最小费用流 排课等匹配问题 各种网络优化 回到始点最佳路线 最短路问题 中国邮路问题 多服务设施布点 单服务设施布点 规划论
引言 1736年瑞士科学家欧拉(1707-1783)发表了关于图论方 面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。 德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿， 河的两岸和岛屿之间有七座桥相互连接，如图a所示。 B 图a 2014-12-15
2014-12-15 3 引言 1736年瑞士科学家欧拉(1707-1783)发表了关于图论方 面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。 德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿， 河的两岸和岛屿之间有七座桥相互连接，如图a所示。 B A C D 图ａ
引言 当地的居民热衷于这样一个问题，一个漫步者如何能够走过这 七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验 者很多，但是都没有成功。 为了寻找答案，1736年欧拉将这个问题抽象成图所示图形的 一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最 终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图 形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就 是古典图论中的第一个著名问题。 A 2014-12 B 图b 4
2014-12-15 4 引言 当地的居民热衷于这样一个问题，一个漫步者如何能够走过这 七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验 者很多，但是都没有成功。 为了寻找答案，1736年欧拉将这个问题抽象成图b所示图形的 一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最 终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图 形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就 是古典图论中的第一个著名问题。 B A C D Ｄ Ａ Ｃ Ｂ 图ｂ
§1图的基本概念与模型 图的定义： 若用点表示研究的对象，用边表示这些对象之间的联系， 则图G可以定义为点和边的集合，记作： G=V,E 其中：V一点集E一边集 ※图G区别于几何学中的图。这里只关心图中有多少个点以 及哪些点之间有连线。 通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。 如果一个图是由点和边所构成的，那么称为无向图，如果一个图是由 点和弧所构成的，那么称为它为有向图，记作D(V,A,其中俵示 有向图D的点集合，A表示有向图D的弧集合。一条方向从%指向y 的边和弧，分别记作[y,(。 2014-12-15
2014-12-15 5 §1 图的基本概念与模型 图的定义： 若用点表示研究的对象，用边表示这些对象之间的联系， 则图G可以定义为点和边的集合，记作： G {V , E} 其中: V——点集 E——边集 ※ 图G区别于几何学中的图。这里只关心图中有多少个点以 及哪些点之间有连线。 通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。 如果一个图是由点和边所构成的，那么称为无向图，如果一个图是由 点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示 有向图D的点集合，A表示有向图D的弧集合。一条方向从vi , 指向vj 的边和弧，分别记作[vi ,vj ]，(vi ,vj )
§1图的基本概念与模型 ,网络（赋权图） 设图G={V,E},对G的每一条边yH相应赋予数量指标w, w称为边[的权，赋予权的图G称为网络（或赋权图）。 权可以代表距离、费用、通过能力（容量）等等。 端点无序的赋权图称为无向网络，端点有序的赋权图称为有 向网络。 15 4 14 20 ⑧ 2014-12-15 25 6
2014-12-15 6 §1 图的基本概念与模型 网络（赋权图） 设图G＝{V，E}，对G的每一条边[vi ,vj ]相应赋予数量指标wij， wij称为边[vi ,vj ]的权,赋予权的图G称为网络(或赋权图）。 权可以代表距离、费用、通过能力(容量)等等。 端点无序的赋权图称为无向网络，端点有序的赋权图称为有 向网络。 ① ② ③ ④ ⑤ ⑥ 9 10 20 15 7 14 19 25 6
§1图的基本概念与模型 定义：图中的点用v表示，边用e表示。对 每条边可用它所连接的点表示，记作： e1=[v1,V1];e2=[v1,v2]。 ·端点，关联边，相邻 % 若有边e可表示为e=y,以，称v和y 06 8 e7 是边e的端点，反之称边e为点y,或y 的关联边。若点"，与同一条边关 联，称点v和v,相邻；若边e和e具 有公共的端点，称边e,和e相邻。 2014-12-15
2014-12-15 7 §1 图的基本概念与模型 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 定义: 图中的点用v表示，边用e表示。对 每条边可用它所连接的点表示，记作： e1=[v1,v1]； e2=[v1,v2]。 端点,关联边,相邻 若有边e可表示为e=[vi ,vj ]，称vi和vj 是边e的端点，反之称边e为点vi或vj 的关联边。若点vi、vj与同一条边关 联，称点vi和vj相邻；若边ei和ej具 有公共的端点，称边ei和ej相邻
§1图的基本概念与模型 。环，多重边，简单图 如果边e的两个端点相重，称该边为 e 环。如右图中边e,为环。 如果两个点之间多于一条，称为多重 es e6 边，如右图中的e4和es。 er 对无环、无多重边的图称作简单图。 一个无环，有多重边的图称为多重图。 2014-12-15 8
2014-12-15 8 §1 图的基本概念与模型 环, 多重边, 简单图 如果边e的两个端点相重，称该边为 环。如右图中边e1为环。 如果两个点之间多于一条，称为多重 边，如右图中的e4和e5。 对无环、无多重边的图称作简单图。 一个无环，有多重边的图称为多重图。 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5
§1图的基本概念与模型 。次，奇点，偶点，孤立点 与某一个点v,相关联的边的数目称为 e 点的次（也叫做度），记作()。 右图中d(v)=4,d(V3)=5,d(vs)=1。次 es 为奇数的点称作奇点，次为偶数的 e 点称作偶点，次为1的点称为悬挂点， 次为0的点称作孤立点。 图的次：一个图的次等于各点的次之和。 2014-12-15 9
2014-12-15 9 §1 图的基本概念与模型 次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为 点vi的次（也叫做度），记作d(vi )。 右图中d(v1 )＝４,d(v3 )=5,d(v5 )=1。次 为奇数的点称作奇点，次为偶数的 点称作偶点，次为1的点称为悬挂点， 次为0的点称作孤立点。 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 图的次: 一个图的次等于各点的次之和
§1图的基本概念与模型 出次与入次 有向图中，以：为始点的边数称为点y的出次，用d()表 示；以为终点的边数称为点y:的入次，用表示d(W);:点 的出次和入次之和就是该点的次。 ※有向图中，所有顶点的入次之和等于所有顶点的出次之 和。 2014-12-15 10
2014-12-15 10 §1 图的基本概念与模型 出次与入次 有向图中，以vi为始点的边数称为点vi的出次，用d + (vi )表 示；以vi为终点的边数称为点vi 的入次，用表示d - (vi ) ；vi 点 的出次和入次之和就是该点的次。 ※ 有向图中，所有顶点的入次之和等于所有顶点的出次之 和