邻接矩阵

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

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

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

定义[编辑]

階為n的圖G的鄰接矩陣An \times n的。將G的頂點標籤為v_1,v_2,...,v_n。若(v_i,v_j) \in E(G)A_{ij}=1,否則A_{ij}=0

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

例子[编辑]

6n-graph2.svg
\begin{pmatrix}
1 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{pmatrix}.

特性[编辑]

設圖G的鄰接矩陣為A

A^n的元素A^n_{ij}表示由頂點i到頂點j長度為n的徑的數目。[1]

G沒有有向圈若且唯若I-A可逆。(I-A)^{-1}的元素ij表示由頂點i到頂點j的所有徑的數目。因為:(I-A)^{-1} = I + A + A^2 + A^3 + ...

传球问题[编辑]

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

A=\begin{pmatrix}
0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 \\
\end{pmatrix},
A^6=\begin{pmatrix}
183 & 182 & 182 & 182 \\
182 & 183 & 182 & 182 \\
182 & 182 & 183 & 182 \\
182 & 182 & 182 & 183 \\
\end{pmatrix}

其他解法[编辑]

  1. m个人传n次球,\sum_{i=1}^{[\frac{n}{2}]}(m-1)^i (m-2)^{n-2i} C_{n-1-i}^{i-1}[2]
  2. (m-1)P_{n+1}=1-P_{n},P_n=\frac{1}{m}(1-(\frac{-1}{m-1})^{n-1}),将Pn乘上总传法数(m-1)^{n-1}[2]

参考资料[编辑]

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