打开主菜单

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

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

定义编辑

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

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

例子编辑

例一编辑

 


例二编辑

 
典型的邻接矩阵

这个矩阵中每一行代表一个点,行a即为点a,每一列代表某一行的点所指向的点,矩阵的每一个(小格)表示一条边。图中的所有边(指向性的箭头)带有权值,通常约定权值为0的边为不存在的边。 如此图中的a指向b,箭头旁边的数字(边的权值)为2,在矩阵中表示为行a 列b为2。又如矩阵中行c 列b为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.