グラフの分散をエッジの重みの分散として定義しましょう。私が解決しようとしているタスクは、与えられたグラフ G が最小分散のスパニング ツリー T を構築するアルゴリズムを設計することです。
これでボールを転がすのに苦労しています。これまでのところ、このようなスパニング ツリーのエッジの平均重みがわかっている場合、すべてのエッジの重みを平均重みの偏差の 2 乗に置き換え、グラフを MST の結果に入力することで問題を解決できることに気付きました。アルゴリズム。
明らかに、構築しようとしているツリーの平均エッジの重みについては何も知りませんが、平均は G の 2 つのエッジの間にある必要があり、おそらくこの情報を利用できる可能性があることに気付きました。
私は修正された辺の重みで G の MST を見つけることに問題を軽減しようとしています。G の各エッジに対してアルゴリズムを実行することを考えました。毎回、最初のエッジが T の平均に最も近く、重み 0 が与えられていると仮定し、他のエッジは最初のエッジの重みからの偏差の 2 乗に等しい重みを取得します。 . 平均がエッジの 1 つの重みと等しくない場合、2 つの最も近いエッジの重みの間のどこにあるかに応じて、重みに基づくエッジの順序が異なり、異なるスパンが生成されるため、このアプローチはどこにも行きませんでした。 MST 発見アルゴリズムに供給されたときのツリー。これは、私が処理する方法がわからないものです (または、処理できるかどうかさえわかりません)。
これは宿題なので、解決策ではなく、正しい方向に導くための小さなヒントが欲しい.