Matlab最优化理论中的最短路问题 (3)
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项的矩阵，此时，可以用特殊的方法来表示和计算这样的矩阵。对于简单有向图 ，结点的邻接关系即是结点集 上的二元关系 ，也就是说，图 的图形表示即为 的关系图，而图 的邻接矩阵即为 的关系矩阵。
上一篇：合理利用可再生资源的策略