计算机科学

首页 > 计算机科学

邻接矩阵

2018-07-27 09:56:51     所属分类:数据结构

邻接矩阵是表示一个图的常用存储表示。它用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。

距离矩阵可算是邻接矩阵的扩充。

目录

  • 1 定义
  • 2 例子
  • 3 特性
  • 4 传球问题
    • 4.1 其他解法
  • 5 邻接矩阵的次方(自乘)
  • 6 参考资料

定义

阶为的图的邻接矩阵的。将的顶点标签为。若,否则

无向图的邻接矩阵是对称矩阵。

例子

6n-graph2.svg


A believable e.g.:




This is a typical adj matrix







这个矩阵中以row为每个点,column则为该点指向的点,分量不是1的时候这个指向性的箭头则带有weight. 如此图中的a指向b,即ROWa COLUMNb是2,则从点a指向点b,同时这个指向动作带有2这个weight.又如从c指向b点,矩阵中则为ROWc COLUMNb且在矩阵中的分量为6,则图中表现为从c指向b并带有6.

特性

设图的邻接矩阵为

的元素表示由顶点到顶点长度为的径的数目。[1]

没有有向圈当且仅当可逆。的元素表示由顶点到顶点的所有径的数目。因为:

传球问题

A、B、C、D四人传球6次,从A开始,最终回到A手里,有多少种传法?

其他解法

  1. m个人传n次球,[2]
  2. ,将Pn乘上总传法数[2]


邻接矩阵的次方(自乘)

对于一个典型的邻接矩阵如图而言 WHEN ADJACENCY MATRIX(DIRECTED GRAPH) MEET SQUARE 它的平方会导致多次的图像的指向.如图所示

它的立方遵循同样规律

总结起来为[3]


参考资料

  1. ^ 图论中邻接矩阵的应用. 
  2. ^ 2.0 2.1 传球问题的终极解法. 
  3. ^ gilbert strang. introduction to linear algebra fourth edition. wellesley-cambridge. 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/338637.html

上一篇:查找表
下一篇:树旋转
相关推荐