圖形的強產物

在圖理論中，強產物是將兩個圖組合形成較大圖的一種方式。當相鄰或相同的因子圖中，兩個頂點來自強產物中的兩個頂點。強產物是圖理論中研究的幾種不同的圖產品操作之一。任何兩個圖的強產物都可以構建為同一兩個圖的其他兩個產品的結合，即笛卡爾的圖形和圖形的張量產物。

強大產品的一個例子是國王的圖，即棋盤上國際象棋王的動作圖，可以作為路徑圖的強產物構建。平面圖和相關圖類分解為強產品的分解已被用作中心工具，以證明有關這些圖的許多其他結果。

在文獻中遇到強產品術語時，應謹慎行事，因為它也被用來表示圖的張量產物。

定義和示例

圖G和H的強產物g h是一個圖，使得g⊠h的頂點集是笛卡爾產物v （ g ）× v （ h ） ;當且僅在以下情況時

u = v和u'與v'相鄰，或

u' = v' ， u與V相鄰，或

u與V相鄰， u'與V'相鄰。

它是笛卡爾產品和張量產品的結合。

例如，國王的圖是一個棋盤的正方形，其邊緣代表國際象棋王的可能動作，是兩個路徑圖的強產物。它的水平邊緣來自笛卡爾產品，其對角線邊緣來自相同兩條路徑的張量產物。這兩種邊緣共同構成了整個強產品。

屬性和應用

每個平面圖都是路徑強產物的子圖，最多六個。該結果已用於證明平面圖具有有限的隊列數，小的通用圖和簡潔的鄰接標記方案，以及有界的非競爭性色數和中心的色度數。可以在線性時間內找到該產品結構。除了平面圖外，這些結果的擴展已被證明用於有界屬的圖形，帶有禁止的小調的圖形，該圖是Apex圖，帶有任何禁止的小調和K-Planar圖的有界度圖。

任意兩個圖的強產物的集團數量等於兩個圖的集團數量的乘積。如果兩個圖都具有雙寬度，另外一個圖具有有限的程度，那麼他們的強產物也具有界限雙寬度。

葉子的功率是一棵樹，當樹上的距離在樹上以下時，將兩個葉子鄰接在樹的葉子上形成 。如果是一個 - 樹的葉子力量 ， 然後可以作為強大產品的子圖。 與 - vertex循環。該嵌入已用於識別葉子功率的識別算法。

7 vertex循環圖和4 Vertex完整圖的強產物， ，已被認為是10個染色雙翼型圖的一種可能性，該圖可以改善地球 - 月球問題上的已知界限。另一個建議的示例是通過從中刪除任何頂點獲得的圖表 。在這兩種情況下，這些圖中的頂點的數量是其最大獨立集的大小的9倍以上，這意味著它們的色數至少為10。但是，尚不清楚這些圖是否為Biplanar。