离散数学第九章图的基本概念及其矩阵表示.ppt

该【离散数学第九章图的基本概念及其矩阵表示 】是由【wxq362】上传分享，文档一共【23】页，该文档可以免费在线阅读，需要了解更多关于【离散数学第九章图的基本概念及其矩阵表示 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。离散数学第九章图的基本概念及其矩阵表示目录CONTENTS图的基本概念图的矩阵表示图的应用图论中的一些重要定理图论的发展前景01图的基本概念CHAPTER边没有方向,连接顶点的边不区分起点和终点。边有方向,连接顶点的边有起点和终点之分。无向图与有向图有向图无向图顶点图中的点,通常表示对象或实体。边连接两个顶点的线段,表示对象之间的关系。顶点与边路径与回路路径连接图中两个顶点的序列,路径上边的方向可以相同也可以不同。回路一个路径的起点和终点是同一个顶点,即形成一个环。02图的矩阵表示CHAPTER邻接矩阵是表示图中顶点之间连接关系的矩阵,每个元素表示相应顶点之间的连接关系。总结词邻接矩阵是一个方阵,行数和列数都等于图中顶点的数量。如果顶点i和顶点j之间存在一条边,则矩阵的第i行第j列的元素为1,否则为0。邻接矩阵可以直观地表示图的结构和连接关系。详细描述邻接矩阵总结词路径矩阵是表示图中路径信息的矩阵,每个元素表示相应路径上的边。详细描述路径矩阵是一个非方阵,其行数等于起点顶点到终点顶点的路径长度。矩阵中的元素表示路径上的边,如果路径上存在一条从顶点i到顶点j的边,则矩阵的第i行第j列的元素为1,否则为0。路径矩阵可以用于求解最短路径问题等图论问题。路径矩阵总结词回路矩阵是表示图中是否存在回路的矩阵,每个元素表示相应顶点是否构成回路。详细描述回路矩阵是一个非方阵,其行数等于图中顶点的数量。如果从顶点i出发经过若干个顶点能够回到起点顶点i,则矩阵的第i行所有元素都为1,否则为0。回路矩阵可以用于判断图是否存在环路等图论问题。回路矩阵