主题
Search

图的幂

下载 Mathematica 笔记本下载 Wolfram 笔记本
GraphPower

图 k 次幂是一个与图 G 具有相同顶点集的图，并且两个顶点之间存在边 当且仅当 它们之间存在长度至多为 k 的路径 (Skiena 1990, p. 229)。由于对于每个顶点 w，如果 {u,w} 和 {w,v} 是图 G 中的边，则在顶点 u 和 v 之间存在长度为 2 的路径，因此图 G 的邻接矩阵的平方计算了这种路径的数量。类似地，图 G 的邻接矩阵的 k 次幂的第 (u,v) 个元素给出了顶点 u 和 v 之间长度为 k 的路径的数量。图的幂在 Wolfram 语言中实现为GraphPower[g, k].

图的 k 次幂然后被定义为邻接矩阵由邻接矩阵的前 k 次幂之和给出的图，

adj(G^k)=sum_(i=1)^k[adj(G)]^i,

它计算了所有长度不超过 k 的路径 (Skiena 1990, p. 230)。

将任何图提升到其图直径的幂都会得到一个完全图。任何双连通图的平方都是哈密顿图 (Fleischner 1974, Skiena 1990, p. 231)。Mukhopadhyay (1967) 考虑了“平方根图”，其平方给出了给定的图 G (Skiena 1990, p. 253)。

参见

邻接矩阵, 图的立方, 图的平方, 波萨定理, 西摩猜想

使用 Wolfram|Alpha 探索

参考文献

Fleischner, H. "The Square of Every Two-Connected Graph Is Hamiltonian." J. Combin. Th. Ser. B 16, 29-34, 1974.Mukhopadhyay, A. "The Square Root of a Graph." J. Combin. Th. 2, 290-295, 1967.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

在 Wolfram|Alpha 上被引用

图的幂

请引用为

Weisstein, Eric W. "图的幂." 来自 MathWorld--Wolfram Web 资源. https://mathworld.net.cn/GraphPower.html

学科分类