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
新卒から4年間、20年もののWebサービスと 向き合って学んだソフトウェア考古学
oguri
7
6.5k
snacks.nvim内のセットアップ不要なプラグインを紹介 / introduce_snacks_nvim
uhooi
0
330
ニックトレイン登壇資料
ryotakurokawa
0
140
バックエンドNode.js × フロントエンドDeno で開発して得られた知見
ayame113
5
1.3k
AIエージェントを活用したアプリ開発手法の模索
kumamotone
1
740
AtCoder Heuristic First-step Vol.1 講義スライド
terryu16
2
1k
MCP世界への招待: AIエンジニアが創る次世代エージェント連携の世界
gunta
2
550
php-fpm がリクエスト処理する仕組みを追う / Tracing-How-php-fpm-Handles-Requests
shin1x1
5
810
PHPでお金を扱う時、終わりのない 謎の1円調査の旅にでなくて済む方法
nakka
3
990
20250326_生成AIによる_レビュー承認システムの実現.pdf
takahiromatsui
17
5.2k
Django for Data Science (Boston Python Meetup, March 2025)
wsvincent
0
230
CQRS+ES勉強会#1
rechellatek
0
390
Featured
See All Featured
Into the Great Unknown - MozCon
thekraken
36
1.7k
A designer walks into a library…
pauljervisheath
205
24k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
102
18k
Rebuilding a faster, lazier Slack
samanthasiow
80
8.9k
Documentation Writing (for coders)
carmenintech
69
4.7k
The Invisible Side of Design
smashingmag
299
50k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
8
700
Building Flexible Design Systems
yeseniaperezcruz
328
38k
Large-scale JavaScript Application Architecture
addyosmani
511
110k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
49k
Unsuck your backbone
ammeep
670
57k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
177
52k
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 •
面白いのでやってみてね!
クリックしてタイトルの挿入! ご清聴ありがとうございました