問題タブ [isomorphism]

私が取り組んできたプロジェクトの 1 つで、同型対単型の話題が出てきました。

ちょっとした背景: 私はグラフ理論の専門家ではなく、正式なトレーニングを受けていません。しかし、このトピックは化学において非常に重要です。化学者は、使用する構造検索システムで特定の種類のサブグラフ マッチングが行われることを期待しています。

ターゲット グラフ A に n 個のノードと m 個のエッジがある場合、化学者はクエリ グラフ B に n 個のノードと m-1 個のエッジがあるサブグラフの一致を受け入れます。唯一の要件は、B のすべてのエッジが A に存在する必要があることです。たとえば、6 つのノードの線形チェーンは、6 つのノードのサイクルと一致する必要があります。

この種のマッチング同形性または単形性はありますか? たぶん、まったく別の何か？

2 つの二分木が同形であるとはどういう意味ですか? 私はオンラインで探していましたが、明確な説明が見つからないようです。

私が理解している限りでは、2 本の木は同じ形であれば同形です。したがって、ノードに異なる値を含めることができる2つの同一のツリーを推測しています。

各ノードが任意の数の子ノードを持つことができる、順序付けられていない根付きツリーを使用する Java でコードを書いています。木 T と部分木 S が与えられた場合、S に一致する T 内のすべての部分木 (つまり、S に同型である T 内のすべての部分木) を見つけられるようにしたいと考えています。

T の部分木は、S のエッジが T のエッジにマッピングされるように S のノードを T のノードにマッピングできる場合、S に同形です。

ツリーに別のサブツリーが含まれているかどうかを確認する方法について以前の質問がありましたが、S に一致する T のすべてのサブツリーを検索できるようにしたいと考えています。さらに、 T の各一致の各ノードからS の対応するノード。

つまり、一致が見つかった場合、単純に S に一致するツリーがルート化されている T 内のノードへのポインターとしてではなく、ノードへのポインターのペアのリストのようなものとして一致を返す必要があります [ (T1,S1),(T2,S2),...(Tn,Sn)] であり、T1 は、サブツリー内のノード S1 にマップされる T 内のノードへのポインターです。

別の方法として、ツリー T とサブツリー S の各ノードには固有の整数識別子が関連付けられているため、単に値のペアのリストを返すこともできます。

例えば：

木 T が次のように与えられます。

サブツリー S は次のようになります。

次の一致のリストが返されます。

[(a,x),(b,y),(c,z)] [(b,x),(d,y),(e,z)]

一意の一致は、T と S のノード間のマッピングではなく、T のノードのセットによって決定されます。

したがって、次の一致：

[(a,x),(b, z ),(c, y )]

の複製と見なされます

[(a,x),(b, y ),(c, z )]

それらは T (a,b,c) からの同じノードのセットを持っているため、一致するもののうちの 1 つだけが返されます。

別の例として、ツリー T が与えられた場合:

部分木 S:

次の一致のリストが返されます。

[(a,x),(b,y),(c,z)] [(a,x),(b,y),(d,z)] [(a,x),(c,y) ,(d,z)]

誰でもこれを行う方法のサンプルコードを教えてもらえますか?

編集（Chris Kannonのコメントに関連して）：

誰かに答えをコーディングしてもらいたいと思っていますか? どこまで行きましたか？どんなコードを書きましたか？– クリス・カノン 1時間前

次のコードを実行すると、特定のサブツリーに一致するサブツリーがルート化されているツリー内のノードへのポインターのリスト (matchesList) が作成されます。ただし、同じノードをルートとする複数のサブツリーが存在する可能性があり、現在、各ノードは、そこにルートが設定されている一致の数に関係なく、matchesList に最大 1 回しか追加されません。

さらに、サブツリーのノードと元のツリーで見つかった一致のノードとの間で上記のマッピングを構築する方法がわかりません。

上記のコードは、次のすべてのサブグラフを見つけようとします。

一致するもの:

コードは、最初のツリーの最上位ノードと最初のツリーの 3 番目の子をルートとする一致があることを正常に検出します。ただし、実際には、1 つだけではなく、最上位ノードに根ざした 3 つの一致があります。さらに、コードはツリー内のノードとサブツリー内のノード間のマッピングを構築せず、これを行う方法がわかりません。

誰でもこれを行う方法についてアドバイスを提供できますか?

Python で UUID を作成するときは、次のようにします。

その UUID を、大文字のアルファベット AZ から文字 D、F、I、O、Q、および U を差し引いた文字列と、数字と文字「+」および「=」で構成される文字列にマップするにはどうすればよいでしょうか。つまり、整数または文字列から 32 個の (比較的 OCR に適した) 文字のセットへ:

これをセットと呼びますOCRf(OCR フレンドリーの場合)。

私は同形関数が欲しいです：

私の最初の考えは、uuid をベース 32 に変更するプロセスを経ることです。

ただし、この方法がこの変換を行うための最良かつ最速の方法であるかどうか、またはより簡単で高速な方法 (組み込み、よりスマートなアルゴリズム、または単に優れた方法など) があるかどうかを知りたいです。

ご意見をお寄せいただきありがとうございます。ありがとうございました。

大きな (数千ノード) 有向グラフGと、はるかに小さい (3-5 ノード) 有向グラフgがあるとします。Gにgの同型がいくつあるかを数えたいと思います。言い換えれば、G内の一意のノード セットがgに一致する数を知りたいのです。これはサブグラフ同型問題のインスタンスであり、したがって NP 完全であることを認識しています。ただし、 gが小さいと仮定すると、これを行うための合理的に効率的なアルゴリズムはありますか?

O（N）のツリー同型問題のコードはどこにありますか？ここで、Nはノードの数です。

2 つのラベル付きグラフ G と T があり、アルゴリズムは、G が T のサブグラフであり、メイン グラフ T とサブグラフ G の対応する頂点が同じラベルを持つべきかどうかを判断すると仮定します。

有向グラフで指定されたパターンに対応するセクションを検索するためのツール/アルゴリズムを見つけようとしています。

A->B->C または A<->B->C

私の検索の方向性を教えてください。

パターンマッチングのことです。指定されたパターンに一致するノードとエッジのすべてのグループを見つける必要があります

SmartClient 8.1 を使用しており、GET および PUT 操作に XML データ ソースを使用しています。

以下は、私が取得したデータのサンプルです。

値を更新してフォームを送信すると、SmartClient は次のデータを PUT ペイロードとして送信します。

PUT ペイロードでは、更新された値がグループ要素なしで (フラット化されて)、グループ内の古い値とともに送信されます。これらのグループ化された古い値は、ここでは必要ありません/望ましくありません。

なぜそれが起こっているのか、そしてこれらの値を PUT ペイロードから削除するにはどうすればよいのか、誰にもわかりますか?

これは DynamicForm.submit() と DynamicForm.saveData() と関係がありますか?

ここSmartClient フォーラムでこの質問をしましたが、まだ回答がありません。ここで誰かが私を助けてくれることを願っています。

誰かがグラフ同型のためのVF2アルゴリズムのステップを簡単な言葉で説明できますか？私はこのアルゴリズムを学んでいますが、実際の例がないと厳しいです。誰かが私を正しい方向に導くことができますか？ありがとうございました。