论文标题
图中的路径数
Number of paths in a graph
论文作者
论文摘要
简单无向图的邻接矩阵的$ k $ - 代表了节点对之间的长度$ k $的步行数。作为没有节点重复的步行，一条路径是步行，每个节点只访问一次。一组路径构成了所有可能步行的相对较小的子集。我们介绍了三种类型的步行，代表所有可能的步行的子集。所考虑的步行类型允许在节点对之间以矩阵形式的一定长度的路径数来得出一个分析解决方案。根据路径长度，不同的方法具有最低的计算复杂性。我们还提出了一种用于确定图中所有路径的递归算法，该算法可以推广到定向（未加权网络）。
The $k$-th power of the adjacency matrix of a simple undirected graph represents the number of walks with length $k$ between pairs of nodes. As a walk where no node repeats, a path is a walk where each node is only visited once. The set of paths constitutes a relatively small subset of all possible walks. We introduce three types of walks, representing subsets of all possible walks. Considered types of walks allow for deriving an analytic solution for the number of paths of a certain length between node pairs in a matrix form. Depending on the path length, different approaches possess the lowest computational complexity. We also propose a recursive algorithm for determining all paths in a graph, which can be generalised to directed (un)weighted networks.
