邻接矩阵

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

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

定义

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

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

例子

$\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$的徑的數目。

$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. $(m-1)P_{n+1}=1-P_{n},P_n=\frac{1}{m}(1-(\frac{-1}{m-1})^{n-1})$，将P_n乘上总传法数$(m-1)^{n-1}$