第六章-运筹学图与网络优化ppt课件.ppt

第六章-运筹学图与网络优化ppt课件.ppt

ID:58579131

大小:318.00 KB

页数:59页

时间:2020-10-20

第六章-运筹学图与网络优化ppt课件.ppt_第1页
第六章-运筹学图与网络优化ppt课件.ppt_第2页
第六章-运筹学图与网络优化ppt课件.ppt_第3页
第六章-运筹学图与网络优化ppt课件.ppt_第4页
第六章-运筹学图与网络优化ppt课件.ppt_第5页
资源描述:

《第六章-运筹学图与网络优化ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第六章图与网络优化第六章图与网络优化第1节图的基本概念第2节树第3节最短路问题第4节网络最大流问题第1节图的基本概念例1:我国北京、上海等十个城市间的铁路交通图如下图所示:北京徐州青岛天津济南武汉南京上海连云港郑州第1节图的基本概念例2:有甲、乙、丙、丁、戊五个球队,他们之间的比赛情况如下图所示:v甲v乙v丙v丁v戊第1节图的基本概念一、图的基本概念图:由一些点及一些点之间的连线组成。边:两点之间不带箭头的连线。弧:两点之间带箭头的连线。无向图:由点及边组成。有向图:由点及弧组成。第1节图的基本概念图例:v

2、2v1e3e2e1v2a1a2a3v3v1第1节图的基本概念二、无向图的基本概念端点:两个点vi,vj属于V,边[vi,vj]属于E,称vi,vj是边的端点。关连边:边[vi,vj]是点vi及点vj的关连边。环:边的两个端点相同。多重边:两个点之间多于一条的边。简单图:不含环和多重边的无向图。多重图:不含环,但含有多重边的无向图。第1节图的基本概念次:以点vi为端点的边的个数。悬挂点:次为1的点。悬挂边:连结悬挂点的边。奇点:次为奇数的点。偶点:次为偶数的点。孤立点:次为零的点。第1节图的基本概念图例:v2

3、e1v4v3v1e2v2v1e3e2e1不连通图第1节图的基本概念三、无向图的基本性质任何无向图中,顶点次数的总和等于边数的2倍。任何无向图中,次为奇数的顶点必为偶数个。第1节图的基本概念四、有向图的基本概念基础图:去掉有向图中所有弧上的箭头得到的无向图。始点、终点:弧(vi,vj)中,称vi为弧的始点,vj为弧的终点。第1节图的基本概念五、图的综合概念(一)无向图链:圈:第1节图的基本概念初等链:链中没有重复的点。初等圈:圈中没有重复的点。简单链:链中没有重复的边。简单圈:圈中没有重复的边。第1节图的基本

4、概念图例:问:(v1,v2,v3,v4,v5,v3,v6,v7)?(v1,v2,v3,v6,v7)?(v1,v2,v3,v4,v1)?(v4,v1,v2,v3,v5,v7,v6,v3,v4)?(v1,v2,v3,v5,v4,v3,v4,v1)?v2e1v4v3v1e2v5v6v7e3e4e5e6e7e8e9第1节图的基本概念(二)有向图链:路:第1节图的基本概念回路:初等路:路中没有重复的点。初等回路:回路中没有重复的点。第1节图的基本概念图例:问:(v3,a3,v2,a5,v4,a6,v5,a8,v3)?

5、(v1,a2,v3,a4,v4,a7,v6)?(v1,a2,v3,a8,v5,a10,v6)?(v1,a2,v3,a4,v4,a6,v5,a8,v3)?v2a1v4v3v1a2v5v6v7a6a5a4a3a10a9a8a7a11第2节树一、树的概念连通图:无向图中任意两点间至少有一条链相连。(不连通图)连通分图:不连通图中每个连通的部分。树:连通且不含圈的无向图。第2节树二、树的性质任何树中必然存在次为1的点。(1)树中次为1的点称为树叶(2)树中次大于1的点称为分枝点树的点有n个,则该树的边必有(n-1)

6、条。任何具有n个点、(n-1)条边的连通图必是树。树中任意两点之间有且只有唯一一条链。从一个树中去掉任一条边,则余下的图必是不连通图。在树中不相邻的两个点之间添上一条边,则必得到一个圈;反之再从该圈中任意去掉一条边,则必得到一个树。第2节树图例:v2v4v1v3v5第2节树三、支撑树支撑子图:支撑树:如果图G的支撑子图是一个树T,则称树T是图G的一个支撑树。支撑树的性质:图G有支撑树的充分必要条件是图G是连通图。第2节树图例:v2v4v1v3v5v2v4v1v3v5支撑子图第2节树四、最小支撑树赋权图:最小

7、支撑树:第2节树最小支撑树的求解方法方法一:避圈法基本做法:首先选一条最小权的边,以后每一步中,总从未被选取的边中选一条权最小的边,并使之与已选取的边不构成圈(每一步中,如果有两条或两条以上最小权的边,则任选一条)。第2节树例3:某工厂内联结六个车间的道路网如下图所示。已知每条道路的长,要求沿道路架设联结六个车间的电话线网,使电话线的总长最小。v3v2v4v1v5v6615572344第2节树方法二:破圈法基本做法:任取一个圈,从圈中去掉一条权最大的边,(如果有两条或两条以上最大权的边,则任去一条),在余下

8、图中重复这个步骤,一直到得到一个不含圈的图为止。破圈法求解例3习题6-1习题6-1:分别用避圈法和破圈法求下述图的最小支撑树。1、2、2314974363231457435741第3节最短路问题一、最短路的含义第3节最短路问题例4:某单行线交通网如下图所示,每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从v1出发,通过这个交通网到v8去,求使总费用最小的旅行路线。v41v6v2v16v5v74106v33

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。