G = (V,E)次のように、貪欲にグラフのエッジに色を割り当てているとします。
- 無色のエッジ (u,v) を選択
- u に接するすべてのエッジの色を特定し、未使用の色のうち最も低い色を選択します。v についても同じことを行います。
- 2 つの色のうち大きい方を (u,v) に割り当てます。
1,2,...ステップ 2 を実行する簡単な方法は、エッジ タッチで使用されていない色に遭遇するまで、すべての色をチェックすることuです。もっと速い方法はありますか？
質問する
106 次