第05讲 图论模型.pdf

第5 讲 图论模型 司守奎 烟台市，海军航空工程学院数学教研室 Email ：sishoukui@163.com 5.1 图与网络的数据结构 5.1.1 图的概念 定义5.1 非赋权图 一个非赋权图是由点集V {v }和 中元素的无序对的一个集合E {e }所构成的二 V i k 元组，记为 ， 中的元素 叫做顶点， 中的元素 叫做边。 G (V,E) V vi E ek 定义5.2 赋权图 赋权图（网络） 是一个三元组，记为 ，其中V {v ,,v }为顶点集 G G (V,E , W) 1 n 合， 为边的集合，W (w ) 为邻接矩阵（或权重矩阵），其中 E ij nn 顶点v 与v 之间边的权重, (v ,v ) E  i j i j  wij  （5-1） 0（或）, v 与v 之间无边时.  i j  当顶点与顶点之间的关系是对称关系时，对应的图是无向图，除非特殊说明，我们所说 的图都是指无向图。当顶点与顶点之间的关系是非对称关系时，对应的图为有向图。 定义5.3 有向图 有向图 是一个二元组，记为 ，其中 为顶点集合， 为弧（带箭头的边） D D (V, A) V A 的集合。 定义5.4 赋权有向图 赋权有向图 是一个三元组，记为 ，其中V {v ,,v }为顶点集合， D D (V, A, W) 1 n A 为弧（带箭头的边）的集合，W (w ) 为邻接矩阵，其中 ij nn 顶点v v 的弧的权重, 当v v 有弧时  i j i j wij  （5-2 ） 0（或）, 当v v 无弧时.  i j  当 （或 ）为非赋权图时，也可以看成赋权图，邻接矩阵 G D 1， 当v 与v 间有边(弧