组合图论图论及其算法课件.ppt
《组合图论图论及其算法课件.ppt》由会员分享,可在线阅读,更多相关《组合图论图论及其算法课件.ppt(32页珍藏版)》请在三一文库上搜索。
1、图论及其算法,张莉 Tongji University ,1 最小支撑树问题,1. 树:无回路的无向连通图.,一.基本概念,2. 叶:树中度数为1的顶点.,3. 森林:连通分支大于1,且每个连通分支均为树的非连通图.,1. 例1:在偏远地区,可以通过公路连接分散的村落,但没有任何电话服务。我们希望铺设电话线路,使得每一对村落都可以通过电话线连接(不必是直接的)。沿着现存的公路铺设电话线最便宜,问沿着哪些公路铺设电话线,可以确保每一对村落被连接,且电话线的总长度达到最小(电话线总长度可能与安装总成本成正比)?,二.最小生成树,解:寻找最小生成树.,例2:假设在一个没有良好高速公路的偏远地区涌现了
2、几个城市,理想的是建筑足够多的高速公路,使得城市之间或者直接通过高速公路往来,或者可以通过去其他城市来实现彼此的互相往来. 现在我们希望成本最小化.,注: (1)成本最小化即:可以实现城市间的互通,同时,每条高速路都不浪费(即去掉后就不能互通了).,(2)不允许高速路在所研究的城市以外的某点处连接.,此问题可抽象为设ABC为等边三角形,连接三顶点的路线(称为网络)。这种网络有许多个,其中最短路线者显然是二边之和(如ABAC).,最短网络问题:,如何用最短的线路将三部电话连起来?,但若增加一个周转站(新点P),连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径O要
3、短。 这样得到的网络不仅比原来节省材料,而且稳定性也更好。,斯坦纳(Steiner)最小树是可以在给定的点之外再增加 若干个点(称为斯坦纳点),然后将所有这些点连起来。,如果不允许增加任何额外的点作为网络的顶点,这种最短网络称为最小生成树。,在前面的例子中Steiner最小树的长为 .,最小生成树的长为2.,1968年贝尔实验室波雷克(Pollak)和研究员吉尔伯特 (Gilbert)提出如下猜想:平面上任意n点集,斯坦纳最 小树长与最小生成树之长的比值的最小值是 .,1967年前,贝尔公司按照连结各分部的最小生成树的长度来收费。1967年一家航空公司戳了贝尔公司一个大洞。当时这家企业申请要求
4、贝尔公司增加一些服务点,而这些服务点恰恰位于构造该公司各分部的斯坦纳最小树需增加的斯坦纳顶点上。这使得贝尔公司不仅要拉新线,增加服务网点,而且还要减少收费。这一意外事件迫使贝尔公司自此以后便采用了斯坦纳最小树原则 。,Steiner猜想起源于在美国贝尔电话公司发生的一个富有戏剧性的事件。,1. 问题描述:如村落间铺设电话线的问题.,三. Kruskal算法,2. 算法思想(贪婪算法):总是选择权最小的边.,3. 算法描述:,步骤1:按照权的递增顺序排列图G的边,置集合T为空集.,步骤2:检查排列序表中第一条未检查的边,此边被放入T中当且仅当它不与T中的边形成回路。若这条边被加入T中,进入步骤3
5、,否则重复步骤2.,步骤3:若T有n-1条边,则停止,T即为所找的最小支撑树,否则,进入步骤2.,5. 实例:,解:abcdde-bd,排序: ab, cd,de,ec,bd,be,ac,ae,四. Prim算法,1. 算法思想(贪婪算法):,从顶点出发,对任意点,总是选择与其关联的权最小的边放入T中.,2. 算法描述:,步骤1:置集合T为空集,任选一点v放入树T中.,步骤2:将连接T中的点与V-V(T)中的点的所有边中权最小的边加入到T中,若权最小的边有多条,任选其一,若不可能把任一条边加入到T中,则停止,输出G非连通.,步骤3:若T有n-1条边,则停止,T即为所找的最小支撑树,否则,重复步
6、骤2.,5. 实例:,解:abbddc-de,1). 选点a,T=a,选出ab, 2). T=ab,选出bd, 3). T=ab,bd,选出dc, 4). T=ab,bd,dc,选出de,2 最短路径问题,一. 简介,1. 问题:寻找网络中两个顶点之间的最短路径问题.,2. 实例:希望利用公路开车从上海到北京,希望路程最短.,注:(1)点城市,边公路, 权距离,连通赋权图.,(2)所有权均非负.,二. Dijkstra 算法(1959),1. 算法思想:,2. 算法描述(从u0到un-1):,3. 实例:,1) S0=x,其他l(v)=,l(x)=0 2) l(a)=3,l(b)=8,l(c)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 图论图 论及 算法 课件
链接地址:https://www.31doc.com/p-3393779.html