Strongly Connectedである有向加重グラフが与えられた場合。最大重みエッジと最小重みエッジの差が最小になるように、このグラフから強く接続されたサブグラフを見つける必要があります。
より明確にするために、エッジを削除した後もグラフが強く接続され、最大重みエッジと最小重みエッジの差が最小になるように、エッジを削除する必要があります。
次に例を示します。
最初の行は、このグラフの N ノードと M エッジの数です。次の M 行は、このグラフのエッジを表します。
3 6
1 2 8
2 3 32
3 1 16
1 3 81
3 2 243
2 1 27
選択された N ノード サブグラフにはエッジが含まれます。
1 2 8
2 3 32
3 1 16
最大重みエッジと最小重みエッジの差は、32 - 8 = 24 です。これは、すべての選択肢の中で最小です。
最適なソリューションを探しています。最大で3000 のノードと5000 のエッジがあります。