グラフ内のすべての頂点を、次数よりも小さい次数で見つける

Question

私は、グラフ内のすべての頂点のセットを、その次数よりも小さい次数で見つけるアルゴリズムを作成しようとしています。私の最初のアプローチは、各頂点の次数を見つけ、リストを調べて、各頂点の次数とその隣接の次数を比較することです。残念ながら、これは非常に時間がかかるようです。このセットを見つけるより効率的な方法はありますか？

Answer 1

おそらく「これは非常に時間がかかる可能性があります」と思われますが、それを見つけるより良い方法があります：-）

グラフを隣接リストとして保存したとします。探しているセットを見つけるには、必ずすべてのエッジを調べる必要があるため、アルゴリズムには＆＃937;（| E |）の下限があります。すべての頂点の次数を見つけるには時間O（| E |）がかかります（すべてのエッジを1回だけ見るため、別の証拠は＆＃8721; d（v）= 2 | E |という事実を使用することです）。各頂点の次数とすべての隣接点との比較にもO（| E |）時間しかかかりません（ここでも、各エッジに対して1回だけ比較を行います）。これは、アルゴリズムがO（| E |）時間（約2 | E |「ステップ」で実行されますが、CPU命令の正確な数は実装に依存します）であり、下限を満たします。したがって、「総当たり」アルゴリズムは、最悪の場合、本質的に（小さな定数まで）可能な限り高速であるため、これ以上最適化する価値はありません。

実際のアプリケーションでこれを実行していて、実際にアルゴリズムに時間がかかりすぎることがわかった場合は、プロファイラーを使用して最適化する部分を見つけます。アルゴリズムの第2フェーズを最適化することが重要であることはまったく明らかではありません。

Answer 2

1つのコメント-無向グラフで作業している場合（ブライアンR 。Bondy ）、頂点の次数がすべての隣接点の次数よりも低いと判断したら、そのプロパティを持たないため、隣接点をチェックする必要はありません。その知識を活用して、物事を助け、スピードアップすることを検討してください。

Answer 3

次のような無向グラフの貪欲なアプローチを想像します。

let Q = all nodes which haven't been checked (initialize all V)
let Q* = all nodes which satisfy the required condition (initialize to empty)
start with an arbitrary node, v in Q
while Q is not empty
    let minDeg be the minimum degree of all v's neighbors
    if degree(v) < minDeg
        add v to Q*
        remove all neighbors of v from Q
        remove v from Q
        set v = new arbitrary node, v in Q
    else
        remove v from Q
        set v = v's neighbor in Q of minimum degree

このアルゴリズムは、反復ごとに満足のいくノードを見つけるか、より低い次数の新しいノードをチェックしてグラフからノードを削除するため、わずかに効率的です。

最悪の場合、ブルートフォースアルゴリズムと同等になります。ただし、平均して、パフォーマンスは向上するはずです。