Matlab最优化理论中的最短路问题 (3)
时间:2017-06-16 16:50 来源:毕业论文 作者:毕业论文 点击:次
1.1.2 有向图 有向图——设 是一个有 个顶点的非空集合： ； 是一个有 条有向边的集合： ，则称 和 这两个集合组成了一个有向图，记作有向图 。 若 ， 为有向边 的起点， 为有向边 的终点，则记 。 例1-2 给有向图 ，其中 ， ， 边与顶点的关系情况由表1-2给出 对表1-2，作几何图形，如图1-2所示。 类似与无向图，有向图 也有下列术语。 平行边——不同的有向边 的起点和终点相同，则称边 为有向图 的平行边。如图1-2中的 与 即为平行边。 孤立点—— 中不与 中任一条边关联的点称为 的孤立点。 简单图——无平行边的有向图称为简单图。 完备图——图中任意两个顶点 和 之间，恰有两条有向边 ，及 ，则称该有向图 为完备图。 基本图——把有向图 的每条边除去定向就得到一个相关的无向图 ，称 为 的基础图。称 为 的定向图。 子图——设 ， 都是有向图，且 则称 为 的子图，并记为 。 导出子图——若 则称有向图 为有向图 中关于 的导出子图，。 链——若 是有向图 的基础图 中的一条链，则 就称为 中一条链。 路——若 是有向图 的基本图 中一条链，且有 ，则称 为 的 至 的单向路，简称为路。 路径——若有向图 的路 中的每一个顶点都不相同，则称 为 的 至 的单向路径，并称 可达 。 回路——若有向图 的单向路径 的第一个顶点与最后一个顶点相同，则称 为 的单向回路，简称回路。 若 为链、路、路径、回路 中的边，则可写为 。 在简单图中，可用顶点序列来表示相应的链、路、路径。 1.2 图的矩阵表示 如何把图的有关信息输入和存储到计算机里去呢？我们知道，图的最本质的内容是顶点和边,顶点与顶点之间的关联关系，我们不难用矩阵来表示这种关联关系。 1.2.1 关联矩阵 定义：设 是有向图，且 , ，若用矩阵的行标号 对应图 的顶点下标，用列标号 对应于图 的边的下标，可构造一个 阶矩阵 为有向图 的关联矩阵，其中 设是无向图， 且 , ，若用矩阵的行标号 对应图 的顶点下标，用列标号 对应于图 的边的下标，可构造一个 阶矩阵 为无向图 的关联矩阵，其中 例1 给出下图G和图D的关联矩阵。 解：图G的关联矩阵为 图D的关联矩阵为 从关联矩阵可以看出无向图的一些性质： （1） 因为每条边关联两个顶点，所以关联矩阵的每一列只有两个1。 （2） 关联矩阵的每一行中元素之和为对应顶点的度。 （3） 若某行中元素全为0，则对应的顶点为孤立点。 （4） 重边所对应的列完全相同。 关于有向图的一些性质可以类似地推出。 1.2.2 邻接矩阵 定义：设 是任意图，其中V={ },E={ },若矩阵的行标号 和列标号 都对应图 的顶点下标，则可构造一个 阶方阵A=( )为G的邻接矩阵。其中 为图G中以 为起点且以 为终点的边的数目。 例2 给出下图所示图 的邻接矩阵。 解：图 的顶点顺序为 的邻接矩阵是 图 的顶点顺序为 的邻接矩阵是 由定义知，无向图的邻接矩阵是对称矩阵，而有向图的邻接矩阵未必是对称矩阵。对于简单无向图 ，其中， ，则 的邻接矩阵是一个 阶0-1矩阵，若此时图里的边相对少时，邻接矩阵是稀疏矩阵，即只有很少的非0项的矩阵，此时，可以用特殊的方法来表示和计算这样的矩阵。对于简单有向图 ，结点的邻接关系即是结点集 上的二元关系 ，也就是说，图 的图形表示即为 的关系图，而图 的邻接矩阵即为 的关系矩阵。 (责任编辑：qin) |