グラフ積

グラフ理論において、グラフ積はグラフ上の二項演算です。具体的には、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 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}}$

• グラフ操作