主题
Search

图的平方

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

图的平方定义为其二阶图的幂。

任何双连通图的平方都是哈密顿图（Fleischner 1974, Skiena 1990, p. 231）。Mukhopadhyay (1967) 曾考虑过“平方根图”，其平方给出了给定的图 G (Skiena 1990, p. 253)。

由于将任何图提升到其图直径的幂都会得到一个完全图，因此任何在 n 个节点上且图直径 <=2 的图的平方都是一个完全图 K_n。这类图包括 鸡尾酒会图、完全图、完全二部图、完全三部图、双锥图、星图 和 轮图。

下表总结了一些索引图族的平方。

图 G图的平方 G^2
反棱柱图 Ci_(2n)(1,2)循环图 Ci_(2n)(1,2,3,4)
圈图 C_n循环图 Ci_n(1,2)
空图 K^__n空图 K^__n
超立方体图 Q_n半立方体图 Q_(n+1)/2
莫比乌斯梯图 M_n循环图 Ci_(2n)(1,2,n-1,n)

参见

图的立方, 图的幂, 图的积

使用 探索

参考文献

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.

请引用本文为

Weisstein, Eric W. "Graph Square." 来自 Web 资源。 https://mathworld.net.cn/GraphSquare.html

主题分类