邻接矩阵与关联矩阵「建议收藏」

邻接矩阵与关联矩阵「建议收藏」【邻接矩阵】定义:设无向图G=(V,E)G=(V,E)G=(V,E),其中顶点集V=v1,v2,…,vnV=v1,v2,…,vnV={v_1,v_2,…,v_n},边集E=e1,e2,…,eεE=e1,e2,…,eεE={e_1,e_2,…,e_\varepsilon}。用aijaija_{ij}表示顶点viviv_i与顶点vjvjv_j之间的边数,可能取值为0,1…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

【邻接矩阵】

定义:
设无向图 G=(V,E) G = ( V , E ) ,其中顶点集 V=v1,v2,...,vn V = v 1 , v 2 , . . . , v n ,边集 E=e1,e2,...,eε E = e 1 , e 2 , . . . , e ε 。用 aij a i j 表示顶点 vi v i 与顶点 vj v j 之间的边数,可能取值为0,1,2,…,称所得矩阵 A=A(G)=(aij)n×n A = A ( G ) = ( a i j ) n × n 为图G的邻接矩阵

若干性质

  • A(G) A ( G ) 为对称矩阵
  • 若G为无环图,则 A(G) A ( G ) 中第i行(列)的元素之和等于顶点 vi v i 的度
  • 两图G和H同构的充要条件是存在置换矩阵P使得 A(G)=PTA(H)P A ( G ) = P T A ( H ) P

类似地,有向图D的邻接矩阵 A(D)=(aij)n×n A ( D ) = ( a i j ) n × n , aij a i j 表示从始点 vi v i 到终点 vj v j 的有向边的条数,其中 vi v i vj v j 为D的顶点

示例,求图所示简单图的邻接矩阵?
这里写图片描述

解:根据定义,可求得该无向图的邻接矩阵为

0111101011011010 [ 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 ]

注:邻接矩阵是描述图的一种常用的矩阵表示。

【关联矩阵】

定义:
设任意图 G=(V,E) G = ( V , E ) ,其中顶点集 V=v1,v2,...,vn V = v 1 , v 2 , . . . , v n ,边集 E=e1,e2,...,eε E = e 1 , e 2 , . . . , e ε 。用 mij m i j 表示顶点 vi v i 与边 ej e j 关联的次数,可能取值为0,1,2,…,称所得矩阵 M(G)=(mij)n×ε M ( G ) = ( m i j ) n × ε 为图G的关联矩阵

类似地,有向图 D D 的关联矩阵
M(D)=(mij)n×ε



M



(


D


)


=


(



m



i


j





)



n


×


ε



的元素 mi×j m i × j 定义为:

mij=1,1,0,viajviajviaj m i j = { 1 , v i 是 有 向 边 a j 的 始 点 − 1 , v i 是 有 向 边 a j 的 终 点 0 , v i 是 有 向 边 a j 的 不 关 联 点

示例,求图中有向图的邻接矩阵和关联矩阵。
这里写图片描述

解:根据定义,可求得该有向图的邻接矩阵:

0001101010000010 [ 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 ]

关联矩阵:

11000110001110011010 [ 1 0 0 − 1 1 − 1 − 1 0 0 0 0 1 1 0 − 1 0 0 − 1 1 0 ]

注:关联矩阵是描述图的另一种矩阵表示。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/222914.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • a4纸两版的小册子怎么打印_word怎么打印小册子用a4

    a4纸两版的小册子怎么打印_word怎么打印小册子用a4用word打印小册子具体操作步骤:1、首先打开将要打印的文档,然后在菜单栏下面的快捷菜单栏,找到打印机的快捷图标,单击鼠标左键选择打开打印机。2、会弹出打印机设置对话框,可以进行打印前的一些细节的设置,由于是要选择打印一本小册子所以选择打印“所有页面”。3、在下面一栏是调整页面大小,也就是打印模式,选择“小册子”进行打印。4、然后下面是关于小册子的一些设置,按照自己的需要进行设置。5、设置完成以后…

  • ODI性能问题

    ODI性能问题

  • 单射、双射与满射[通俗易懂]

    单射、双射与满射[通俗易懂]数学上,单射、满射和双射指根据其定义域和陪域的关联方式所区分的三类函数。单射:指将不同的变量映射到不同的值的函数。满射:指陪域等于值域的函数。即:对陪域中任意元素,都存在至少一个定义域中的元素与之对应。双射(也称一一对应):既是单射又是满射的函数。直观地说,一个双射函数形成一个对应,并且每一个输入值都有正好一个输出值以及每一个输出值都有正好一个输入值。(在一些参考书中,“一一”用…

  • c语言return x_没有return

    c语言return x_没有returnint GetX() const;int 表示函数返回值为复int型;()为空表示该函数不需要参数制;const 表示该函数不修改百任何值;加起来就是:定义一个返回值类型为度 int 参数为void 名为GetX 的常知函数;类的常对象只道能调用这种常成员函数。const修饰知变量的时候,表示该变量是常量,也就是不可以改变的变量。当const放在成员函道数”尾巴”上修饰成员函数时,则…

  • 惯性矩阵计算

    惯性矩阵计算

  • Xray扫描器使用联动 burp,以及结合 fofa 批量自动化挖洞「建议收藏」

    Xray扫描器使用联动 burp,以及结合 fofa 批量自动化挖洞「建议收藏」xray简介xray(https://github.com/chaitin/xray)是从长亭洞鉴核心引擎中提取出的社区版漏洞扫描神器,支持主动、被动多种扫描方式,自备盲打平台、可以灵活定义POC,功能丰富,调用简单,支持Windows/macOS/Linux多种操作系统,可以满足广大安全从业者的自动化Web漏洞探测需求。特点xray为单文件二进制文件,无依赖,也无需安装,下载后直接使用使用go语言编写,跨平台、纯异步、无阻塞,并发能力强,扫描速度刚刚的提供多种使用

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号