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项的矩阵,此时,可以用特殊的方法来表示和计算这样的矩阵。对于简单有向图 ,结点的邻接关系即是结点集 上的二元关系 ,也就是说,图 的图形表示即为 的关系图,而图 的邻接矩阵即为 的关系矩阵。
- 上一篇:合理利用可再生资源的策略
- 下一篇:公司人力资源配置优化研究+文献综述
-
-
-
-
-
-
-
河岸冲刷和泥沙淤积的监测国内外研究现状
乳业同业并购式全产业链...
酸性水汽提装置总汽提塔设计+CAD图纸
大众媒体对公共政策制定的影响
电站锅炉暖风器设计任务书
中考体育项目与体育教学合理结合的研究
当代大学生慈善意识研究+文献综述
十二层带中心支撑钢结构...
杂拟谷盗体内共生菌沃尔...
java+mysql车辆管理系统的设计+源代码