主題
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.tw/GraphSquare.html

主題分類