资源描述：
《数学建模-图论讲稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学建模图论方法专题图论方法专题一图的基本概念二三最短路问题及其算法四最小生成树问题五E图与H图图的矩阵表示数学建模-图论32021年9月7日一、图的基本概念数学建模-图论42021年9月7日一、图的基本概念一、图的基本概念次数为奇数顶点称为奇点，否则称为偶点。52021年9月7日数学建模-图论常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.与顶点v出关联的边的数目称为出度，记作d+(v)，与顶点v入关联的边的数目称为入度，记作d-(v)。用N(v)表示图G中所有与顶点v相邻的顶点的集合.任意两顶点都相
2、邻的简单图称为完全图.有n个顶点的完全图记为Kn。一、图的基本概念数学建模-图论几个基本定理：一、图的基本概念数学建模-图论若将图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通路，任二顶点都连通的图称为
3、连通图，否则，称为非连通图。极大连通子图称为连通分图。连通而无圈的图称为树,常用T表示树.树中最长路的边数称为树的高，度数为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图，如果G的底图是树，则称G是有向树，也简称树。一、图的基本概念数学建模-图论邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）可达性矩阵直达矩阵等等……二、图的矩阵表示数学建模-图论1有向图的邻接矩阵A=(aij)n×n（n为结点数）例1：写出右图的邻接矩阵：解：二、图的矩阵表示数学建模-图论2有向
4、图的权矩阵A=(aij)n×n（n为结点数）例2：写出右图的权矩阵：解：二、图的矩阵表示数学建模-图论3有向图的关联矩阵A=(aij)n×m（n为结点数m为边数）有向图：无向图：二、图的矩阵表示数学建模-图论例3：分别写出右边两图的关联矩阵解：分别为：二、图的矩阵表示数学建模-图论二、图的矩阵表示4应用实例某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从{1，2，3，4，5，6)中任取一数．由于工艺及其它原因，制造锁具时对5个槽的高度有两个限制：(1)至少有3个不同的数；(2)相邻两槽的高度之差不能为5．满足以上条
5、件制造出来的所有互不相同的锁具称为一批．我们的问题是如何确定每一批锁具的个数?1994年全国大学生数学建模竞赛B题(锁具装箱)中关于锁具总数的问题可叙述如下：数学建模-图论该问题用图论中的邻接矩阵解决较为简单易见，x=t-s，其中，t代表相邻两槽高度之差不为5的锁具数，即：满足限制条件(2)的锁具数，s代表相邻两槽高度之差不为5且槽高仅有1个或2个的锁具数，即：满足限制条件(2)但不满足限制条件(1)的锁具数．我们用图论方法计算t和s.数学建模-图论二、图的矩阵表示（应用实例及解法分析）在G中t每一条长度为4的道路对应于一个相
6、邻两槽高度之差不超过5的锁具，即满足限制条件（2）的锁具，反之亦然，于是可以通过G的邻接矩阵A来计算t的值，具体步骤如下：数学建模-图论二、图的矩阵表示（应用实例及解法分析）构造无向图124356因此，数学建模-图论二、图的矩阵表示（应用实例及解法分析）又令其中yi表示满足限制条件(2)但不满足限制条件(1)且首位为i的锁具数,（i=1,2,3,4,5,6),显然y1=y6,y2=y4=y3=y5,于是我们只需要计算y1和y2.计算y1可分别考虑槽高只有1，12，13，14，15的情形．若只有1，这样的锁具效只有1个，若只有1
7、和i(i=2,3,4,5)，这样的锁具数=G中以1和i为顶点，长度为3的道路数，此数可通过A的子矩阵A1i计算得到．数学建模-图论二、图的矩阵表示（应用实例及解法分析）124356二、图的矩阵表示（应用实例解法分析）事实上，因为其中i=2,3,4,5,显然y1=1+(4+4+4+4-1)4=61.同理，计算y2时应考虑槽高只有2,21,23,24,25,26时的情形，类似计算可得y2=1+(4+4+4+4-1)×5=76．于是，s=61×2+76×4=426，x=6306-426=5880.该算法既易理解又易操作并且又可扩展．
8、数学建模-图论二、图的矩阵表示（应用实例及解法分析）公交线路选择问题：在给定某城市公交线路的公交网信息后，求任意两个站点之间的最佳出行路线，包括换乘次数最少、出行时间最短、出行费用最低等。以下图的简化公交网为例来说明。数学建模-图论12345图中由两条公交线路组成，实线表示第
