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

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

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

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

切断されたサブグラフの数が不明なグラフがあります。それらすべてを見つけるための良いアルゴリズム（またはJavaライブラリ）は何ですか？

疑似コードで、グラフから固定サイズのすべてのサブグラフを取得する方法は? （強引な）

可能であれば外部ライブラリなし。ありがとう！

のDOT言語でGraphViz、依存関係図を表現しようとしています。コンテナ内にノードを配置し、ノードやコンテナを他のノードやコンテナに依存させることができる必要があります。

subgraphコンテナを表すために使用しています。ノードのリンクは問題なく機能しますが、サブグラフを接続する方法がわかりません。

cluster_1以下のプログラムを考えると、矢印を使用して接続できる必要がありますが、cluster_2試したものはすべて、クラスターを接続する代わりに新しいノードを作成します。

サブグラフ同型はNP完全問題です。最も広く使用されているアルゴリズムは、Ullmanによって提案されたものです。

誰かが私にアルゴリズムを素人の言葉で説明してもらえますか？私は彼の上記の論文を読みましたが、あまり理解できませんでした。

この問題には他にどのようなアルゴリズムがありますか？

私は画像処理プロジェクトに取り組んでいます。

次の属性を持つグラフがあります。

• 無向
• 加重なし
• 各頂点には、最小で 2 つ、最大で 6 つのエッジが接続されています。
• 頂点数は < 100 になります
• グラフは静的であり、頂点/エッジを追加/削除または編集することはできません。

頂点のランダムなサブセット (少なくとも 2 つ) 間のパスを探しています。パスは、頂点を 1 回だけ通過する単純なパスにする必要があります。

私の最終的な目標は、ルートのセットを作成して、サブセット頂点の 1 つから開始し、他のサブセット頂点のいずれかに到達できるようにすることです。ルートをたどる場合、すべてのサブセット ノードを通過する必要はありません。

私が見つけたすべてのアルゴリズム (ダイクストラ、深さ優先検索など) は、2 つの頂点間のパスと最短パスを処理しているようです。

これらの頂点のサブセットを接続するすべてのパス (これらはサブグラフだと思います) を提供する既知のアルゴリズムはありますか?

編集：

私が達成しようとしていることを説明するために、(警告! プログラマー アート) アニメーション GIF を作成しました: http://imgur.com/mGVlX.gif

前処理と実行時の 2 つの段階があります。

前処理

1. グラフと頂点のサブセット (青いノード) があります。
2. すべての青いノードを接続するすべての可能なルートを生成します

ランタイム

1. 任意の青いノードから開始して、生成されたルートのいずれかを選択し、それに沿って移動して目的の青いノードに到達できます。

したがって、私のタスクは、A->B からのパスを作成するのではなく、すべての青いノードを接続するすべてのサブグラフ (ルート) を作成することです。

グラフ内のすべての完全なサブグラフを見つけるための既知のアルゴリズムまたは方法はありますか? 無向で加重されていないグラフがあり、サブグラフ内の各ノードがサブグラフ内の他のノードに接続されているすべてのサブグラフを見つける必要があります。

このための既存のアルゴリズムはありますか?

重み付けされていない接続グラフがあります。特定のノード セットを確実に含み、エクストラをできるだけ少なくした、接続されたサブグラフを見つけたいと考えています。これはどのように達成できますか？

念のため、より正確な言葉を使用して質問を言い直します。G(V,E) を無向、無向、連結グラフとします。N を V の部分集合とします。N が V' の部分集合となるような G(V,E) の最小連結部分グラフ G'(V',E') を見つける最良の方法は何ですか?

近似は問題ありません。

この画像に示すように、ノード（またはノードを囲むサブグラフ-可能な/簡単な方）を回転させようとしています：

（「B」ラベルがローテーションされているかどうかは関係ありません。レコード内の「verti- *」テキスト[つまり、レコードノード全体]が図のようにローテーションされているだけです）

ただし、それに最も近いのは次のdotコードです。

私がsubgraph clusterSubRotateBoxそこにいる唯一の理由（そしてそれが内部にネストされている唯一の理由clusterMasterBox）は、回転を割り当てることができることを望んでいたためですが、明らかにできません-上記のコードがこの画像を生成するため：

だから私の質問は-レコードノードをローテーションする方法はありますか？それ自体ではない場合、おそらくサブグラフ（または別の種類の「オブジェクト」）の一部としてですか？

よろしくお願いします、
乾杯！