【问题求解II-HW1.C】新马走日

邻接矩阵是描述图的一种常见方法：$\text{ga}(i,j)=1$ 当且仅当图中点 $i,j$ 之间有边。它之所以被称为“矩阵”，是因为矩阵的乘法恰好可以用于描述图上的游走。

令 $A_k$ 为一个 $n$ 阶矩阵，其中 $A_k(i,j)$ 表示从点 $i$ 走 $k$ 步到点 $j$ 的方案数，那么我们可以发现 $A_0=I,A_1=\text{ga}$。更一般地，我们可以发现

$$ \forall p, q. A_{p+q}=A_p\cdot A_q $$

Proof: 考虑任意点对 $i,j$，从 $i$ 走 $p+q$ 步到 $j$ 可以被分解成两个阶段：

• 从 $i$ 走 $p$ 步到某一个节点 $k$。
• 从 $k$ 走 $q$ 步到 $j$。

因此我们可以枚举这个中间节点 $k$，再根据加法/乘法原理有如下递推式： $$ A_{p+q}(i,j)=\sum_{k=1}^n A_p(i,k)\cdot A_q(k,j) $$

容易发现这恰好是矩阵乘法的计算公式，从而原命题得证。$\square$

因此，$A_k=\text{ga}^k$。至于如何将原问题转化为一个图上的游走问题，想必你能够自己解决。