疎グラフと密グラフ

グラフはノードとエッジという２つのパラメータを持つ点が、グラフ構造に関するアルゴリズムの検討に影響する。ノードとエッジの数をそれぞれV,Eとすると、EがVに比べ比較的少ないグラフを疎グラフ(sparse graph)、EがVに比べ比較的多いグラフを密グラフ(dense graph)と呼ぶ。グラフに適用するアルゴリズムのステップ数が、疎グラフとステップ数がEとVの関数で表せたとすると、疎グラフと密グラフでその効率の評価が分かれることがある。グラフの疎密の基準として、 を疎グラフ、 を密グラフとすれば、たとえば、ステップのアルゴリズムとステップのアルゴリズムがあるとき、疎グラフには が早いが、密グラフでは が早い。