美文网首页
关联矩阵与邻接矩阵 2018-11-27

关联矩阵与邻接矩阵 2018-11-27

作者: 默写年华Antifragile | 来源:发表于2018-11-27 20:09 被阅读32次

参考: 关联矩阵与邻接矩阵

1. 邻接矩阵

1.1 定义

设无向图 G=(V, E)，其中顶点集 V = {v_1, v_2,\cdots, v_n}, 边集 E={e_1, e_2, \cdots, e_m}，
用 a_{ij}表示顶点v_i与顶点v_j之间的边的数目，可能取值为0, 1, 2, ....,
称所得矩阵A=A(G)=(a_{ij}))_{n \times n}为图 G 的邻接矩阵

1.2 邻接矩阵的性质

  • A(G) 是对称矩阵
  • 若 G 是无环图，则A(G)中第 i 行(列)的元素之和等于顶点v_i的度

类似地，有向图D的邻接矩阵A(D)=(a_{ij})_{n \times n}，a_{ij}表示从始点v_i到终点v_j的有向边的条数，其中v_i和v_j为D的顶点

e.g. 求下图的邻接矩阵


其邻接矩阵如下所示：

邻接矩阵： \left[ \begin{matrix} 0&1&1&0\\ 0&0&0&0 \\ 0 &1 & 0 &1\\ 1&0&0&0 \end{matrix} \right] 关联矩阵： \left[ \begin{matrix} 1&0&0&-1&1\\ -1&-1&0&0&0 \\ 0 &1 & 1 &0 &-1\\ 0&0&-1&1&0 \end{matrix} \right]

相关文章

  • 关联矩阵与邻接矩阵 2018-11-27

    参考: 关联矩阵与邻接矩阵 1. 邻接矩阵 1.1 定义 设无向图 G=(V, E)，其中顶点集 , 边集 ，用 ...

  • 离散数学中的图矩阵

    本文涉及到的图矩阵主要包括邻接矩阵和关联矩阵，在离散数学中这部分内容属于用矩阵来表示图。 邻接矩阵 用矩阵表示图，...

  • 数据结构与算法 学习笔记-4

    有向图 稀疏矩阵与邻接矩阵 邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,...

  • 数据结构之图的存储结构邻接矩阵法

    一、邻接矩阵法定义 二、邻接矩阵法表示图 2.1 邻接矩阵法表示图的定义 2.2 邻接矩阵法表示图的示例 2.2....

  • 第三十节-图的表示

    邻接矩阵存储方法 图最直观的一种存储方法就是，邻接矩阵 (Adjacency Matrix)。邻接矩阵的底层依赖一...

  • 图的邻接表邻接矩阵创建

    一、邻接矩阵 1.1 邻接矩阵的定义 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V, E)是具有n个顶点的图，...

  • 数据结构课程 第十周 图

    定义和基本术语 案例引入 图的类型定义 图的存储结构 1数组（邻接矩阵）表示法 邻接矩阵的建立 邻接矩阵的优缺点 ...

  • 图的五种存储结构

    1.邻接矩阵 图的邻接矩阵（Adjacency Matrix）：图的邻接矩阵用两个数组来表示图。一个一维数组存储图...

  • 邻接矩阵及其实现

    通过图论学习，能将图之间的关系用矩阵来表示。 提前在文档里写好邻接矩阵。 输出邻接矩阵

  • 2019-10-24图论基础

    图的2种表示手段：邻接矩阵和邻接表邻接矩阵用一个数组存储所有结点的信息，用一个矩阵来代表边，适合稠密图邻接矩阵用链...

网友评论

      本文标题：关联矩阵与邻接矩阵 2018-11-27

      本文链接：https://www.haomeiwen.com/subject/ypenqqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|关联矩阵与邻接矩阵 2018-11-27|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！