グラフアルゴリズムの計算量 - 折りたたみを展開する

アルゴリズムの本を読んでいる。

いまいち良くわからない箇所があったので訳を載せておく。因みに、邦訳もあるのだが、わかりにくかった。原著でもよくわからない部分だったので、訳本の問題ではない。

該当箇所はグラフに関する探索アルゴリズムの実装に関する部分。幅優先探索とか深さ優先探索とかの箇所だ。

Many graph algorithms need to examine all edges incident to a given node v. In the adjacency matrix representation, doing this involves considering all other nodes w, and checking the matrix entry A[v, w] to see whether the edge (v, w) is present—and this takes O (n) time. In the worst case, v may have O(n) incident edges, in which case checking all these edges will take O(n) time regardless of the representation. But many graphs in practice have significantly fewer edges incident to most nodes, and so it would be good to be able to find all these incident edges more efficiently. 　*1
ざっくり訳すとこんな感じである。
多くのアルゴリズムでは、与えられた点vから伸びる辺を調べる。隣接行列表現では、すべての点wについて、行列A[v, w]を使って辺(v, w)があるかどうか調べる。そして、これは (vという1つの点について) O(n)時間かかる。最悪のケースでは、vはO(n)の辺を持っていて、この辺すべてを調べるのに O(n) 時間かかるのは(隣接行列といった特定の)表現に関係ない。しかし、実用的には多くのグラフは(最悪のケースである点がn本の辺を持つ場合より) 少ない辺の数を持っている。つまり、( (vという1つの点について) O(n)時間かかるアルゴリズムより)　効率のよくすべての辺を見つけられれば、ためになる。

まず、最初の O(n)のところでつまずいた。全部を調べる最悪のケースのO( $n^2$ )と勘違いしていたのだ。ここでは、ある1個の点vについての計算量なのでO(n)が正しい。

次に、

But many graphs in practice have significantly fewer edges incident to most nodes...

の所だが、何に対して significantly fewer edges なのかよくわからない。これは、*2最悪のケースである、点がn本の辺を持つ場合と比べてということである。

簡単なことを述べているだけなのだが、わかりづらかった。最後の、

it would be good to be able to find all these incident edges more efficiently

はどうもしっくりと訳せなかった。大体、効率よく辺を見つかられるアルゴリズムを見つけることは常に良いことだろうに。

*1:Kleinberg, Jon, and Eva Tardos. Algorithm design. Pearson Education India, 2006.

*2:次数が最大である