主題
Search

圖乘積

一般來說，兩個圖 G 和 H 的圖乘積是一個新圖，其頂點集為 V(G)×V(H)，其中，對於乘積中的任意兩個頂點 (g,h) 和 (g^',h^')，這兩個頂點的鄰接性完全由 g 和 g^' 的鄰接性（或相等性，或非鄰接性）以及 h 和 h^' 的鄰接性決定。有 3×3-1=8 種情況需要決定（每個有三種可能性，其中兩者相等的情況被排除），因此可以定義 2^8=256 種不同型別的圖乘積。

最常用的圖乘積，由鄰接的充分必要條件給出，總結在下表中（Hartnell 和 Rall 1998）。請注意，術語並非完全標準化，因此這些乘積實際上可能被不同來源以不同的名稱提及（例如，圖字典序乘積也稱為圖組合；Harary 1994，第 21 頁）。在 Jensen 和 Toft (1994) 中可以找到許多其他圖乘積；另請參見 Hammack 等人 (2016)。

圖乘積可以使用 Wolfram 語言計算，使用GraphProduct[G, H, type]，其中術語"Normal"用於圖強乘積。

圖乘積名稱符號定義
圖笛卡爾積G square H(g=g^' 且 hadjh^') 或 (gadjg^' 且 h=h^'>)</td></tr><tr style=圖字典序積G-H(gadjg^') 或 (g=g^' 且 hadjh^'>)</td></tr><tr style=圖強積G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H(g=g^' 且 hadjh^') 或 (gadjg^' 且 h=h^') 或 (gadjg^' 且 hadjh^'>)</td></tr><tr style=圖張量積G×H(gadjg^' 且 hadjh^'>)</td></tr> </tbody></table> </div> </div> <!-- End Content --> <hr class=

另請參閱

圖笛卡爾積, 圖張量積, 圖組合, 圖日冕積, 圖字典序積, 圖冪, 圖強積, 圖和

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

使用 探索

參考文獻

Hammack, R.; Imrich, W.; 和 Klavžar, S. 圖乘積手冊，第二版。 Boca Raton, FL: CRC Press, 2016.Harary, F. 圖論。 Reading, MA: Addison-Wesley, 1994.Hartnell, B. 和 Rall, D. "笛卡爾積中的支配：維辛猜想。" 在 圖的支配--高階主題 (Ed. T. W. Haynes, S. T. Hedetniemi, 和 P. J. Slater). New York: Dekker, pp. 163-189, 1998.Imrich, W. 和 Klavžar, S. 圖乘積：結構與識別。 New York: Wiley, 2000.Imrich, W.; KlavĽorezar, S.; 和 Rall, D. F. 圖及其笛卡爾積。 Wellesley, MA: A K Peters, 2008.Jensen, T. R. 和 Toft, B. 圖著色問題。 New York: Wiley, 1994.

在 中被引用

圖乘積

請引用為

佈雷，尼古拉斯 和 韋斯坦因，埃裡克·W. "圖乘積。" 來自 —— 資源。 https://mathworld.tw/GraphProduct.html

主題分類