グラフ積

グラフ理論において、グラフ積はグラフ上の二項演算です。具体的には、2つのグラフG ₁とG ₂を取り、以下の性質を持つ グラフHを生成する演算です

• Hの頂点集合は直積V ( G1 )× V(G2)であり、_ここでV ( G1 )_とV ( G2 )は_それぞれG1と_G2の頂点集合で_ある。
• Hの2 つの頂点( a ₁、a ₂ )と( b ₁、b ₂ )が辺で接続される場合、G ₁のa ₁、b ₁とG ₂のa ₂、b ₂に関する条件が満たされます。

グラフ積によって、この条件が具体的に何であるかは異なります。これは常に、 G _nの頂点a _n、b _nが等しいか、または辺で接続されている かどうかに関するものです。

文献における特定のグラフ製品に関する用語と表記法は非常に多様です。以下はある程度標準的であると考えられるかもしれませんが、特に古いテキストでは、読者は特定の著者がグラフ製品にどのような定義を使用しているかを確認することをお勧めします。

より標準的な定義であっても、文献において自己ループの扱い方は必ずしも一貫しているわけではありません。積の辺数に関する以下の公式も、自己ループを含む場合、正しく適用できないことがあります。例えば、単一頂点の自己ループとそれ自身のテンソル積は、別の単一頂点の自己ループとそれ自身とのテンソル積であり、式から示唆される通りではありません。 ${\displaystyle E=1}$ ${\displaystyle E=2}$ ${\displaystyle E_{G\times H}=2E_{G}E_{H}}$

概要表

次の表は、最も一般的なグラフ積を示しています。 は「〜に辺で接続されている」ことを示し、 は隣接していないことを示します。は等号を許容しますが、はそれらが異なっていて隣接していない必要があることを意味します。ここにリストされている演算子記号は、特に古い論文では決して標準的ではありません ${\displaystyle \sim}$ ${\displaystyle \not \sim}$ ${\displaystyle \not \sim}$ ${\displaystyle \not \simeq}$

名前	の条件${\displaystyle (a_{1},a_{2})\sim (b_{1},b_{2})}$		辺の数${\displaystyle {\begin{array}{cc}v_{1}=\vert \mathrm {V} (G_{1})\vert &v_{2}=\vert \mathrm {V} (G_{2})\vert \\e_{1}=\vert \mathrm {E} (G_{1})\vert &e_{2}=\vert \mathrm {E} (G_{2})\vert \end{array}}}$	例
		略称は${\displaystyle a_{n}~{\text{rel}}~b_{n}}$ ${\displaystyle {\text{rel}}_{n}}$
デカルト積（ボックス積）${\displaystyle G_{1}\square G_{2}}$	${\displaystyle a_{1}=b_{1}~\land ~a_{2}\sim b_{2}}$ ${\displaystyle \lor}$ ${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}=b_{2}}$	${\displaystyle =_{1}~\sim _{2}}$ ${\displaystyle \lor}$ ${\displaystyle \sim_{1}~=_{2}}$	${\displaystyle v_{1}~e_{2}~+~e_{1}~v_{2}}$
テンソル積（クロネッカー積、カテゴリカル積）${\displaystyle G_{1}\times G_{2}}$	${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}}$	${\displaystyle \sim _{1}~\sim _{2}}$	${\displaystyle 2~e_{1}~e_{2}}$
強い商品（通常商品、AND商品）${\displaystyle G_{1}\boxtimes G_{2}}$ ${\displaystyle =(G_{1}\times G_{2})\cup (G_{1}\square G_{2})}$	${\displaystyle a_{1}=b_{1}~\land ~a_{2}\sim b_{2}}$ ${\displaystyle \lor}$ ${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}=b_{2}}$ ${\displaystyle \lor}$ ${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}}$	${\displaystyle =_{1}~\sim _{2}}$ ${\displaystyle \lor}$ ${\displaystyle \sim_{1}~=_{2}}$ ${\displaystyle \lor}$ ${\displaystyle \sim _{1}~\sim _{2}}$	${\displaystyle v_{1}~e_{2}~+~e_{1}~v_{2}~+~2~e_{1}~e_{2}}$
辞書式製品または${\displaystyle G_{1}\cdot G_{2}}$ ${\displaystyle G_{1}[G_{2}]}$	${\displaystyle a_{1}\sim b_{1}}$ ${\displaystyle \lor}$ ${\displaystyle a_{1}=b_{1}~\land ~a_{2}\sim b_{2}}$	${\displaystyle \sim_{1}}$ ${\displaystyle \lor}$ ${\displaystyle =_{1}~\sim _{2}}$	${\displaystyle v_{1}~e_{2}~+~e_{1}~v_{2}^{2}}$
共正規積（選言積、[ 1 ] OR積）または${\displaystyle G_{1}*G_{2}}$ ${\displaystyle G_{1}\or G_{2}}$ ${\displaystyle =G_{1}[G_{2}]\cup G_{2}[G_{1}]}$ ${\displaystyle ={\overline {\;{\overline {G_{1}}}\boxtimes {\overline {G_{2}}}\;}}}$	${\displaystyle a_{1}\sim b_{1}}$ ${\displaystyle \lor}$ ${\displaystyle a_{2}\sim b_{2}}$	${\displaystyle \sim_{1}}$ ${\displaystyle \lor}$ ${\displaystyle \sim _{2}}$	${\displaystyle v_{1}^{2}~e_{2}~+~e_{1}~v_{2}^{2}~-~2~e_{1}~e_{2}}$
モジュラー製品${\displaystyle G_{1}\diamond G_{2}}$ ${\displaystyle =(G_{1}\boxtimes G_{2})\cup ({\overline {G_{1}}}\times {\overline {G_{2}}})}$	${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}}$ ${\displaystyle \lor}$ ${\displaystyle a_{1}\not \simeq b_{1}~\land ~a_{2}\not \simeq b_{2}}$	${\displaystyle \sim _{1}~\sim _{2}}$ ${\displaystyle \lor}$ ${\displaystyle \not \simeq _{1}~\not \simeq _{2}}$
ルート製品	記事参照		${\displaystyle v_{1}~e_{2}~+~e_{1}}$
ジグザグ積	記事参照		記事参照	記事参照
置換積
準同型積[ 2 ] [ 4 ]${\displaystyle G_{1}\ltimes G_{2}}$	${\displaystyle a_{1}=b_{1}}$ ${\displaystyle \lor}$ ${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}\not \sim b_{2}}$	${\displaystyle =_{1}}$ ${\displaystyle \lor}$ ${\displaystyle \sim _{1}~\not \sim _{2}}$	${\displaystyle v_{1}v_{2}(v_{2}-1)/2+e_{1}(v_{2}^{2}-2e_{2})}$

