Trianguler

2014JOi夏季セミナー Looking for a challenge 班

Transcript

1. Looking for Challenge 小倉拳 @catupper
2. Looking for Challenge グラフ理論
3. 問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ
4. 問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ
5. 問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ • 一つ
6. 問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ • 二つ
7. 問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ • たくさん
8. Looking for Challenge グラフ理論 列挙
9. 第一の疑問 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を列挙せよ • 最大で何個くらいあるの？
10. 第一の補題 • 辺の数がMのグラフの中にある三角形の個数は たかだかM√(2M)個
11. 第一の補題 • 辺の数がMのグラフの中にある三角形の個数は たかだかM√(2M)個 • 証明しよう！ • 証明は2通り 1.バリバリのグラフ理論 2.不等式をこねる
12. 第一の補題 • 辺の数がMのグラフの中にある三角形の個数は たかだかM√(2M)個 • 証明しよう！ • 証明は2通り 1.バリバリのグラフ理論 2.不等式をこねる
13. Looking for Challenge グラフ理論 列挙
14. バリバリのグラフ理論 • 命題：辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ 　 　 　 　 　
15. バリバリのグラフ理論 • 命題：辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ – 次数の総和は2Mと一致する 　 　 　 　
16. バリバリのグラフ理論 • 命題：辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ – 次数の総和は2Mと一致する • 背理法で証明 – 全て次数が√(2M)以上と仮定 　 　
17. バリバリのグラフ理論 • 命題：辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ – 次数の総和は2Mと一致する • 背理法で証明 – 全て次数が√(2M)以上と仮定 – 頂点数は√(2M)を超える 　
18. バリバリのグラフ理論 • 命題：辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ – 次数の総和は2Mと一致する • 背理法で証明 – 全て次数が√(2M)以上と仮定 – 頂点数は√(2M)を超える – 次数の総和が2Mを超える
19. バリバリのグラフ理論 • グラフの中から最も次数が小さい頂点を選び、 それを含む三角形を列挙し、その頂点を消すと いう操作を考える – 隣接する辺も同時に消す 　　 　　　　　　　　　　　　　　　　　　　　　　　 　
20. バリバリのグラフ理論 • グラフの中から最も次数が小さい頂点を選び、 それを含む三角形を列挙し、その頂点を消すと いう操作を考える – 隣接する辺も同時に消す • これを全頂点がなくなるまで繰り返す – 全ての三角形を漏れなく、重複なく列挙することが できる
21. Looking for Challenge グラフ理論 列挙
22. バリバリのグラフ理論 • 辺に注目する • ある辺eが消えるタイミングを考える – その辺がつなぐ頂点のうちどちらかが消えるとき • vとする 　　　　　　　　　　　　　　　　　　　　　　　 　　 　 　　　　　
23. バリバリのグラフ理論 • 辺に注目する • ある辺eが消えるタイミングを考える – その辺がつなぐ頂点のうちどちらかが消えるとき • vとする – そのとき数えられる三角形の中でeを含むものはい くつあるか？ 　 　 　　　　　
24. バリバリのグラフ理論 • 辺に注目する • ある辺eが消えるタイミングを考える – その辺がつなぐ頂点のうちどちらかが消えるとき • vとする – そのとき数えられる三角形の中でeを含むものはい くつあるか？ – eでない辺のうち少なくともひとつはvに隣接する – よってたかだかeの次数しかない 　　　　　
25. バリバリのグラフ理論 • 辺に注目する • ある辺eが消えるタイミングを考える – その辺がつなぐ頂点のうちどちらかが消えるとき • vとする – そのとき数えられる三角形の中でeを含むものはい くつあるか？ – eでない辺のうち少なくともひとつはvに隣接する – よってたかだかeの次数しかない – 命題1よりたかだか√(2M)　　　　　　　　　　　 　　　　
26. バリバリのグラフ理論 • 例 • 赤い辺について考 える • 次数が4の頂点と共 に消えるとする
27. バリバリのグラフ理論 • 例 • 赤い辺について考 える • 次数が4の頂点と共 に消えるとする • この辺と頂点を含 む三角形はたかだ か4つ
28. バリバリのグラフ理論 • 辺は全部でM個なので数えられる三角形はたか だかM√(2M)個 • やったぜ
29. バリバリのグラフ理論 • 辺は全部でM個なので数えられる三角形はたか だかM√(2M)個 • やったぜ • 頭が痛くてなってつらい
30. 第一の補題 • 辺の数がMのグラフの中にある三角形の個数は たかだかM√(2M)個 • 証明しよう！ • 証明は2通り 1.バリバリのグラフ理論 2.不等式をこねる
31. 不等式をこねる • 次数がd[v]の頂点vを含む三角形はたかだか d[v]*d[v]/2個しかない – vに隣接する頂点から2つ選ぶ組み合わせ
32. 不等式をこねる • 辺の数がM個のグラフの頂点vを含む三角形は たかだかM個しかない – 頂点vとそれを含まない辺が与えられるとそれらを つかってたかだか1個しか三角形が作れない
33. 不等式をこねる • 辺がM個のグラフの次数がd[v]の頂点vを含む三 角形の個数はmin(d[v]*d[v]/2, M)個を超えない
34. 不等式をこねる • 辺がM個のグラフの次数がd[v]の頂点vを含む三 角形の個数はmin(d[v]*d[v]/2, M)個を超えない
35. 不等式をこねる • 辺がM個のグラフの次数がd[v]の頂点vを含む三 角形の個数はmin(d[v]*d[v]/2, M)個を超えない • 全頂点で総和を取る – 次数の総和は 2Mなので
36. 不等式をこねる • 辺がM個のグラフの次数がd[v]の頂点vを含む三 角形の個数はmin(d[v]*d[v]/2, M)個を超えない • やったぜ
37. 第一の疑問 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を列挙せよ • 最大で何個くらいあるの？ – M√(2M)個
38. 第二の疑問 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を列挙せよ • どうやって列挙する？
39. 実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ 　 　 　 　 　
40. 実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す 　 　 　 　
41. 実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す – それを含む三角形を全部列挙 　 　 　
42. 実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す – それを含む三角形を全部列挙 – その頂点を消す 　 　
43. 実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す – それを含む三角形を全部列挙 – その頂点を消す – 繰り返す 　
44. 実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す – それを含む三角形を全部列挙 – その頂点を消す – 繰り返す – やったぜ
45. 実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す　　　ならしO(1) – それを含む三角形を全部列挙　O(d[v]^2 logM) – その頂点を消す 　　　　　 ならしO(1) – 繰り返す – やったぜ？
46. 実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す　　　ならしO(1) – それを含む三角形を全部列挙　O(d[v]^2 logM) – その頂点を消す 　　　　　 ならしO(1) – 繰り返す – 全部でO(M√MlogM)で残念ながら遅い
47. どうすればよいのか?
48. もっとバリバリの グラフ理論をする
49. もっとバリバリのグラフ理論 • グラフの辺にループが出来ないように適当な向 きを付ける – DAGを作れば良い
50. もっとバリバリのグラフ理論 • グラフの辺にループが出来ないように適当な向 きを付ける – DAGを作れば良い • 三角形はすべてこの形になる
51. もっとバリバリのグラフ理論 • グラフの辺にループが出来ないように適当な向 きを付ける – DAGを作れば良い • 三角形はすべてこの形になる • ある辺について始点と終点から 同じ頂点に辺が出ている時 ちょうど1個三角形がある
52. もっとバリバリのグラフ理論 • グラフの辺にループが出来ないように適当な向 きを付ける – DAGを作れば良い • 三角形はすべてこの形になる • ある辺について始点と終点から 同じ頂点に辺が出ている時 ちょうど1個三角形がある • 重複や漏れはない
53. Looking for Challenge グラフ理論 列挙
54. もっとバリバリのグラフ理論 • 全ての辺について、その始点からも終点からも 点が出ている頂点を数え上げれば良い 　 　　　　　　　　　　　　　　　　　　　　　 　　　 　 　　　　　　　　　　　　　　　　　　　　　 　
55. もっとバリバリのグラフ理論 • 全ての辺について、その始点からも終点からも 辺が出ている頂点を数え上げれば良い • ここで計算量を考える • 各辺についてその終点と始点から共通して出て いる頂点はflagを使って調べれば良い 　 　　　　　　　　　　　　　　　　　　　　　 　
56. もっとバリバリのグラフ理論 • 全ての辺について、その始点からも終点からも 点が出ている頂点を数え上げれば良い • ここで計算量を考える • 各辺についてその終点と始点から共通して出て いる頂点はflagを使って調べれば良い • 計算量はmax(始点の出次数、終点の出次数) 　　　　　　　　　　　　　　　　　　　　　 　
57. もっとバリバリのグラフ理論 • 全ての辺について、その始点からも終点からも 点が出ている頂点を数え上げれば良い • ここで計算量を考える • 各辺についてその終点と始点から共通して出て いる頂点はflagを使って調べれば良い • 計算量はmax(始点の出次数、終点の出次数) • 出次数をおさえることに成功したら計算量が削 減される
58. もっとバリバリのグラフ理論 • どうやって出次数を削減しようか？
59. Looking for Challenge グラフ理論 列挙
60. ひらめきのLooking for Challenge • 元の無向グラフの頂点たちの次数を求める • 各辺には次数が小さい方から大きい方に向きを 付ける 　　　　　　　　　　　　　　　　　　　　　 　　 　
61. ひらめきのLooking for Challenge • 元の無向グラフの頂点たちの次数を求める • 各辺には次数が小さい方から大きい方に向きを 付ける • これでDAGになるので先ほどの数え上げが使え る
62. ひらめきのLooking for Challenge • 元の無向グラフの頂点たちの次数を求める • 各辺には次数が小さい方から大きい方に向きを 付ける • これでDAGになるので先ほどの数え上げが使え る • 出次数はどうなるだろうか？
63. ひらめきのLooking for Challenge • 命題1の証明を思い出す – 次数が√(2M)より大きい頂点は√(2M)個より少ない 　　　　　　　　　　　　　　　　　　　　　 　　　　　　 　　　　　　　　　　　　　　　　　　　　　 　
64. ひらめきのLooking for Challenge • 命題1の証明を思い出す – 次数が√(2M)より大きい頂点は√(2M)個より少ない • 次数が√(2M)より小さい頂点はどんなふうに向 きを付けても出次数は√(2M)を超えない 　　　　　　　　　　　　　　　　　　　　　 　　　　　 　
65. ひらめきのLooking for Challenge • 命題1の証明を思い出す – 次数が√(2M)より大きい頂点は√(2M)個より少ない • 次数が√(2M)より小さい頂点はどんなふうに向 きを付けても出次数は√(2M)を超えない • 次数が√(2M)より大きい頂点は自分より次数が 多い頂点にしか辺は出て行かない – √(2M)個もないので出自数は√(2M)を超えない
66. ひらめきのLooking for Challenge • 次数が√(2M)より小さい頂点はどんなふうに向 きを付けても出次数は√(2M)を超えない • 次数が√(2M)より大きい頂点は自分より次数が 多い頂点にしか辺は出て行かない – √(2M)個もないので出自数は√(2M)を超えない
67. ひらめきのLooking for Challenge • どの頂点も出次数が√(2M)を超えない！ • さきほどの考察より全計算量はM√2M • これは三角形の個数の最大値と一致するのでお およそ最適！ • やったぜ
68. テクニックまとめ • 辺の数がMの単純なグラフのなかで次数が最小 のものはO(√M) – 三角形の個数はO(M√M) • 次数が小さい方から大きい方に向きをつけると 全頂点の出次数をO(√M)に抑えられる。 • min(a, b) ≦ √(ab)
69. Looking for Challenge 小倉拳 @catupper
70. 今の発想を使う問題 • Algorithmic Engagements 2009　Round6 – Cakes • http://main.edu.pl/en/archive/pa/2009/cia • 面白いのでやってみてね！
71. クリックしてタイトルの挿入! ご清聴ありがとうございました