打开主菜单

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

距離矩陣可算是鄰接矩陣的擴充。

目录

定义编辑

階為 的圖 的鄰接矩陣  的。將 的頂點標籤為 。若  ,否則 

无向图的鄰接矩陣是對稱矩陣

例子编辑

 
 


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]

 沒有有向圈若且唯若 可逆。 的元素 表示由頂點 到頂點 的所有徑的數目。因為: [2]

传球问题编辑

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

 

其他解法编辑

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


鄰接矩陣的次方(自乘)编辑

对于一个典型的邻接矩阵如图而言   它的平方会导致多次的图像的指向.如图所示

它的立方遵循同样规律

总结起来为[4]


参考资料编辑

  1. ^ 图论中邻接矩阵的应用. 
  2. ^ Neumann series. Wikipedia. 2018-05-28 (英语). 
  3. ^ 3.0 3.1 传球问题的终极解法. 
  4. ^ gilbert strang. introduction to linear algebra fourth edition. wellesley-cambridge.