资源描述：
《《数学建模图论》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学建模图论方法专题专题板块系列概率统计专题1优化专题2模糊方法及微分方程专题3图论方法专题4www.shumo.cn华中农业大学数学建模基地图论方法专题一图论的基本概念二最短路与最小生成树三二部图的匹配四网络流www.shumo.cn华中农业大学数学建模基地ABCD哥尼斯堡七桥示意图问题1:七桥问题能否从任一陆地出发通过每座桥恰好一次而回到出发点？图论的基本概念www.shumo.cn华中农业大学数学建模基地七桥问题模拟图:ABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回
2、到出发地。图论的基本概念www.shumo.cn华中农业大学数学建模基地问题2:哈密顿圈（环球旅行游戏）十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？图论的基本概念www.shumo.cn华中农业大学数学建模基地问题3:四色问题对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了。德·摩尔根致哈密顿的信（1852年10月23日）我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜
3、色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。……图论的基本概念www.shumo.cn华中农业大学数学建模基地问题4(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进
4、度的要害工序是哪几个？图论的基本概念www.shumo.cn华中农业大学数学建模基地定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中①V或V(G)称为G的顶点集,V≠Φ,其元素称为顶点或结点,简称点;②E或E(G)称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.图论的基本概念www.shumo.cn华中农业大学数学建模基地如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.如果E的每一条边都是无向边,则称G为无向图;如果E的每
5、一条边都是有向边,则称G为有向图;否则,称G为混合图.记E={e1,e2,…,em}(ek=vivj).图论的基本概念www.shumo.cn华中农业大学数学建模基地对于一个图G=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.称点vi,vj为边vivj的端点.有边联结的两个点称为相邻顶点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.有向图中的关联又分出关联和入关联。图论的基本概念www.shumo.cn华中农业大学数学建模基地常用d(v)表示图G中与顶点v关联的边的数目
6、,d(v)称为顶点v的度数.与顶点v出关联的边的数目称为出度，记作d+(v),与顶点v入关联的边的数目称为入度，记作d-(v)。用N(v)表示图G中所有与顶点v相邻的顶点的集合.图论的基本概念任意两顶点都相临的简单图称为完全图.有n个顶点的完全图记为Kn。www.shumo.cn华中农业大学数学建模基地几个基本定理：图论的基本概念www.shumo.cn华中农业大学数学建模基地用图论思想求解以下各题例1、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出
7、渡河方法。图论的基本概念www.shumo.cn华中农业大学数学建模基地解：用四维0-1向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取1，否则取0.）共24=16种状态，由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允许的，从而对应状态（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允许的，图论的基本概念www.shumo.cn华中农业大学数学建模基地人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）
8、（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。图
