グラフを作ってみましょう。エッジを削除すると、エッジの各頂点から1つずつ、2つの「車」が作成されます。これらの2台の車が出会うと停止します。問題は、各頂点を通過する車の数の合計が最小になるようにスパニングツリーを作成することです。
追加の難しさは、頂点からn台の車が通過する場合、コストはK ^ nであり、n*Kではないことです。
いくつかの考え。最短のコードレスサイクルを開始点として見つけることができましたが、それらのコードレスサイクルの位置、つまり、それらが互いに接触しているかどうかによって、メトリックが変化し、したがって最短サイクルが何であるかが変わります。
これは最小スパニングツリーの問題ではありません。各車は変数を表し、スパニングツリーは最適化問題を計算するための最も効率的な方法であるため、これを解決したいと思います。同じエッジから2台の車が出会って停止すると、最適化から1つの変数が削減されます。
編集：
プロセスはこのようなものです。グラフをスパニングツリーにするために、いくつかのエッジを削除します。削除された各エッジは、削除されたエッジの各頂点に1つずつ、2台の車を作成します。これらの車は互いに交わる必要があります。これらのツインカーのそれぞれのパスを修正します。次に、（削除したすべてのエッジから）各頂点を通過する車の数を確認します。頂点から通過する車の数がnの場合、コストはK ^ nです。ここで、Kは定数です。次に、すべてのコストを追加します。これは、最小化する必要があるグローバルコストです。
不明な点があれば教えてください。 https://mathoverflow.net/questions/86301/spanning-tree-that-minimizes-a-dynamic-metric