建模M05-图的模型和基本概念.ppt

5-1 图的模型和基本概;一、 概论二、 最短路问题;哥尼斯堡“七桥问题” ;1998年全国大学生 数学模;2 图的基本概念 定;在图G中，与V 中顶点的有序偶;图G中，如果任意两个不同的顶点;在无向图G中，若边e=(vi，;点边交替序列l= v0 e1 ;若将图G的每一条边e都对应一个;例 图G如右图所示，是一;三、 图的矩阵表示(1)邻接矩;返回例斡敬片叙点乓滑行狡族潜矩;1 单源问题最短路的性质;Dijkstra算法的步骤： ;例返回岂诽巧墟爪加善戌府刨动绵;2 每对顶点之间的最短;Floyd算法的步骤：Step;例 某公司在六个城市中有分公司;将捌狄展用伊漫诛捏狮霜晃眨须瞄;吉瓜矢监画艇实已堤胁朔棕嫂轧疚;D6（1，2）＝35，故从c1;1 哈密顿路径问题定义 ;无向赋权完全图，一种简单的构造;最邻近算法所求为：（ａ，ｃ，ｅ;2、推销员问题（TSP）定义 ;定理 如果赋权图 G＝;对已构造的Hamilton圈改