問題タブ [isomorphism]

boost::isomorphism_mapを使用する場合はどのように指定すればよいadjacency_list<vecS, vecS, undirectedS>ですか?

私が完了しようとしているものはマークされてい?????????ます：

同形ではない 2 つのグラフ G1 と G2 があります。G1 の最小の変更で、G1 と G2 の両方のノードを持つように、新しいグラフ G1' を作成する必要があります。たとえば、G1 にノード n1 があり、3 つの接続ノード n11、n12、n13 があるとします。G2 の「対応する」ノード n2 に 5 つのノード n21、n22、n23、n24、n25 がある場合、G1' の n1' にも 5 つのノード n11'、n12'、n13'、n14'、n15' が必要です。G1 からコピーされた最初の 3 つのノードと、最後の 3 つの値を持つ 2 つの余分なノード。余分なノードから発生するツリーは、完全に新しく作成されるか、G2 に同等のノードがない (ある意味で「使い果たされた」わけではない) G1 からのいくつかの余分なノードで構成されます。

問題は、1) 開始点として最も適切なシードを見つけて、開始ビューが可能な限り類似するようにすることです。2) 追加ノード数を最小限に抑えて余分なノードからツリーを構築することです。

編集：

イラストを使ってこれをさらに説明しようと思います。グラフ理論に関する私の知識は非常に表面的なものです。

最小限のノード操作で、2 つの非同型ソース グラフのいずれかの形をとることができるグラフを取得したいと考えています。

上の例では、グラフ G' は G または H の 2 つの形式をとることができ、ある程度のノード シャッフルが行われます。

1) G にするために、すべてのオレンジ色のノードをその位置に保持します。点線のノードは、隣接するノードに「マージ」されます。したがって、B21' は A21 の値を持ち、同じ位置になります (対応するエッジをディゾルブします)。対 B31'-A31、B14'-A15、B25'-B23、A32'-A22、および A23'-A32 の場合も同様です。この構成では、グラフは G に完全に似ており、エッジが「突き出ている」ことはありません。

2) H と同形にするには、A11 と A12 は、A13 と A32 と A32' の値を A23 の値、A23' を A22 の値とします。点線のノードは、マージされた位置から「出てきます」。

問題は G' を見つけることです。準備ができたグラフ操作がないか、解決策が不可能かもしれませんが、近似と効率の程度でこれを達成するためのポインタは大歓迎です。

注意: 開始ノード A1 と B1 は任意です。問題の前半は、ビューができるだけ類似するようにこれらのノードを識別することです。