私が取り組んできたプロジェクトの 1 つで、同型対単型の話題が出てきました。
ちょっとした背景: 私はグラフ理論の専門家ではなく、正式なトレーニングを受けていません。しかし、このトピックは化学において非常に重要です。化学者は、使用する構造検索システムで特定の種類のサブグラフ マッチングが行われることを期待しています。
ターゲット グラフ A に n 個のノードと m 個のエッジがある場合、化学者はクエリ グラフ B に n 個のノードと m-1 個のエッジがあるサブグラフの一致を受け入れます。唯一の要件は、B のすべてのエッジが A に存在する必要があることです。たとえば、6 つのノードの線形チェーンは、6 つのノードのサイクルと一致する必要があります。
この種のマッチング同形性または単形性はありますか? たぶん、まったく別の何か？
G1、G2 をそれぞれ頂点と辺 V1、V2 および E1、E2 の集合から構成されるグラフとします。
G2 は、V2 の各頂点と V1 の頂点の間、および E2 の各エッジと E1 のあるエッジの間に 1 対 1 の写像が存在する場合、G1 の部分グラフと同形です。したがって、同形であるためには、グラフがノード間に複数のエッジを含む場合を含め、完全に一致する必要があります。
G2 は、頂点間にそのようなマッピングがあり、V1 に対応するエッジがある V2 のすべての頂点間にエッジが存在する場合、モノモルフィックです。ただし、少なくとも 1 つのエッジが存在する限り、それで十分です。
これはcomp.lang.pythonからの素晴らしいパッケージの説明です。
単形性。
あるグラフ (「B」) から別のグラフ (「A」) への単型は、B から A のサブグラフへの同型と等価です。
この例は、任意の n 頂点パス (「チェーン」) が n 頂点サイクルに単形性であることを示しています。また、n+1 の頂点サイクル、または任意の k に対して n+k に対して単形性になります。
無向グラフ準同型 h: H -> G は、頂点上の h が単射関数であるとき、単型であると言われます。グラフ準同型 h はもちろんエッジをエッジにマッピングしますが、エッジ h(v0)-h(v1) が H に反映されている必要はありません。
有向グラフの場合も同様です。
ここで、数学用語と CS 用語の間に矛盾があります。数学から、次の 2 つの項が得られます。
subgraph isomorphism: H = (VH, EH) と G = (V, E) をグラフとする。f : VH → V は、(u, v) ∈ EH の場合、(f(u), f(v)) ∈ E の場合、部分グラフ同型です。H は、G の部分グラフに同型です。
誘導サブグラフ同型性: H = (VH, EH) および G = (V, E) をグラフとする。f : VH → V は、(u, v) ∈ EH の場合、誘導部分グラフ同型であり、(f(u), f(v)) ∈ E. そして、(u, v) が EH の要素ではなく、( f(u), f(v)) は E の元ではありません。H は G の誘導部分グラフと同型です。
http://theory.stanford.edu/~virgi/cs267/lecture1.pdfからの定義。それらは、「グラフ理論の最初のコース」で見つけたものと同等です。
これらは両方ともグラフ間の単射準同型、つまりグラフ単型であることに注意してください。
CS への移行、具体的にはサブグラフ同型問題。私の理解の限りでは、サブグラフ同型アルゴリズムは、上記の (2) を満たす関数が存在するかどうかを判断します。
グラフ単型性は (1) に一致します。
CS の定義は VF2 アルゴリズムからのものですが、その使用法がどれほど普及しているかはわかりません。プロジェクトの正しいアルゴリズムを探している間、まだあいまいさが残っており、すべてのプロジェクトが同じ定義を使用しているとは限りません。
この答えを一粒の塩で取ってください http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf は、単形性をグラフサブグラフ同形性とは別のものとして紹介していますが、セクション 2 では、グラフとサブグラフの同型を (1) と概念的に同一であると定義しています。これは、何かが欠けていることを示しています。