Page 201 - 数学建模算法与应用

第八章 图与网络模型及方法应用

当边 ek = vi v j 时，称 vi ，v j 为边 ek 的端点，并称 vi 与 vi 相邻；边 ek 称
为与顶点 vi ，v j 关联。如果某两条边至少有一个公共端点，则称这两条边在图

G 中相邻。边上赋权的无向图称为赋权无向图或无向网络。对图和网络不作严格
区分，因为任何图总是可以赋权的一个图称为有限图，如果它的顶点集和边集都

有限。图 G 的顶点数用符号 |V | 或 (G) 表示，边数用 | E | 或 (G) 表示。
当讨论的图只有一个时，总是用 G 来表示这个图。常略去字母 G。
端点重合为一点的边称为环。

一个图称为简单图，如果它既没有环也没有两条边连接同一对顶点。

二、 有向图

定义一个有向图 G 是由一个非空有限集合 V 和 V 中某些元素的有序对集合
A 构成的二元组，记为 G (V，A)。其中 V ={v 1 ，v 2 ，…，v n } 称为图 G 的顶点

集或节点集，V 中的每一个元素 v i (i 1 ，2，…L，n) 称为该图的一个顶点或节点；
A={a 1 ，a 2 ，…，a m } 称为图 G 的弧集，A 中的每一个元素 ak ( 即 V 中某两个元
素 vi ，v j 的有序对 ) 记为 ak = (vi ，v j) 或 ak=v i vj(k= 1，2…，n)，被称为该图

的一条从 v i 到 vj 的弧。当弧 ak =vi v j 时，称 vi 为 ak 的尾，v j 为 ak 的头，并
称弧 ak 为 vi 的出弧，为 v j 的入弧。

对应于每个有向图 D ，我们可以在相同顶点集上作一个图 G ，而使得对于
D 的每条弧，G 有一条有相同端点的边与之相对应。这个图称为 D 的基础图。

这样的有向图称为 G 的一个定向图。以下若未指明“有向图”三字，“图”字
皆指无向图。

三、完全图、二分图

每一对不同的顶点都有一条边相连的简单图称为完全图。n 个顶点的完全图
记为 Kn 。

若 （这里 X 表示集合 X 中的元素个）X
中无相邻顶点对，Y 亦然，则称 G : 则 则称 G 为完全二

分图，记成

191