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

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

四、子图

图 H 叫做图 G 的子图，记作 ，如果 若 H 是
G 的子图，则 G 称为 H 的母图，G 的支撑子图是指满足 V(H)=V(G) 的子图 H。

五、顶点的度

设 G 中与 v 关联的边数（每个环算作两条边）称为 v 的度 (degree)，
记作 d(v)。若 d(v) 是奇数，称 v 是奇顶点；d(v) 是偶数，称 v 是偶顶点。关于顶

点的度，我们有如下结果
任意一个图的奇顶点的个数是偶数。

六、图与网络的数据结构

网络优化领域探讨了网络中多种优化模型与算法的设计与应用。要在计算机
上实施这些网络优化算法，首要任务是找到一种合适的数据结构来表达图和网络。
实际上，算法的效率往往受到所选用的网络表示方式及其操作过程中间结果的方
法的影响。本文将概述在计算机科学中用于描述图和网络的五种常见表示技术：

邻接矩阵、关联矩阵、弧列表、邻接列表及星型表示。在下面数据结构的讨论中，
我们首先假设 G =(V， A) 是一个简单有向图 并假设 V 中的顶点用

自然数 1，2，…，n 表示或编号， A 中的弧用自然数 1，2，…，m 表示或编号。
对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，
给出一些说明。
1. 邻接矩阵表示法

邻接矩阵表示法是将图以邻接矩阵的形式存储在计算机中。图 G=(V， A) 的
邻接矩阵是如下定义的：C 是一个 n×n 的 0-1 矩阵，即

也就是说，当两个节点间存在一条连接时，邻接矩阵中的相应位置会被标记
为 1；反之，则标记为 0。这种方法的特点在于其简洁性和直观性。然而，考虑
到邻接矩阵总共包含 n² 个元素，而其中仅有 m 个是非零值，若网络结构较为稀疏，

192