Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Trianguler
Search
Catupper
August 29, 2014
Programming
0
190
Trianguler
2014JOi夏季セミナー Looking for a challenge 班
Catupper
August 29, 2014
Tweet
Share
More Decks by Catupper
See All by Catupper
ants' roots
catupper
1
2.4k
sort conference
catupper
2
99
計算量の話
catupper
0
1.1k
Graph is Fun
catupper
0
130
About累積和
catupper
0
1.6k
For You
catupper
1
150
Other Decks in Programming
See All in Programming
Devinのメモリ活用の学びを自社サービスにどう組み込むか?
itarutomy
0
1.7k
CTFのWebにおける⾼難易度問題について
hamayanhamayan
1
980
ニックトレイン登壇資料
ryotakurokawa
0
140
PHPのガベージコレクションを深掘りしよう
rinchoku
0
240
エンジニア未経験が最短で戦力になるためのTips
gokana
0
210
php-fpm がリクエスト処理する仕組みを追う / Tracing-How-php-fpm-Handles-Requests
shin1x1
5
830
PHPによる"非"構造化プログラミング入門 -本当に熱いスパゲティコードを求めて- #phperkaigi
o0h
PRO
0
1.1k
Windows版PHPのビルド手順とPHP 8.4における変更点
matsuo_atsushi
0
370
SLI/SLOの設定を進めるその前に アラート品質の改善に取り組んだ話
tanden
2
730
Go1.24で testing.B.Loopが爆誕
kuro_kurorrr
0
160
生産性アップのためのAI個人活用
kunoyasu
0
640
今から始めるCursor / Windsurf / Cline
kengo_hayano
0
110
Featured
See All Featured
Code Review Best Practice
trishagee
67
18k
Six Lessons from altMBA
skipperchong
27
3.7k
Writing Fast Ruby
sferik
628
61k
Building a Scalable Design System with Sketch
lauravandoore
462
33k
RailsConf 2023
tenderlove
29
1k
Into the Great Unknown - MozCon
thekraken
36
1.7k
Producing Creativity
orderedlist
PRO
344
40k
BBQ
matthewcrist
88
9.5k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
Optimising Largest Contentful Paint
csswizardry
35
3.2k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
Transcript
Looking for Challenge 小倉拳 @catupper
Looking for Challenge グラフ理論
問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ
問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ
問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ • 一つ
問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ • 二つ
問題 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を全て見つけよ • たくさん
Looking for Challenge グラフ理論 列挙
第一の疑問 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を列挙せよ • 最大で何個くらいあるの?
第一の補題 • 辺の数がMのグラフの中にある三角形の個数は たかだかM√(2M)個
第一の補題 • 辺の数がMのグラフの中にある三角形の個数は たかだかM√(2M)個 • 証明しよう! • 証明は2通り 1.バリバリのグラフ理論 2.不等式をこねる
第一の補題 • 辺の数がMのグラフの中にある三角形の個数は たかだかM√(2M)個 • 証明しよう! • 証明は2通り 1.バリバリのグラフ理論 2.不等式をこねる
Looking for Challenge グラフ理論 列挙
バリバリのグラフ理論 • 命題:辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓
バリバリのグラフ理論 • 命題:辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ – 次数の総和は2Mと一致する
バリバリのグラフ理論 • 命題:辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ – 次数の総和は2Mと一致する • 背理法で証明
– 全て次数が√(2M)以上と仮定
バリバリのグラフ理論 • 命題:辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ – 次数の総和は2Mと一致する • 背理法で証明
– 全て次数が√(2M)以上と仮定 – 頂点数は√(2M)を超える
バリバリのグラフ理論 • 命題:辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ – 次数の総和は2Mと一致する • 背理法で証明
– 全て次数が√(2M)以上と仮定 – 頂点数は√(2M)を超える – 次数の総和が2Mを超える
バリバリのグラフ理論 • グラフの中から最も次数が小さい頂点を選び、 それを含む三角形を列挙し、その頂点を消すと いう操作を考える – 隣接する辺も同時に消す
バリバリのグラフ理論 • グラフの中から最も次数が小さい頂点を選び、 それを含む三角形を列挙し、その頂点を消すと いう操作を考える – 隣接する辺も同時に消す • これを全頂点がなくなるまで繰り返す –
全ての三角形を漏れなく、重複なく列挙することが できる
Looking for Challenge グラフ理論 列挙
バリバリのグラフ理論 • 辺に注目する • ある辺eが消えるタイミングを考える – その辺がつなぐ頂点のうちどちらかが消えるとき • vとする
バリバリのグラフ理論 • 辺に注目する • ある辺eが消えるタイミングを考える – その辺がつなぐ頂点のうちどちらかが消えるとき • vとする –
そのとき数えられる三角形の中でeを含むものはい くつあるか?
バリバリのグラフ理論 • 辺に注目する • ある辺eが消えるタイミングを考える – その辺がつなぐ頂点のうちどちらかが消えるとき • vとする –
そのとき数えられる三角形の中でeを含むものはい くつあるか? – eでない辺のうち少なくともひとつはvに隣接する – よってたかだかeの次数しかない
バリバリのグラフ理論 • 辺に注目する • ある辺eが消えるタイミングを考える – その辺がつなぐ頂点のうちどちらかが消えるとき • vとする –
そのとき数えられる三角形の中でeを含むものはい くつあるか? – eでない辺のうち少なくともひとつはvに隣接する – よってたかだかeの次数しかない – 命題1よりたかだか√(2M)
バリバリのグラフ理論 • 例 • 赤い辺について考 える • 次数が4の頂点と共 に消えるとする
バリバリのグラフ理論 • 例 • 赤い辺について考 える • 次数が4の頂点と共 に消えるとする •
この辺と頂点を含 む三角形はたかだ か4つ
バリバリのグラフ理論 • 辺は全部でM個なので数えられる三角形はたか だかM√(2M)個 • やったぜ
バリバリのグラフ理論 • 辺は全部でM個なので数えられる三角形はたか だかM√(2M)個 • やったぜ • 頭が痛くてなってつらい
第一の補題 • 辺の数がMのグラフの中にある三角形の個数は たかだかM√(2M)個 • 証明しよう! • 証明は2通り 1.バリバリのグラフ理論 2.不等式をこねる
不等式をこねる • 次数がd[v]の頂点vを含む三角形はたかだか d[v]*d[v]/2個しかない – vに隣接する頂点から2つ選ぶ組み合わせ
不等式をこねる • 辺の数がM個のグラフの頂点vを含む三角形は たかだかM個しかない – 頂点vとそれを含まない辺が与えられるとそれらを つかってたかだか1個しか三角形が作れない
不等式をこねる • 辺がM個のグラフの次数がd[v]の頂点vを含む三 角形の個数はmin(d[v]*d[v]/2, M)個を超えない
不等式をこねる • 辺がM個のグラフの次数がd[v]の頂点vを含む三 角形の個数はmin(d[v]*d[v]/2, M)個を超えない
不等式をこねる • 辺がM個のグラフの次数がd[v]の頂点vを含む三 角形の個数はmin(d[v]*d[v]/2, M)個を超えない • 全頂点で総和を取る – 次数の総和は 2Mなので
不等式をこねる • 辺がM個のグラフの次数がd[v]の頂点vを含む三 角形の個数はmin(d[v]*d[v]/2, M)個を超えない • やったぜ
第一の疑問 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を列挙せよ • 最大で何個くらいあるの? – M√(2M)個
第二の疑問 • 頂点数がN、辺の数がMのグラフが与えられる • 互いに隣接している3頂点を列挙せよ • どうやって列挙する?
実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ
実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す
実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す – それを含む三角形を全部列挙
実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す – それを含む三角形を全部列挙 – その頂点を消す
実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す – それを含む三角形を全部列挙 – その頂点を消す
– 繰り返す
実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す – それを含む三角形を全部列挙 – その頂点を消す
– 繰り返す – やったぜ
実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す ならしO(1) – それを含む三角形を全部列挙 O(d[v]^2 logM) –
その頂点を消す ならしO(1) – 繰り返す – やったぜ?
実装の仕方 • 「バリバリのグラフ理論」の取り除くやつを実 際に実装するだけ – 次数が最小の頂点を探す ならしO(1) – それを含む三角形を全部列挙 O(d[v]^2 logM) –
その頂点を消す ならしO(1) – 繰り返す – 全部でO(M√MlogM)で残念ながら遅い
どうすればよいのか?
もっとバリバリの グラフ理論をする
もっとバリバリのグラフ理論 • グラフの辺にループが出来ないように適当な向 きを付ける – DAGを作れば良い
もっとバリバリのグラフ理論 • グラフの辺にループが出来ないように適当な向 きを付ける – DAGを作れば良い • 三角形はすべてこの形になる
もっとバリバリのグラフ理論 • グラフの辺にループが出来ないように適当な向 きを付ける – DAGを作れば良い • 三角形はすべてこの形になる • ある辺について始点と終点から
同じ頂点に辺が出ている時 ちょうど1個三角形がある
もっとバリバリのグラフ理論 • グラフの辺にループが出来ないように適当な向 きを付ける – DAGを作れば良い • 三角形はすべてこの形になる • ある辺について始点と終点から
同じ頂点に辺が出ている時 ちょうど1個三角形がある • 重複や漏れはない
Looking for Challenge グラフ理論 列挙
もっとバリバリのグラフ理論 • 全ての辺について、その始点からも終点からも 点が出ている頂点を数え上げれば良い
もっとバリバリのグラフ理論 • 全ての辺について、その始点からも終点からも 辺が出ている頂点を数え上げれば良い • ここで計算量を考える • 各辺についてその終点と始点から共通して出て いる頂点はflagを使って調べれば良い
もっとバリバリのグラフ理論 • 全ての辺について、その始点からも終点からも 点が出ている頂点を数え上げれば良い • ここで計算量を考える • 各辺についてその終点と始点から共通して出て いる頂点はflagを使って調べれば良い •
計算量はmax(始点の出次数、終点の出次数)
もっとバリバリのグラフ理論 • 全ての辺について、その始点からも終点からも 点が出ている頂点を数え上げれば良い • ここで計算量を考える • 各辺についてその終点と始点から共通して出て いる頂点はflagを使って調べれば良い •
計算量はmax(始点の出次数、終点の出次数) • 出次数をおさえることに成功したら計算量が削 減される
もっとバリバリのグラフ理論 • どうやって出次数を削減しようか?
Looking for Challenge グラフ理論 列挙
ひらめきのLooking for Challenge • 元の無向グラフの頂点たちの次数を求める • 各辺には次数が小さい方から大きい方に向きを 付ける
ひらめきのLooking for Challenge • 元の無向グラフの頂点たちの次数を求める • 各辺には次数が小さい方から大きい方に向きを 付ける • これでDAGになるので先ほどの数え上げが使え
る
ひらめきのLooking for Challenge • 元の無向グラフの頂点たちの次数を求める • 各辺には次数が小さい方から大きい方に向きを 付ける • これでDAGになるので先ほどの数え上げが使え
る • 出次数はどうなるだろうか?
ひらめきのLooking for Challenge • 命題1の証明を思い出す – 次数が√(2M)より大きい頂点は√(2M)個より少ない
ひらめきのLooking for Challenge • 命題1の証明を思い出す – 次数が√(2M)より大きい頂点は√(2M)個より少ない • 次数が√(2M)より小さい頂点はどんなふうに向 きを付けても出次数は√(2M)を超えない
ひらめきのLooking for Challenge • 命題1の証明を思い出す – 次数が√(2M)より大きい頂点は√(2M)個より少ない • 次数が√(2M)より小さい頂点はどんなふうに向 きを付けても出次数は√(2M)を超えない
• 次数が√(2M)より大きい頂点は自分より次数が 多い頂点にしか辺は出て行かない – √(2M)個もないので出自数は√(2M)を超えない
ひらめきのLooking for Challenge • 次数が√(2M)より小さい頂点はどんなふうに向 きを付けても出次数は√(2M)を超えない • 次数が√(2M)より大きい頂点は自分より次数が 多い頂点にしか辺は出て行かない –
√(2M)個もないので出自数は√(2M)を超えない
ひらめきのLooking for Challenge • どの頂点も出次数が√(2M)を超えない! • さきほどの考察より全計算量はM√2M • これは三角形の個数の最大値と一致するのでお およそ最適!
• やったぜ
テクニックまとめ • 辺の数がMの単純なグラフのなかで次数が最小 のものはO(√M) – 三角形の個数はO(M√M) • 次数が小さい方から大きい方に向きをつけると 全頂点の出次数をO(√M)に抑えられる。 •
min(a, b) ≦ √(ab)
Looking for Challenge 小倉拳 @catupper
今の発想を使う問題 • Algorithmic Engagements 2009 Round6 – Cakes • http://main.edu.pl/en/archive/pa/2009/cia •
面白いのでやってみてね!
クリックしてタイトルの挿入! ご清聴ありがとうございました