- 1、本文档共111页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 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〕;算法复杂性;分派问题;对偶规划;算法步骤 ;算法步骤 〔续〕;算例;
您可能关注的文档
- 《园艺植物病虫害防治》 1.3第一章 园艺植物病害基础知识.ppt
- 《园艺植物病虫害防治》 2.1第二章 园艺昆虫基础知知识.ppt
- 《园艺植物病虫害防治》 2.2第二章 园艺昆虫基础知知识.ppt
- 《园艺植物病虫害防治》 2.3第二章 园艺昆虫基础知知识.ppt
- 《云计算基础架构构建与应用 》 电子资源 PPT 第二章.ppt
- 《云计算基础架构构建与应用 》 电子资源 PPT 第三章.ppt
- 《云计算基础架构构建与应用 》 电子资源 PPT 第一章.ppt
- 《云计算基础架构构建与应用 》 电子资源 PPT 任务八Cinder的手工安装与配置.ppt
- 《云计算基础架构构建与应用 》 电子资源 PPT 任务二 MySQL数据库的手工安装与配置.ppt
- 《云计算基础架构构建与应用 》 电子资源 PPT 任务九Dashboard的安装与配置.ppt
文档评论(0)