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
97
計算量の話
catupper
0
1.1k
Graph is Fun
catupper
0
130
About累積和
catupper
0
1.6k
For You
catupper
1
140
Other Decks in Programming
See All in Programming
Vitest Browser Mode への期待 / Vitest Browser Mode
odanado
PRO
2
1.7k
Amazon Neptuneで始めてみるグラフDB-OpenSearchによるグラフの全文検索-
satoshi256kbyte
4
330
qmuntal/stateless のススメ
sgash708
0
120
Streams APIとTCPフロー制御 / Web Streams API and TCP flow control
tasshi
1
290
ECS Service Connectのこれまでのアップデートと今後のRoadmapを見てみる
tkikuc
2
210
go.mod、DockerfileやCI設定に分散しがちなGoのバージョンをまとめて管理する / Go Connect #3
arthur1
10
2.4k
Macとオーディオ再生 2024/11/02
yusukeito
0
180
Go言語でターミナルフレンドリーなAIコマンド、afaを作った/fukuokago20_afa
monochromegane
2
140
飲食業界向けマルチプロダクトを実現させる開発体制とリアルな現状
hiroya0601
1
390
カラム追加で増えるActiveRecordのメモリサイズ イメージできますか?
asayamakk
4
1.6k
Vue SFCのtemplateでTypeScriptの型を活用しよう
tsukkee
3
1.5k
LLM生成文章の精度評価自動化とプロンプトチューニングの効率化について
layerx
PRO
2
140
Featured
See All Featured
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
191
16k
Six Lessons from altMBA
skipperchong
26
3.5k
Scaling GitHub
holman
458
140k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
3
370
Stop Working from a Prison Cell
hatefulcrawdad
267
20k
The Pragmatic Product Professional
lauravandoore
31
6.3k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
9
680
Fantastic passwords and where to find them - at NoRuKo
philnash
50
2.8k
Intergalactic Javascript Robots from Outer Space
tanoku
268
27k
Building a Modern Day E-commerce SEO Strategy
aleyda
38
6.9k
How GitHub (no longer) Works
holman
311
140k
The Power of CSS Pseudo Elements
geoffreycrofte
72
5.3k
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 •
面白いのでやってみてね!
クリックしてタイトルの挿入! ご清聴ありがとうございました