サブグラフ同型とサブグラフ単型の違いは何ですか？

StackOverflow https://stackoverflow.com/questions/459799

質問

私が取り組んだプロジェクトの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 。

他のヒント

単相。

あるグラフ（<！> quot; B <！> quot;）から別のグラフ（<！> quot; A <！> quot;）への単型は、BからAのサブグラフへの同型と同等です。

この例では、n個の頂点パス（<！> quot; chain <！> quot;）はn個の頂点サイクルに対して単相であると言っています。また、n + 1頂点サイクルに対して単相、またはkに対してn + kです。

無向グラフ準同型h：H-<！> gt; Gは、頂点上のhが単射関数である場合、単型であると言われます。グラフ準同型hはもちろんエッジをエッジにマッピングしますが、エッジh（v0）-h（v1）がHに反映されるという要件はありません。

有向グラフの場合も同様です。

ここでMathとCSの用語に矛盾があります。 数学から、2つの用語が得られます。

  1. サブグラフ同型： H =（VH、EH）とG =（V、E）をグラフにします。 f：VH <！>＃8594; Vは（u、v）<！>＃8712の場合、サブグラフ同型です。 EH、次に（f（u）、f（v））<！>＃8712; E. HはGのサブグラフと同型です

  2. 誘発サブグラフ同型： H =（VH、EH）とG =（V、E）をグラフにします。 f：VH <！>＃8594; Vは、（u、v）<！>＃8712の場合、誘導サブグラフ同型です。 EH、次に（f（u）、f（v））<！>＃8712; E.そして、（u、v）がEHの要素ではない場合、（f（u）、f（v））はEの要素ではありません。 Hは、Gの誘導部分グラフと同型です

http://theory.stanford.edu/~virgi/cs267/ Lecture1.pdf 。 これらは、<！> quot;グラフ理論の最初のコースで見つけたものと同等です。<！> quot;

これらは両方とも、グラフ間の単射準同型であり、グラフ単型とも呼ばれることに注意してください。

CS、特にサブグラフ同型問題への移行。私の理解する限り、サブグラフ同型アルゴリズムは、上から（2）を満たす関数が存在するかどうかを判断します。

グラフの単相一致（1）。

CSの定義はVF2アルゴリズムからのものであり、その使用がどれほど普及しているかはわかりません。プロジェクトの正しいアルゴリズムを検索している間は、まだ曖昧さがあり、すべてのプロジェクトが同じ定義を使用しているわけではないようです。

一粒の塩でこの回答を取得 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342 <！> amp; rep = rep1 <！> amp; type = pdf 導入部では、単形性をグラフとサブグラフの同型性とは別のものとしてリストしていますが、セクション2では、グラフとサブグラフの同型性を概念的に（1）と同じものとして定義しています。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top