簡単そうに見えて、とても難しい

今日は、簡単そうに見えて、とても難しい問題に突き当たった。

「頂点数 n, 枝の本数 m のグラフで、multi edge があるかどうかを判断するのが O(m+n) でできるのか」

という問題である。multi edge とは、枝の両端が同じ頂点、つまり、並行している枝のことである。
たとえば、(a,b) で枝が a と b にあるとしたときに、
(1,4), (2,5), (3,4), (2,4), (2,5), (1,3), (1,5)
などとあったときには、(2,5) が２本あるので、 multi edge である。

最初は、頂点の番号でソートすれば簡単だと思ったのだが、それでは O(m+n) にならない。
O(m+n) なので、以下の２つは使えない。
1. ソート（ O(m log m) か O(n log n) となり、O(m+n) を超えてしまう。）
2. 頂点同士のペアで調べることができない (２重の for になって O(n^2) になるため。）

ソートできないと、配列中に同じ値が存在するかどうかを調べるのが線形時間でできるのかどうか解からない。(これが最大のネックになっていると思う)

論文には、multi edge の探索を内部的につかって、全体としてO(m+n) になる、と書いてあるので、これはO(m+n)になるはずなのであるが、さっぱり解からない。



今日は６時間ぐらいかけて、論文の２ページぐらい読み進んだ。
この論文、はたして読み終えることができるんだろうか？

読むのが遅くなっている理由として、必要な事項が足りないことが多すぎる、などがある。
たとえば、「頂点 v について成り立つ」とあるのに、「特定の条件を満たす v について成り立つ」という「特定の条件」が暗黙のうちにかかれていて、これを推測しないといけない。
あと、文章の内容とexampleの図があっていないので、それもどちらが正しいのかを推測しないといけない。

とりあえず、こつこつと読み進めよう。

今日の作業内容: 論文読み 6h
今日のBGM: マクロスF OST [1-2], FF12 OST [1-2]
今日のランチ: いろは 豚汁定食
明日の予測作業時間: 2h