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