《运筹学》教学课件 第6章 图与网络分析.ppt

《运筹学》教学课件 第6章 图与网络分析.ppt

  1. 1、本文档共111页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
运 筹 帷 幄 之 中;Leonhard Euler (公元1707-1783年);哥尼斯堡七桥问题;第6章 网 络 分 析; 图 与 子 图;无向图的根本概念;关联:一条边的端点称为与这条边的关联 邻接:与同一条边关联的端点称为是邻接的,同时如果两条边 有一个公共端点,那么称这两条边是邻接的 有限图:任何图G=(N,E),假设N和E都是有限集合,那么称G为… 空图:没有任何边的图 平凡图:只有一个点的图 简单图:一个图,既没有环,也没有重边,那么称为… 例如:(a)是 一简单图,但(b)就不是简单图.;完全图:每一对点之间均有一条边相连的图 二分图 G=(N,E):存在的一个二分划(S,T),使得G的每条边有一个端点在S中,另一个端点在T中 完全二分图 G=(S,T,E):S中的每个点与T中的每个点都相连的简单二分图 简单图G的补图 :与G有相同顶点集合的简单图,且补图中的两个点相邻当且仅当它们在G中不相邻; ;7;无向完全图:在无向图中,如果任意两个顶点之间存在边。 ;关联矩阵;右图的关联矩阵是 右图的关联矩阵是 ;邻接矩阵;图〔6.1.7〕的邻接矩阵是 图〔6.1.8〕的邻接矩阵是 ;几个根本结论;子 图;;点i和j点是连通的:G中存在一条{i,j}路 G是连通的:G中任意两点都是连通的 连通分支:G的极大连通子图 图6.2.1中〔a〕是连通图;〔b〕是一个具有三个连通分支的非连通图。 ; 图的连通性;有向图G中的一条有向路:个点和弧的交错序列 (ni,aij,nj,…,nk,akl,nl), 记为(ni,nl)有向路 简单有向路:弧不重的有向路 初级有向路:点不重的有向路 有向回路:至少包含一条弧且ni=nj的(ni,nj)有向路 简单有向回路:弧不重的有向回路 初级有向回路:点不重的有向回路;如以下图: (1,2,4,3,2,4,6)是一条(1,6)有向路; (1,2,4,5,3,4,6)是一条(1,6)简单有向路; (1,2,3,4,6)是一条〔1,6〕初级有向路;(1,2,4,3,2,4,5,3,1)是一条有向回路;(1,2,3,4,5,3,1)是一条简单有向回路;(1,2,4,5,3,1)是一条初级有向回路。;点i和点j是强连通的:G中存在一条(i,j)有向路,也存在一条(j,i)有向路 G是强???通的:G中任意两点都是强连通的 G的强连通分支:G的极大连通子图 图6.2.4中,〔a〕是一个强连通分支,〔b〕是一个具有三个强连通分支的非强连通图。;§6.2 有向图的连通性;2. 割集;图中{2,4}和{6,7}都是割边 图中,边集{{2,1},{2,4},{2,3}}和边集{{2,3},{2,4},{1,4},{1,5}}均为割集;割集的性质; 树与支撑树; 树与支撑树; 树与支撑树; 最小树问题;----最小树及其性质;---求最小树的Kruskal算法;D;用Kruskal算法求解以下图所示网络的最小树,其中每条边上的数表示该边的权值。 ;计算的迭代过程 ;---Kruskal算法的算法复杂性分析; 最小树问题;U={A} ;例:;例:;例:;例:;例:;例:;图; 最小树问题; 最小树问题; 最短有向路问题;1. 最短有向路方程; 最短有向路问题;2. Dijkstra算法步骤: ;---- 算例;--- 算法的实现过程 ; 最短有向路问题; 最短有向路问题;D;参加边信息的存储后的算法;D;D;D;---- 算法复杂性; 最大流问题;----- 根本概念 -----;----主要定理 ----;----- 算法步骤 -----;--- 算例 ---;计算的迭代过程 ;--- 算法复杂性 ---; 最小费用流问题;问 题;线性规划形式;对偶规划;算法步骤 ;算例;计算的迭代过程〔1〕;;计算的迭代过程〔3〕;计算的迭代过程〔4〕;算法复杂性 ;运输问题;对偶规划;算法步骤;算例;迭代过程;续〔1〕;w w;续〔2〕;续〔3〕;;续〔4〕;续〔5〕;w w; 最大对集问题;根本概念;主要定理;根本思想;算法步骤;算例;迭代过程〔1〕;迭代过程〔2〕;算法复杂性;分派问题;对偶规划;算法步骤 ;算法步骤 〔续〕;算例;

文档评论(0)

qjgyx + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档