资源描述：
《数学建模图论模型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论模型1图论模型图论基本概念最短路径算法最小生成树算法遍历性问题二分图与匹配网络流问题关键路径问题系统监控模型着色模型21、图论的基本概念问题1(哥尼斯堡七桥问题):能否从任一陆地出发通过每座桥恰好一次而回到出发点？3欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.4问题2(哈密顿环球旅行问题):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？欧拉问题是“边遍历”，哈密尔顿问题是“点遍历”5问题3(四色问题):对任何一张地图进行着色
2、，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题4(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？6图的定义图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系
3、的一个数学系统.定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中①V称为G的顶点集,V≠,其元素称为顶点或结点,简称点;②E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.7如果E的每一条边都是无向边,则称G为无向图(如图1);如果E的每一条边都是有向边,则称G为有向图(如图2);否则,称G为混合图.图1图2并且常记:V={v1,v2,…,vn},
4、V
5、=n;E={e1,e2,…,em}(ek=vi
6、vj),
7、E
8、=m.称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.该图称为(n,m)图8对于一个图G=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.例如,设V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},则G=(V,E)是一个有4个顶点和6条边的图,G的图解如下图所示.9一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、
9、确定的图解去表示一个图.10有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.对于有向图,还有出度和入度之分.用N(v)表示图G中所有与顶点v相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2dout(v1)=dout(v3)=dout(v4)=2,dout(v2)=1din(v1)=din(v3)=din(v4)=2,din(v2)=111握手定理握手定理：无向图中，所有结点的度数之和等于2m。右图：推论1：无向图中
10、必有偶数个度数为奇数的结点。推论2：有向图中所有结点的出度之和等于入度之和。d(v1)=d(v3)=d(v4)=4,d(v2)=212我们今后只讨论有限简单图：(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图,则任意两个顶点最多只有一条边与之相联结;(4)若是有向图,则任意两个顶点最多只有两条边与之相联结.当两个顶点有两条边与之相联结时，这两条边的方向相反.如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.13定义2若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并
11、称图G为赋权图(网络),记为G=(V,E,F).定义3任意两点均有通路的图称为连通图.定义4连通而无圈的图称为树,常用T表示树.14常用的图给定图G=和G’=是两个图，如果有V’⊆V和E’⊆E,则称图G’是图G的子图。若V’=V称图G’是图G的生成子图；若将图G的每一条边e都对应一个实数F(e)，则称F(e)为该边的权，并称图G为赋权图(网络),记为G=。任意两点均有通路的图称为连通图。连通而无圈的图称为树，常用T=表示树。若图G’是图G的生成子图，且G’又是一棵树，则称G’是图G的生成树。15例R
12、amsey问题问题：任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。图论模型：用红、蓝两种颜色对6个顶点的完全图K6的边进行任
