グラフの直積

グラフ理論では、グラフGとグラフH の直積 G □ Hは次のようなグラフです。

• G □ Hの頂点集合は直積V ( G ) × V ( H )である。
• 2つの頂点( u , v )と( u' , v' )がG □ H において隣接している場合、かつその 場合のみ、
  • u = u'かつv はH内でv'に隣接している、または
  • v = v'であり、 u はG内でu'に隣接しています。

グラフの直積はグラフのボックス積と呼ばれることもあります[Harary 1969]。

グラフ ( F □ G ) □ HとF □ ( G □ H )は自然に同型なので、この演算は結合的です。この演算はグラフの同型クラスに対する演算としては可換であり、さらに強くグラフG □ HとH □ G は自然に同型ですが、ラベル付きグラフに対する演算としては可換ではありません。

G × Hという表記はグラフの直積を表すのによく使われてきましたが、現在ではグラフのテンソル積と呼ばれる別の構成を表すのによく使われています。正方形の記号は、2つの辺の直積から得られる4つの辺を視覚的に示すため、直観的で明確な直積の表記法として意図されています。^[1]

• 2 つの辺の直積は4 つの頂点上のサイクルです: K ₂ □ K ₂ = C ₄。
• _{K 2}とパスグラフの直積はラダーグラフです。
• 2 つのパス グラフの直積はグリッド グラフです。
• n辺の直積は超立方体です。

${\displaystyle (K_{2})^{\square n}=Q_{n}.}$

したがって、2 つのハイパーキューブ グラフの直積は別のハイパーキューブ Q _i □ Q _j = Q _i+jになります。

• 2 つの中央値グラフの直積は、別の中央値グラフになります。
• n角柱の頂点と辺のグラフは、直積グラフ K ₂ □ C _nです。
• ルークのグラフは、 2 つの完全グラフの直積です。

連結グラフが直積である場合、グラフ自体をグラフの積として分解することができない素因数の積として一意に因数分解できます。^[2]しかし、Imrich & Klavžar (2000) は、素数グラフの直積として2つの異なる方法で表現できる切断されたグラフについて説明しています。

${\displaystyle (K_{1}+K_{2}+K_{2}^{2})\mathbin {\square } (K_{1}+K_{2}^{3})=(K_{1}+K_{2}^{2}+K_{2}^{4})\mathbin {\square } (K_{1}+K_{2}),}$

ここで、プラス記号は不連続和を表し、上付き文字は直積の累乗を表す。これは、

${\displaystyle {\begin{aligned}(1+x+x^{2})(1+x^{3})&=(1+x^{2}+x^{4})(1+x)\\&=1+x+x^{2}+x^{3}+x^{4}+x^{5}\\&=(1+x)(1+x+x^{2})(1-x+x^{2})\end{aligned}}}$

因子と は両方とも既約多項式ではありませんが、それらの因子には負の係数が含まれるため、対応するグラフは分解できません。この意味で、（おそらく切断されている）グラフ上で一意に因数分解できないことは、非負の整数係数を持つ多項式が一意に因数分解できない半環であるという主張に似ています。 ${\displaystyle 1+x^{3}}$${\displaystyle 1+x^{2}+x^{4}}$

デカルト積が頂点推移的であるためには、その各因子が頂点推移的である必要があります。^[3]

直積が二部積であるのは、その各因数が二部積である場合に限ります。より一般的には、直積の 彩色数は次の式を満たします。

${\displaystyle \chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.}$ ^[4]

ヘデトニエミ予想は、グラフのテンソル積に関する関連する等式を述べている。直積の独立数はそれほど簡単には計算できないが、Vizing (1963)が示したように、それは不等式を満たす。

${\displaystyle \alpha (G)\alpha (H)+\min\{|V(G)|-\alpha (G),|V(H)|-\alpha (H)\}\leq \alpha (G\mathbin {\square } H)\leq \min\{\alpha (G)|V(H)|,\alpha (H)|V(G)|\}.}$

ヴィジング予想は、直積の 支配数が不等式を満たすことを述べている。

${\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\gamma (H).}$

単位距離グラフの直積は別の単位距離グラフである。^[5]

デカルト積グラフは線形時間で効率的に認識できる。^[6]

