邻接矩阵

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

定义[编辑]

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

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

例子[编辑]

6n-graph2.svg

特性[编辑]

設圖的鄰接矩陣為

的元素表示由頂點到頂點長度為的徑的數目。[1]

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

传球问题[编辑]

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

其他解法[编辑]

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

参考资料[编辑]

  1. ^ 图论中邻接矩阵的应用. 
  2. ^ 2.0 2.1 传球问题的终极解法.