图论(túlùn)方法专题数学(shùxué)建模-图论数学(shùxué)建模-图论一、图的基本概念常用(chánɡyònɡ)d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.与顶点v出关联的边的数目称为出度，记作d+(v)，与顶点v入关联的边的数目称为入度，记作d-(v)。几个基本(jīběn)定理：若将图G的每一条边e都对应(duìyìng)一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F).顶点(dǐngdiǎn)u与v称为连通的，如果存在u到v通路，任二顶点(dǐngdiǎn)都连通的图称为连通图，否则，称为非连通图。极大连通子图称为连通分图。邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）可达性矩阵直达(zhídá)矩阵等等……1有向图的邻接矩阵A=(aij)n×n（n为结点(jiédiǎn)数）2有向图的权矩阵(jǔzhèn)A=(aij)n×n（n为结点数）3有向图的关联矩阵A=(aij)n×m（n为结点(jiédiǎn)数m为边数）例3：分别(fēnbié)写出右边两图的关联矩阵二、图的矩阵(jǔzhèn)表示该问题用图论中的邻接矩阵解决较为简单易见，x=t-s，其中(qízhōng)，t代表相邻两槽高度之差不为5的锁具数，即：满足限制条件(2)的锁具数，s代表相邻两槽高度之差不为5且槽高仅有1个或2个的锁具数，即：满足限制条件(2)但不满足限制条件(1)的锁具数．我们用图论方法计算t和s.在G中t每一条长度(chángdù)为4的道路对应于一个相邻两槽高度之差不超过5的锁具，即满足限制条件（2）的锁具，反之亦然，于是可以通过G的邻接矩阵A来计算t的值，具体步骤如下：因此(yīncǐ)，又令二、图的矩阵(jǔzhèn)表示（应用实例解法分析）二、图的矩阵(jǔzhèn)表示（应用实例及解法分析）若将图G的每一条边e都对应(duìyìng)一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F).重要(zhòngyào)性质：设有给定连接(liánjiē)若干城市的公路网，寻求从指定城市到各城市的最短路线。32333435363738394041424344454647顶点(dǐngdiǎn)u与v称为连通的，如果存在u-v通路，任二顶点(dǐngdiǎn)都连通的图称为连通图，否则，称为不连通图。极大连通子图称为连通分图。若任意一个(yīɡè)连通的图G=<V,E>的生成子图T=<V’,E’>(V’=V,E’为E的子集)为树,这棵树T称为图G的生成树.怎样(zěnyàng)找出最小生成树？？？53545556575859称经过图G=(V,E)的每条边恰好(qiàhǎo)一次的路为Euler路径，经过G的每条边恰好(qiàhǎo)一次的回路为Euler回路。称有Euler回路的图为Euler图中国邮递员问题：一个邮递员从邮局取出邮件后，需要到他管辖区域内的每条街道进行投递，送完邮件后返回邮局，问如何选择一条总路程(lùchéng)最短的投递路线？65666768697072与最短路问题相反，至今未找到有求解旅行商问题的有效算法，我们试图寻找一个比较(bǐjiào)好的方法，但不一定是最优解；首先给出近似最优的改良后的最邻近算法，称为改良圈算法，改良圈算法是一种近似算法，给出的结果不一定是最优的，但是有理由认为它常常是比较(bǐjiào)好的。该算法的matlab程序为：77787980ThankYou!感谢您的观看(guānkàn)！