主題
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)。

參見

鄰接矩陣, 圖的立方, 圖的平方, 波薩定理, 西摩猜想

使用 探索

參考文獻

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. "圖的冪." 來自 Web 資源. https://mathworld.tw/GraphPower.html

學科分類