グラフのモジュラー積

グラフ理論において、グラフ $G$ と $H$ のモジュラー積は、 $G$ と $H を$ 組み合わせて形成されるグラフであり、部分グラフ同型性に応用されます。これは研究されてきた数種類のグラフ積のうちの 1 つであり、一般的には同じ頂点セット ( 2 つのグラフ $G$ と $Hの頂点$ セットの直積) を使用しますが、どの辺を含めるかを決定するルールが異なります。

意味

$G$ と $H$ のモジュラー積の頂点集合は直積 $V (G) \times V (H)$ である。任意の 2 つの頂点 $(u, v)$ と $(u', v')が$ $G$ と $H$ のモジュラー積において隣接しているのは、 $u が$ $u'$ と異なり、 $v が$ $v'$ と異なり、かつ次のいずれかの場合のみである。

$u は$ $u'$ と隣接しており、 $v は$ $v'$ と隣接している、または
$u は$ $u'$ と隣接しておらず、 $v は$ $v'$ と隣接していません。

部分グラフ同型性への応用

モジュラー積グラフのクリークは、 $G$ および $H$ の誘導部分グラフの同型性に対応します。したがって、モジュラー積グラフを使用すると、誘導部分グラフ同型の問題をグラフ内のクリークを見つける問題に簡約できます。具体的には、 $G$ と $H$ の両方の最大共通誘導部分グラフは、それらのモジュラー積の最大クリークに対応します。最大共通誘導部分グラフを見つける問題と最大クリークを見つける問題はどちらもNP 完全ですが、この簡約により、クリークを見つけるアルゴリズムを共通部分グラフの問題に適用できます。

参考文献

バロー、H.;バーストール、R. (1976)、「サブグラフ同型性、マッチング関係構造および最大クリーク」、情報処理レター、4 (4): 83–84、doi :10.1016/0020-0190(76)90049-1。
Levi, G. (1973)、「2つの有向グラフまたは無向グラフの最大共通部分グラフの導出に関する注記」、Calcolo、9 (4): 341–352、doi :10.1007/BF02575586。
Vizing, VG (1974)、「グラフの非密度を見つけるタスクへの同型性と同型性入口の問題の削減」、Proc. 3rd All-Union Conf. Problems of Theoretical Cybernetics、p. 124。