数学建模提高班第六讲网络优化模型及案例分析.pptx

网络优化模型及案例分析本专项学习目一个表示工具——图练习题图论起源：七桥问题欧拉——图论之父
■定理1：一个图存在通过每边正好一次回到出发点路线充要条件是：
1）图要是连通
2）与图中每一顶点相连边必须是偶数条。
于是得出结论：七桥问题无解。无向图，普通用大写字母G,H表示。无向图：G=(V,E)，
顶点集：V；边集：E。
e与顶点u,v相关联。
u与v相邻。
两边相邻。
重边
两种特殊图：
简朴图完全图，记为Kn有向图：网络(G)和(G)分别表示图G顶点数和边数
在无向图中，v度数，记为d(v)；
在有向图中，v出度，记为d+(v);v入度，记为d-(v)。一个时间安排问题一个时间安排问题人狼羊菜渡河问题南岸状态：
16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，图矩阵表示办法无向图邻接矩阵：A=(aij)nn，其中关联矩阵无向图关联矩阵：M=(mij)nm,其中边矩阵最短路问题及算法2)在赋权图G中，从顶点u到顶点v含有最小权1)赋权图中从给定点到其余顶点最短路Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.Dijkstra算法:求G中从顶点u0到其余顶点最短路.定义2依据顶点v标号l(v)取值路径，使到v表22)求赋权图中任意两顶点间最短路算法基本思想（I）求距离矩阵办法.（II）求路径矩阵办法.（IV）Floyd算法：求任意两顶点间最短路.例2求下图中加权图任意两点间距离与路径.最小生成树及算法1)树定义与树特性定理2设G是含有n个顶点图，则下述命题等价：2）图生成树（II）找图中生成树办法A避圈法a)深探法3B破圈法B破圈法3)最小生成树与算法AKruskal算法（或避圈法）例7用Kruskal算法求下图最小树.B破圈法旅行售货员问题旅行售货员问题或货郎担问题一个可行办法:定义7若对于某一对i和j，有例9对下图,用二边逐次修正法求较优H圈.分析:找出这个解好坏可用最优H圈权1.设某校田径选拔赛共设六个项目标比赛，即跳高，跳远，标枪，铅球，100米和200米短跑，要求每个选手至多参加三个项目标比赛。现有七名选手报名，选手所选项目如表1所表示。现在要求设计一个比赛日程安排表，使得在尽也许短时间内完成比赛。表1参赛选手比赛项目表附录：图论算法matlab实现最短路问题最小生成树问题