重み付けされたエッジを持つ 2 つの完全なグラフが与えられた場合、学習した 2 つの MST が特定のエッジのサブセットに共通のエッジを持つという制約の下で、2 つのグラフでそれぞれ 2 つの最小スパニング ツリー (MST) を見つけたいと思います。2 つのグラフの頂点の数は同じですが、辺の重みがすべて異なることに注意してください。
たとえば、2 つのグラフが頂点 {1,...,d} を持つ完全なエッジ加重グラフである場合。学習した 2 つの MST が、頂点 {1,...,d/2} を持つ完全なサブグラフ上で同じエッジを持っている必要があります。
そのような MST を見つけるためにどのアルゴリズムを使用できますか? Kruskal のアルゴリズムを修正したものを使用してみましたが、うまくいきませんでした。