グラフの直積

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

$G$ $□$ $H$ の頂点集合は直積 $V$ $($ $G$ $) \times$ $V$ ( $H$ $)$ $で$ ある。
二つの頂点( 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 \times H$ という表記はグラフの直積を表すのによく使われてきましたが、現在ではグラフのテンソル積と呼ばれる別の構成によく使われています。正方形の記号は、2つの辺の直積から得られる4つの辺を視覚的に表すため、直積を表す直感的で明確な表記法となることを意図しています。^[1]

例

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

(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つの異なる方法で表現できる非連結グラフについて説明しています。

(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}),

ここで、プラス記号は互いに素な和を表し、上付き文字は直積のべき乗を表す。これは、

{\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}}

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

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

直積が二部積であるためには、その各因数が二部積でなければならない。より一般的には、直積の彩色数は次式を満たす。

\chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.

^[4]

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

\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)|\}.

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

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

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

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

辺の数 $| E (G □ H)|は$ $| V (G)|| E (H)| + | V (H)|| E (G)|$ に等しい。

代数的グラフ理論

代数的グラフ理論は、グラフ直積の解析に用いることができる。グラフが頂点を持ち隣接行列を持ち、グラフが頂点を持ち隣接行列を持つ場合、両グラフの直積の隣接行列は次のように与えられる。 $G_{1}$ $n_{1}$ $n_{1}\times n_{1}$ $\mathbf {A} _{1}$ $G_{2}$ $n_{2}$ $n_{2}\times n_{2}$ $\mathbf {A} _{2}$

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

、

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

カテゴリー理論

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

歴史

Imrich & Klavžar (2000) によると、グラフの直積は1912年にホワイトヘッドとラッセルによって定義されました。その後、Gert Sabidussi (1960) などによって繰り返し再発見されました。

注記

^ ハーン＆サビドゥッシ（1997年）。
^ サビドゥッシ（1960）；ヴィイジング（1963）。
^ Imrich & Klavžar (2000)、定理 4.19。
^ サビドゥッシ（1957年）。
^ Horvat & Pisanski (2010).
^ イムリッヒとペテリン (2007)。以前の多項式時間アルゴリズムについては、Feigenbaum、Hershberger & Schäffer (1985) および Aurenhammer、Hagauer & Imrich (1992) を参照してください。
^ Kaveh & Rahami (2005).
^ ウェーバー 2013より。

参考文献

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), Graph symmetry: algebraic methods and applications, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116, ISBN 978-0-7923-4668-5。
Horvat, Boris; Pisanski, Tomaž (2010)、「単位距離グラフの積」、Discrete Mathematics、310 (12): 1783– 1792、doi : 10.1016/j.disc.2009.11.035、MR 2610282。
イムリッチ、ウィルフリード；クラヴジャー、サンディ（2000年）、プロダクトグラフ：構造と認識、ワイリー、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、MR0209178。
ウェーバー、マーク（2013）「高次オペラド代数の自由積」、TAC、28（2）：24–65。

外部リンク

ワイスタイン、エリック・W.「グラフ直積」。MathWorld。

[FOOTNOTEHahnSabidussi1997-1] ハーン＆サビドゥッシ（1997年）。

[2] サビドゥッシ（1960）；ヴィイジング（1963）。

[3] Imrich & Klavžar (2000)、定理 4.19。

[FOOTNOTESabidussi1957-4] サビドゥッシ（1957年）。

[FOOTNOTEHorvatPisanski2010-5] Horvat & Pisanski (2010).

[6] イムリッヒとペテリン (2007)。以前の多項式時間アルゴリズムについては、Feigenbaum、Hershberger & Schäffer (1985) および Aurenhammer、Hagauer & Imrich (1992) を参照してください。

[FOOTNOTEKavehRahami2005-7] Kaveh & Rahami (2005).

[FOOTNOTEWeber2013-8] ウェーバー 2013より。