本页使用了标题或全文手工转换

邻接矩阵

维基百科,自由的百科全书
(重定向自鄰接矩陣
跳到导航 跳到搜索

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

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

定义[编辑]

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

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

例子[编辑]

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]

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

传球问题[编辑]

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

其他解法[编辑]

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


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

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

它的立方遵循同样规律

总结起来为[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.