主題
Search

圖的笛卡爾積

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
GraphProduct

笛卡爾圖積 G=G_1 square G_2，也稱為圖盒積，有時簡稱為“圖”積（Beineke 和 Wilson 2004, p. 104），有時表示為 G_1×G_2（例如，Salazar 和 Ugalde 2004；儘管此符號更常用於不同的圖張量積），對於具有不相交點集 V_1 和 V_2 以及邊集 X_1 和 X_2 的圖 G_1 和 G_2 而言，是點集為 V_1×V_2 的圖，且 u=(u_1,u_2) 與 v=(v_1,v_2) 相鄰當且僅當 [u_1=v_1 and u_2 adj v_2] 或 [u_2=v_2 and u_1 adj v_1] （Harary 1994, p. 22）。

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

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

其中 tensor 表示 克羅內克積（Hammack等人 2016）。

圖的笛卡爾積可以使用 Wolfram 語言 計算，方法是GraphProduct[G1, G2,"Cartesian"].

如果 G 是單位距離圖，那麼 G square K_2 也是。更一般地，G 的圖維度和 G square K_2 的圖維度之間存在簡單的關係（Erdős等人 1965, Buckley 和 Harary 1988）。

下表給出了一些圖笛卡爾積的示例。這裡，C_n 表示圈圖，K_n 表示完全圖，P_n 表示路徑圖，S_n 表示星圖。

積結果
P_m square P_n網格圖 G_(m,n)
P_m square P_2梯形圖 L_m
P_l square P_m square P_n網格圖 G_(l,m,n)
C_m square P_2稜柱圖 Y_m
C_m square P_n堆疊稜柱圖 Y_(m,n)
C_m square C_n環面網格圖 T_(m,n)
C_m square C_n 其中 (m,n)=1迴圈圖 Ci_(mn)(m,n)
S_(m+1) square P_2書圖
S_(m+1) square P_n堆疊書圖
K_2 square K_n^_皇冠圖
K_n square C_rKC 圖
K_n square P_rKP 圖
K_m square K_nm×n 車圖
K_m square K_n^_m×n 車補圖
P_2 square ... square P_2_()_(n)超立方體圖 Q_n

另請參閱

書圖, 迴圈圖, 皇冠圖, 圖的組合, 圖的維度, 圖的積, 網格圖, KC 圖, KP 圖, 梯形圖, 中值圖, 稜柱圖, 車補圖, 車圖, 堆疊書圖, 環面網格圖, 單位距離圖, Vizing 猜想

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

使用 探索

參考文獻

Buckley, F. 和 Harary, F. "論輪的歐幾里得維度。" Graphs and Combin. 4, 23-30, 1988.Beineke, L. W. 和 Wilson, R. J. (編). 代數圖論主題。 紐約: Cambridge University Press, p. 104, 2004.Clark, W. E. 和 Suen, S. "與 Vizing 猜想相關的不等式。" Electronic J. Combinatorics 7, No. 1, N4, 1-3, 2000. http://www.combinatorics.org/Volume_7/Abstracts/v7i1n4.html.Erdős, P.; Harary, F.; 和 Tutte, W. T. "論圖的維度。" Mathematika 12, 118-122, 1965.Hammack, R.; Imrich, W.; 和 Klavžar, S. 圖積手冊，第二版。 Boca Raton, FL: CRC Press, 2016.Harary, F. 圖論。 Reading, MA: Addison-Wesley, 1994.Hartnell, B. 和 Rall, D. "笛卡爾積中的支配：Vizing 猜想。" 在 圖的支配--高階主題 (編. T. W. Haynes, S. T. Hedetniemi, 和 P. J. Slater). 紐約: Dekker, pp. 163-189, 1998.Imrich, W. "Mengensystemen 和 Graphen 的 Kartesisches Produkt。" Studia Sci. Math. Hungar. 2, 285-290, 1967.Imrich, W.; Klavzar, S.; 和 Rall, D. F. 圖及其笛卡爾積。 Wellesley, MA: A K Peters, 2008.Sabidussi, G. "圖乘法。" Math. Z. 72, 446-457, 1960.Salazar, G. 和 Ugalde, E. "C_m×C_n 的交叉數的改進界限：主要使用組合論證的自包含證明。" Graphs Combin. 20, 247-253, 2004.Skiena, S. "圖的積。" §4.1.4 在 實現離散數學：Mathematica 的組合學和圖論。 Reading, MA: Addison-Wesley, pp. 133-135, 1990.Vizing, V. G. "圖的笛卡爾積。" Vyčisl. Sistemy 9, 30-43, 1963.

在 中被引用

圖的笛卡爾積

請這樣引用

Sauras-Altuzarra, Lorenzo 和 Weisstein, Eric W. "圖的笛卡爾積。" 來自 Web 資源。 https://mathworld.tw/GraphCartesianProduct.html

主題分類