グラフ積

グラフ理論において、グラフ積はグラフに対する二項演算である。具体的には、2つのグラフG1とG2_を入力として、以下の性質を持つグラフH_を生成する演算である。

• Hの頂点集合は、デカルト積V ( G ₁ ) × V ( G ₂ )であり、V ( G ₁ )とV ( G ₂ )はそれぞれG ₁とG ₂の頂点集合である。
• 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 a_{n}=b_{n}}$そして${\displaystyle a_{n}\sim b_{n}}$。

させて$\displaystyle K_{2}}$2 つの頂点 (つまり 1 つのエッジ) 上の完全グラフとする。積グラフ${\displaystyle K_{2}\square K_{2}}$、$\displaystyle K_{2}\times K_{2}}$、 そして$\displaystyle K_{2}\boxtimes K_{2}}$演算子を表すグラフとまったく同じように見える。たとえば、${\displaystyle K_{2}\square K_{2}}$は4サイクル（正方形）であり、$\displaystyle K_{2}\boxtimes K_{2}}$これは4つの頂点を持つ完全グラフです。

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

• グラフ操作

• ワイススタイン、エリック W. 「グラフ積」 . MathWorld .
• Weisstein, Eric W. 「グラフのデカルト積」 . MathWorld .
• Weisstein, Eric W. 「グラフテンソル積」 . MathWorld .
• Weisstein, Eric W. 「グラフの強い積」 . MathWorld .
• Weisstein, Eric W. 「グラフ辞書式積」 . MathWorld .