🏷️ 知识点：长度为k的路径

矩阵A是有向图G的邻接矩阵，若矩阵(A^2)的某元素((A^2)_{ij}=3)，则说明()。

A. 从顶点i 到j 存在3条长度为2的路径 B. 从顶点i 到j存在3条长度不超过2的路径 C. 从顶点i 到j 存在2条长度为3的路径 D. 从顶点i 到j 存在2条长度不超过3的路径

[tag_link]

正确答案：A

结论

答案为 A：从顶点 i 到 j 恰有 3 条长度为 2 的路径。

推导

矩阵乘法中 ((A^2){ij}=\sum_k A{ik}A_{kj})，每个乘积对应经由中间顶点 k 的一条两步路径。

易错点

矩阵幂统计的是“恰好”长度，不是“不超过”长度；长度 3 也不能由 (A^2) 得出。