数学建模培训班的图论课件(编辑修改稿)

数学建模培训班的图论课件(编辑修改稿)内容摘要：

定边 ，则从 ieee ,..., 21 },...,{\ 21 ieeeE中选取 ，使得 : 1iei) 为无圈图， }],...,[{ 121 ieeeG ii) 是满足 i)的尽可能小的权， )( 1iew 3) 当第 2)步不能继续执行时，则停止 . 定理 4 由 Kruskal算法构作的任何生成树 }], . . . ,[{ 121*  eeeGT 都是最小树 . 最小生成树与算法 河南城建学院 例 用 Kruskal算法求下图的最小树 . 在左图中 权值 },...,{ 821 eee最小的边有 任取一条 , 51 ee ,1e 在 中选取权值 },...,{ 832 eee,5e最小的边 中权值最小边有 , 从中选 ：73,ee。 3e任取一条边 会与已选边构成圈 ,故停止 ,得 中选取在中选取 ,7e 中选取 . 但 与 都 }, 86 ee 84,ee 4e 8e},,{ 876432 eeeeee},{ 87642 eeeee,{ 42 ee在河南城建学院 B 破圈法 任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。 在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 河南城建学院 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 河南城建学院 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 v3 v1 v2 v4 v5 v6 1 5 河南城建学院 最小生成树实例 :有线电视网最优布线问题 单位： 100米 : 卫星加密电视的开播 ,受到大 家欢迎 ,要想收看加密电视必 须建一套有线电视网．我们 考虑这样一个具体问题：设 某市六个个区之的相互距离 如下表所示，试确定表数据 形成的网络中，如何布线能 布线最省。 1 2 3 4 5 6 1 0 13 51 77 68 50 2 13 0 60 70 67 59 3 51 60 0 57 3 62 4 77 70 57 0 20 55 5 68 67 36 20 0 34 6 50 59 2 55 34 0 河南城建学院 最小生成树实例 :有线电视网最优布线问题 ２ .问题求解 : 最优布线问题，就是要求任何两地都有链相连，而使总线路最短，这个问题在图论中也称为最小树题．作下图，其中顶点 v1 ， v２ ， v３ ， v４ ， v５ ， v６ 分别表示两区之间的距离． V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建学院 最小生成树实例 :有线电视网最优布线问题 对于上图，我们要找使布线最省的网络模型．图论中的破圈法可以解 决这个问题，具体过程如下：在圈 v1v２ v３ v1中，去掉最长边 v２ v３ ＝ 60，同 样去掉圈 v1v３ v６ v1， v２ v４ v５ v２ ， v３ v４ v５ v３ ， v3 v5v６ v3， v4v5 v6 v4， v1v3v4v1， v1v6v2v1， v2v5v6v2中最长的边 v1v３ ＝ 51， v2v4＝ 70， v3v4＝ 57， v3v5＝ 36,v4v6＝ 55， v1v4＝ 77， v1v5＝ 68， v2v6＝ 59， v2v5＝ 67，最后构 成的图（如下）就是最省的 布线图 ． 13 2 50 34 20 v2 v3 v1 v6 v4 v6 V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建学院 167。 8 最短路径问题及其应用 最短路问题就是从给定的网络图中找出任意两点间 距离最短的一条路，其中距离只是权数的代称（在实际 网络中，权数可指时间、费用等）。 如选址、管道铺设 时的选线、设备更新、投资等都可以归给为求最短路的 问题。 最短路问题有一个重要而明显的性质（ 算法思 想 ）：最短路是一条路径，且最短路的任一段也是最短 路。 求最短路的方法： (1) 求从一点到其余各点间的 Dijkstra算法。 (2) 求任意两点间最短距离的 矩阵算法 (Floyd算法 )。 设 G为赋权有向图或无向图， G边上的权均非负。 河南城建学院 Dijkstra(标号法）的算法： 迪克斯特拉 不妨用 表示图中两相邻点 i和 j的距离；若点 I 和 j不相邻，则可令 ，显然 ；用 表示从 点 s到 i点的最短距离。 现要求从点到某一点 t的最 短路。 Dijkstra算法步骤如下 ： （１） 从点 s出发，因 ，将此值标在 s旁，表示此点已标号； （２）从 s点出发，找出与 s点相邻的点中距离最小的一个，设为 r， 将 的值标在 r旁，表示此点已标； （３）从已标号的点出发，找出与这些点相邻的所有未标号点 p。 若有 ，则对 p点标号； （４）重复第三步，一直到 t点得到标号为止。 矩阵算法步骤（略） ijdijd  0iid  siL0ssL sr ss srL L dm in{。 }sp ss sp sr rpL L d L d  河南城建学院 例 求图中顶点 v0与 v5的最短路径 . 解 :可以将计算过程用一张表表示出来 (见下页表 ) 算法示例 河南城建学院 由上表可知 ,v5与 v3相邻 ,v3与 v4相邻 ,v4与 v2相邻 ,v2与 v1相邻 ,v1与 v0相邻 .这 样从 v5往前追踪 ,得 v0到 v5的最短路径为： Γ=v0v1v2v4v3v5. W(Γ)=9. 河南城建学院 Dijkstra算法的标号法举例 2 10 7 3 6 4 5 2 10 7 3 6 4 5 2 2 10 7 3 6 4 5 2 10 7 3 6 4 5 10  2   9 5 2 2 5 5 9 9 9 9 0 0 0 0 河南城建学院 最短路径问题实例：医院选址问题 ： 新建居民小区的医院 ， 对该区每一户居民都很重要。 如下图是一个新 建居民区的示意图 ， 医院建在哪里为好呢。 V2 V1 V3 V5 V10 V7 V6 V4 V9 V8 9 3 2 1 8 2 7 9 5 6 4 8 1 3 1 6 5 河南城建学院 最短路径问题实例： 医院选址问题 在上图中 ， v1， v２ ， … ， v10表示各居民点 ， 边表示两居民点之间的道路 ， 边上的数值表示两居民 点之间的距离 （ 也就是该边的权 ） . 现在需要我们考虑的问题是在这 10个居民点中 ， 何 处作为新建医院的理想地址 ， 以使所建医院到最远的 居民点距离尽可能近 （ 即最远点的病人到医院看病时 走的路尽可能短 ）。 河南城建学院 2. 问题求解： 显然可以看出 ,上图是一个连通无向图，记为Ｇ＝｛Ｖ，Ｅ｝ . 任取 vi ∈ V(i=1,2, ……,10) ，考察 vi与Ｖ中其他顶点间的最短路（也称为距离）：Ｐ ＊ （ vi， v１ ），Ｐ ＊ （ vi，v2）， …… ，Ｐ ＊ （ vi， v１０ ），把这 10个距离中最大的数称为顶 vi的最大服务距离，记为 L(vi). 求出上图中各点间的距离，如下表所示，这样就可以把每个顶点 vi对应的最大服务距离 L(vi)求出来 . 最短路径问题实例： 医院选址问题 河南城建学院 最短路径问题实例 ： 医院选址问题 1 2 3 4 5 6 7 8 9 10 1 0 5 3 6 5 10 10 9 12 13 2 5 0 2 3 4 9 6 8 8 9 3 3 2 0 3 2 7 7 6 9 10 4 6 3 3 0 5 7 5 6 7 8 5 5 4 2 5 0 5 5 4 7 8 6 10 9 7 7 5 0 2 1 4 5 7 10 6 7 5 5 2 0 1 2 3 8 9 8 6 6 4 1 1 0 3 4 9 12 8 9 7 7 4 2 3 0 5 10 13 9 10 8 8 5 3 4 5 0 河南城建学院 最短路径问题实例 ： 医院选址问题 注：上表中的１，２，３，４，５，６，７，８，９，１０分别代表 v1， v２ ， v３ ， v４ ， v５ ， v６ ， v７ ， v８ ， v９ ， v１０ v1到各顶点的距离就是上表中的第一行各数，它们中最大的是 13，所以 L(v1)=13，其它各点的最大服务距离分别为 : L(v2)=9， L(v3)=10， L(v4)=8，。