グラフの頂点のカバー - 同程度の頂点の混乱

Question

グラフの頂点のカバーの問題を解決するために、最大次数を持つ頂点vを選択し、その頂点を頂点のセットから削除し、上記の頂点とエッジを削除した後に同じ程度の複数の頂点がある場合、どの頂点が私の欲張りアルゴリズムで選択されますか？

オンラインで検索しようとしましたが、上記の問題の候補が見つかりませんでした。誰かが助けてくれたら。ありがとう

Answer 1

ネクタイは任意に破ることができます。たとえば、ランダムに選択することができます。アルゴリズムが決定論的である必要がある場合、頂点が格納されているデータ構造内で最初に出現する頂点を常に選択することができます。