《图与网络分析》 (2).ppt

该【《图与网络分析》 (2) 】是由【相惜】上传分享，文档一共【36】页，该文档可以免费在线阅读，需要了解更多关于【《图与网络分析》 (2) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第八章图与网络分析第一节图与网络的根本知识第二节树第三节最短路问题第四节最大流问题第五节最小费用流问题精选课件〔一〕哥尼斯堡七桥难题 1736年瑞士数学家欧拉〔〕在求解七桥一笔画难题时,就用了点线图来分析论证:每个点均有奇数条边时,一笔画问题无解。〔要求不重边〕CDAB(前苏)哥尼斯堡城中的普雷格尔河ACBD精选课件〔二〕“环球旅行〞问题 1857年,英国数学家哈密尔顿(Hamilton)创造了一种游戏,他用一个实心正12面体象征地球,正12面体的20个顶点分别表示世界上20座名城,要求游戏者从任一城市出发,寻找一条可经由每个城市一次且仅一次再回到原出发点的路,这就是“环球旅行〞问题。〔要求不重点〕精选课件〔三〕“中国邮路问题〞一个邮递员从邮局出发要走遍他所负责的每条街道去送信,问应如何选择适当的路线可使所走的总路程最短。这个问题就与欧拉回路有密切的关系。精选课件第一节图与网络的根本知识一、图与网络的根本概念〔一〕图及其分类5家企业业务往来关系甲乙戊丙丁精选课件由上面的例子可以看出,这里所研究的图与平面几何中的图不同,这里只关心图中有多少个点,点与点之间有无连线,至于连线的方式是直线还是曲线,点与点的相对位置如何,都是无关紧要的。工人与需要完成的工作电路网络城市规划交通运输、信息传递、物资调配甲乙丙丁戊ABCD精选课件定义1一个图是由点集V={vi}和V中元素的无序对的一个集合E={ek}所构成的二元组,记为G=(V,E),V中的元素vi叫做顶点,E中的元素ek叫做边。当V,E为有限集合时,G称为有限图,否那么,称为无限图。精选课件两个点u,v属于V,如果边(u,v)属于E,那么称u,v两点相邻。u,v称为边(u,v)的端点。?1?2?3?4?5e1e2e3e4e5e6精选课件两条边ei,ej属于E,如果它们有一个公共端点u,那么称ei,ej相邻。边ei,ej称为点u的关联边。用m(G)=|E|表示图G中的边数,用n(G)=|V|表示图G的顶点个数。在不引起混淆情况下简记为m,n。对于任一条边(vi,vj)属于E,如果边(vi,vj)端点无序,那么它是无向边,此时图G称为无向图。如果边(vi,vj)的端点有序,即它表示以vi为始点,vj为终点的有向边(或称弧),(自回路)。两个点之间多于一条边的,称为多重边。精选课件定义2不含环和多重边的图称为简单图,含有多重边的图称为多重图。(a)(b)(c)(d)精选课件