邻接矩阵

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

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

定义

階為$n$$n$的圖$G$$G$的鄰接矩陣$A$$A$是$n\times n$$n\times n$的。將$G$$G$的頂點標籤為$v_{1},v_{2},...,v_{n}$$v_{1},v_{2},...,v_{n}$。若$(v_{i},v_{j})\in E(G)$$(v_{i},v_{j})\in E(G)$，$A_{ij}=1$$A_{{ij}}=1$，否則$A_{ij}=0$$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}}.$${\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$$G$的鄰接矩陣為$A$$A$。

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

$G$$G$沒有有向圈若且唯若$I-A$$I-A$可逆。$(I-A)^{-1}$$(I-A)^{{-1}}$的元素$ij$$ij$表示由頂點$i$$i$到頂點$j$$j$的所有徑的數目。因為：$(I-A)^{-1}=I+A+A^{2}+A^{3}+...$$(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}}$$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}$$\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})$$(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}$$(m-1)^{{n-1}}$