代数グラフ理論は、直交グラフ積を解析するために使用できます。グラフに頂点と隣接行列があり、グラフに頂点と隣接行列がある場合、両方のグラフの直交積の隣接行列は次のように表されます。 ${\displaystyle G_{1}}$${\displaystyle n_{1}}$${\displaystyle n_{1}\times n_{1}}$ ${\displaystyle \mathbf {A} _{1}}$${\displaystyle G_{2}}$${\displaystyle n_{2}}$${\displaystyle n_{2}\times n_{2}}$${\displaystyle \mathbf {A} _{2}}$

${\displaystyle \mathbf {A} _{1\mathbin {\square } 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _ {n_{1}}\otimes \mathbf {A} _{2}}$、

ここで、は行列のクロネッカー積を表し、は単位行列を表します。^[7]したがって、直交グラフ積の隣接行列は、因子の隣接行列の クロネッカー和です。${\displaystyle \otimes }$${\displaystyle \mathbf {I} _{n}}$${\displaystyle n\times n}$

グラフを、頂点をオブジェクトとし、グラフ内のパスを射とするカテゴリとして見ると、グラフの直積はカテゴリの奇妙なテンソル積に対応する。グラフの直積は、グラフとグラフ準同型のカテゴリを対称 閉モノイドカテゴリ（単なる対称モノイドではなく）に変換する 2 つのグラフ積のうちの 1 つであり、もう 1 つはグラフのテンソル積である。^[8]グラフの直積の 内部 hom は、からへのグラフ準同型を頂点とし、それらの間の「不自然な変換」を辺とする。^[8]${\displaystyle [G,H]}$${\displaystyle G}$${\displaystyle H}$

Imrich & Klavžar (2000) によれば、グラフの直積は 1912 年にWhiteheadとRussellによって定義されました。その後、 Gert Sabidussi  (1960) などによって繰り返し再発見されました。

• Aurenhammer, F. ; Hagauer, J.; Imrich, W. (1992)、「Cartesian graph factorization at logarithmic cost per edge」、Computational Complexity、2 (4): 331–349、doi :10.1007/BF01200428、MR  1215316。
• ファイゲンバウム、ジョアン;ハーシュバーガー、ジョン; シェーファー、アレハンドロ A. (1985)、「直積グラフの素因数を求める多項式時間アルゴリズム」、離散応用数学、12 (2): 123–138、doi : 10.1016/0166-218X(85)90066-6、MR  0808453。
• Hahn, Geňa; Sabidussi, Gert (1997)、「グラフ対称性: 代数的手法と応用」、NATO Advanced Science Institutes Series、第 497 巻、Springer、p. 116、ISBN 978-0-7923-4668-5。
• Horvat, Boris; Pisanski, Tomaž (2010)、「単位距離グラフの積」、離散数学、310 (12): 1783–1792、doi : 10.1016/j.disc.2009.11.035、MR  2610282。
• イムリッチ、ウィルフリード、クラヴジャー、サンディ（2000）、プロダクトグラフ：構造と認識、Wiley、ISBN 0-471-37039-8。
• ヴィルフリート・イムリッヒ;クラヴジャール、サンディ。 Rall、Douglas F. (2008)、Graphs and their Cartesian Products、AK Peters、ISBN 1-56881-429-1。
• イムリッチ、ウィルフリード、ピーターイン、イズトク (2007)、「線形時間でのデカルト積の認識」、離散数学、307 (3–5): 472–483、doi : 10.1016/j.disc.2005.09.038、MR  2287488。
• Kaveh, A.; Rahami, H. (2005)、「グラフ積の固有値分解の統一手法」、Communications in Numerical Methods in Engineering with Biomedical Applications、21 (7): 377–388、doi :10.1002/cnm.753、MR  2151527。
• サビドゥッシ、G. (1957)、「与えられた群と与えられたグラフ理論的性質を持つグラフ」、カナダ数学ジャーナル、9 :515–525、doi :10.4153/CJM-1957-060-7、MR  0094810。
• Sabidussi, G. (1960)、「グラフ乗算」、数学ツァイツシュリフト、72 : 446–457、doi :10.1007/BF01162967、hdl : 10338.dmlcz/102459、MR  0209177。
• Vizing, VG (1963)、「グラフの直積」、Vycisl. Sistemy、9 :30–43、MR  0209178。
• ウェーバー、マーク（2013）「高次オペラド代数の自由積」、TAC、28（2）：24–65。

• Weisstein、Eric W.「グラフ直積」。MathWorld。