数学建模 图论方法专题图论方法专题 一 一 图的基本概念 二 二 三 三 最短路问题及其算法 四 四 最小生成树问题 五 五 E图与H图 图的矩阵表示 数学建模 数学建模 - - 图论 图论 3 * 一、图的基本概念数学建模 数学建模 - - 图论 图论 4 * 一、图的基本概念 一、图的基本概念 次数为奇数顶点称为奇点，否则称为偶点。 5 * 数学建模 数学建模 - - 图论 图论常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 与顶点v出关联的边的数目称为出度，记作d + (v)， 与顶点v入关联的边的数目称为入度，记作d - (v)。 用N(v)表示图G中所有与顶点v相邻的顶点的集合. 任意两顶点都相邻的简单图称为完全图. 有n个顶点的完全图记为K n 。 一、图的基本概念 数学建模 数学建模 - - 图论 图论几个基本定理： 一、图的基本概念 数学建模 数学建模 - - 图论 图论 若将图G的每一条边e都对应一个实数F(e), 则称F(e) 为该边的权, 并称图G为赋权图, 记为G = (V, E , F ). 设G = (V, E )是一个图, v