一般に、グラフ積は、およびで表現できる の任意の条件によって決定されます。 ${\displaystyle (a_{1},a_{2})\sim (b_{1},b_{2})}$ ${\displaystyle a_{n}=b_{n}}$ ${\displaystyle a_{n}\sim b_{n}}$

記憶法

を2頂点（つまり1辺）の完全グラフとします。積グラフ、、は、演算子を表すグラフと全く同じように見えます。例えば、は4閉路（正方形）であり、は4頂点の完全グラフです ${\displaystyle K_{2}}$ ${\displaystyle K_{2}\square K_{2}}$ ${\displaystyle K_{2}\times K_{2}}$ ${\displaystyle K_{2}\boxtimes K_{2}}$ ${\displaystyle K_{2}\square K_{2}}$ ${\displaystyle K_{2}\boxtimes K_{2}}$

辞書式積の表記は、この積が可換ではないことを思い出させるものです。結果として得られるグラフは、 のすべての頂点を のコピーで置き換えたように見えます。 ${\displaystyle G_{1}[G_{2}]}$ ${\displaystyle G_{2}}$ ${\displaystyle G_{1}}$

参照

• グラフ操作

注記

1. グラフ積再考：誘導マッチングの厳密近似困難性、半順序次元など、Parinya Chalermsook、Bundit Laekhanukit、Danupon Nanongkai、2012年
2. Roberson, David E.; Mancinska, Laura ( 2012). 「量子プレイヤーのためのグラフ準同型性」. Journal of Combinatorial Theory, Series B. 118 : 228–267 . arXiv : 1212.1724 . doi : 10.1016/j.jctb.2015.12.009 .
3. Bačík, R.; Mahajan, S. (1995). 「半正定値計画法とそのNP問題への応用」.コンピューティングと組合せ論. コンピュータサイエンス講義ノート. 第959巻. p. 566. doi : 10.1007/BFb0030878 . ISBN 978-3-540-60216-3.
4. ^{[ 3 ]}の準同型積^{は、 [ 2 ]}の準同型積のグラフ補である

参考文献

• イムリッチ、ウィルフリード、クラヴジャー、サンディ（2000年）。『プロダクトグラフ：構造と認識』ワイリー。ISBN 978-0-471-37039-0.

• ワイスタイン、エリック・W. 「グラフ積」 MathWorld
• Weisstein, Eric W. 「グラフ直積」MathWorld。
• Weisstein, Eric W. 「グラフテンソル積」MathWorld。
• Weisstein, Eric W. 「グラフ強積」。MathWorld 。
• Weisstein, Eric W. 「グラフ辞書的積」。MathWorld 。