菜单
  

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

  2. 基于模型的故障检测观测...

  3. MATLAB重庆市三峡库区的降...

  4. MATLAB上海车牌拍卖中标价估计模型的研究

  5. Matlab手绘多边形的识别方法和研究

  6. 线性方程组的迭代法及其Matlab实现程序

  7. 企业生产计划决策的多目标最优化模型

  8. 河岸冲刷和泥沙淤积的监测国内外研究现状

  9. 乳业同业并购式全产业链...

  10. 酸性水汽提装置总汽提塔设计+CAD图纸

  11. 大众媒体对公共政策制定的影响

  12. 电站锅炉暖风器设计任务书

  13. 中考体育项目与体育教学合理结合的研究

  14. 当代大学生慈善意识研究+文献综述

  15. 十二层带中心支撑钢结构...

  16. 杂拟谷盗体内共生菌沃尔...

  17. java+mysql车辆管理系统的设计+源代码

  

About

751论文网手机版...

主页:http://www.751com.cn

关闭返回