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项的矩阵,此时,可以用特殊的方法来表示和计算这样的矩阵。对于简单有向图 ,结点的邻接关系即是结点集 上的二元关系 ,也就是说,图 的图形表示即为 的关系图,而图 的邻接矩阵即为 的关系矩阵。
上一篇:合理利用可再生资源的策略
下一篇:公司人力资源配置优化研究+文献综述

矩阵在数学建模中的应用及其MATLAB求解

数字签密的理论研究与实现

基于粗糙集理论的决策规则获取方法研究

关于均值不等式的探讨

多元表征理论在数学中的应用

约束最优化问题的算法研...

不动点的理论及其应用

医院财务风险因素分析及管理措施【2367字】

C#学校科研管理系统的设计

公寓空调设计任务书

中国学术生态细节考察《...

志愿者活动的调查问卷表

承德市事业单位档案管理...

国内外图像分割技术研究现状

神经外科重症监护病房患...

10万元能开儿童乐园吗,我...

AT89C52单片机的超声波测距...