主題
Search

圖的強積

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

圖的強積，也稱為圖的與積或圖的正規積，是一種 圖的積，有多種表示方法 G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H, G·H (Alon, and Lubetzky 2006), 或 G*H (Beineke and Wilson 2004, p. 104) ，由鄰接關係 (g=g^' 且 hadjh^') 或 (gadjg^' 且 h=h^') 或 (gadjg^' 且 hadjh^') 定義。

換句話說，兩個圖 G_1 和 G_2 的圖的強積具有 頂點集 V(G_1)×V(G_2)，並且兩個不同的頂點 (v_1,v_2) 和 (u_1,u_2) 是連線的 當且僅當 它們在每個座標中相鄰或相等，即對於 i in {1,2}, 要麼 v_i=u_i 要麼 v_iu_i in E(G_i), 其中 E(G) 是 G 的 邊集。

令 A(G) 表示 鄰接矩陣，I_n 表示 n×n 單位矩陣，以及 |V(G)| 表示 G 的 頂點數，簡單圖 G 和 H 的圖的強積的鄰接矩陣由下式給出

A(G square H)=A(G) tensor I_(|V(H)|)+I_(|V(G)|) tensor A(H)+A(G) tensor A(H),

其中 tensor 表示 克羅內克積 (Hammack et al. 2016)。

圖的強積可以使用 Wolfram 語言 計算，使用GraphProduct[G1, G2,"Normal"].

圖的強積與稱為 圖的強度 的圖論性質無關。

另請參閱

圖的積, 圖的強度, 夏農容量

此條目部分內容由 Nicolas Bray 貢獻

此條目部分內容由 Lorenzo Sauras-Altuzarra 貢獻

使用 探索

參考文獻

Alon, N. and Lubetzky, E. "The Shannon Capacity of a Graph and the Independence Numbers of Its Powers." IEEE Trans. Inform. Th. 52, 2172-2176, 2006.Beineke, L. W. and Wilson, R. J. (Eds.). Topics in Algebraic Graph Theory. New York: Cambridge University Press, p. 104, 2004.Hammack, R.; Imrich, W.; and Klavžar, S. Handbook of Product Graphs, 2nd ed. Boca Raton, FL: CRC Press, 2016.

在 中引用

圖的強積

請引用為

Bray, Nicolas; Sauras-Altuzarra, Lorenzo; 和 Weisstein, Eric W. "Graph Strong Product." 來自 —— 資源。 https://mathworld.tw/GraphStrongProduct.html

主題分類