数学建模-图论讲稿

《数学建模-图论讲稿》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模图论方法专题图论方法专题一图的基本概念二三最短路问题及其算法四最小生成树问题五E图与H图图的矩阵表示六网络最大流ABCD哥尼斯堡七桥示意图问题1:七桥问题能否从任一陆地出发通过每座桥恰好一次而回到出发点？数学建模-图论七桥问题模拟图:ABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。数学建模-图论问题2:哈密顿圈（环球旅行游戏）十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？数学建模-图论问题3:四色问题对任何一张地图进行着色，两个共

2、同边界的国家染不同的颜色，则只需要四种颜色就够了。德·摩尔根致哈密顿的信（1852年10月23日）我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。……数学建模-图论1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和实践利用于工程技巧的电网络方程组的研究；1857年英国的凯莱(A.Cayley)也提出了树的概念，并运用于有机化合物的分子构造的研究中；1936年匈牙利的数学家哥尼格(D.Kon

3、ig)写出了第一本图论专著《有限图与无穷图的理论》，使图论成为一门独立的学科。图论的应用数学建模-图论由于管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大增进了图论的发展。特别是电子计算机的大量应用，使大规模问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的辅助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、经济治理等几乎所有学科领域都有应用。数学建模-图论数学建模-图论92021年10月2日一、图的基本概念102021年10月2日一

4、、图的基本概念数学建模-图论例：什么是匹配：把上图想象成3男4女搞对象（无同性吸引），连线代表彼此有好感，但最终只能1夫1妻，最终的配对结果连线就就是一个匹配。 什么是最大匹配：在有好感的基础上，能够最多发展几对。一、图的基本概念次数为奇数顶点称为奇点，否则称为偶点。112021年10月2日数学建模-图论常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.与顶点v出关联的边的数目称为出度，记作d+(v)，与顶点v入关联的边的数目称为入度，记作d-(v)。用N(v)表示图G中所有与顶点v相邻的顶点的集合.一、图的基本概念数学建模-图论几个基本

5、定理：一、图的基本概念数学建模-图论若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F).设G=(V,E)是一个图,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,则称v0v1…vk是G的一条通路.如果通路中没有相同的顶点,则称此通路为路径,简称路.始点和终点相同的路称为圈或回路.一、图的基本概念数学建模-图论顶点u与v称为连通的，如果存在u到v通路，任二顶点都连通的图称为连通图，否则，称为非连通图。极大连通子图称为连通分图。连通而无圈的图称为树,常用T表示树.树中最长路的边数称为树的高，度数

6、为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图，如果G的底图是树，则称G是有向树，也简称树。一、图的基本概念数学建模-图论邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）可达性矩阵直达矩阵等等……二、图的矩阵表示数学建模-图论1有向图的邻接矩阵A=(aij)n×n（n为结点数）例1：写出右图的邻接矩阵：解：二、图的矩阵表示数学建模-图论2有向图的权矩阵A=(aij)n×n（n为结点数）例2：写出右图的权矩阵：解：二、图的矩阵表示数学建模-图论3有向图的关联矩阵A=(aij)n×m（n为结点数m为

7、边数）有向图：无向图：二、图的矩阵表示数学建模-图论例3：分别写出右边两图的关联矩阵解：分别为：二、图的矩阵表示数学建模-图论二、图的矩阵表示4应用实例某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从{1，2，3，4，5，6)中任取一数．由于工艺及其它原因，制造锁具时对5个槽的高度有两个限制：(1)至少有3个不同的数；(2)相邻两槽的高度之差不能为5．满足以上条件制造出来的所有互不相同的锁具称为一批．我们的问题是如何确定每一批锁具的个数?1994年全国大学生数学建模竞赛B题(锁具装箱)中关于锁具总数的问题可叙述如下：数学建模-图论该问题用图论中的邻

8、接矩阵解决较为简单易见，令x=t-s，