行列木定理の証明 - blogoid
0. はじめに 今回は行列木定理(Kirchhoff's theorem)の証明を紹介してみようと思います。 行列木定理とは、全域木の個数の数え上げに関する定理です。証明方法はいくつかありますが、今回は漸化式を用いた全域木の個数の数え上げとの対応を見ることで定理を証明してみたいと思います。 1. 定理の内容 頂点数$n$のループを含まない多重無向グラフ$G$が与えられたとします。対角成分に頂点の次数を並べた行列から、隣接行列*1を引いたものをラプラシアン行列といいます。つまり、$G$に対する$n$×$n$ラプラシアン行列$L=(l_{ij})$は$$\begin{aligned}l_{ij}=\begin{cases}\text{頂点iの次数}&(i=j)\\ \text{頂点iと頂点jの間の辺の数}\times (-1)&(\mathrm{otherwise}) \end{cases}
トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する - 終末 A.I.
Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。 一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。 もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない
Dijkstra法に関するn考察 〜前半〜 - Mister雑記
(思ったより長くなりそうだったので前半と後半に分けることにしました。 後半の投稿予定は未定です。) 競技プログラミングのグラフ問題でしばしば題材となるアルゴリズム「Dijkstra法」。 その名前のインパクトと汎用性から比較的知名度が高いアルゴリズムだが、実装がそこそこ重いため初心者の壁となることもある。 そんなDijkstra法について、私の持つ知識、イメージを適当に書き連ねていこうと思う。 目次 目次 Dijkstra法の概要 何をするアルゴリズムか 具体例 イメージ？ 実装方法 パターンA パターンB (PFS) 計算量の比較 問題例 後半について Dijkstra法の概要 何をするアルゴリズムか Dijkstra法を一言で説明するなら「重み付きグラフにおいて、ある頂点から他の全ての頂点までの最短距離を求める」アルゴリズムである。 一工夫すれば最短距離を実現する経路も同時に求められる
ダイクストラとポテンシャルのはなし - niuez’s diary
はじめまして, niuezといいます. 競プロを少ししています. 最近勉強したことのメモ書きをしておきます. ダイクストラ法 ダイクストラ法(Dijkstra)は負の長さの無いグラフで始点からの最短距離を求めるアルゴリズムです. 具体的には 距離が未確定の頂点の中で一番小さいものを選び, 距離を確定させる. 選んだ頂点から距離が未確定の頂点に伸びる辺で, 未確定な距離をより短いものに更新する. を繰り返します. これを実装すると $O(N)$ですが, よく知られるダイクストラの計算量は $O((E+ V) \log E)$ です(heapとかを使う). #include <set> #include <queue> #include <vector> struct edge { int u,v; int dist; }; std::vector<int> dijkstra(const st
Graph Golf参加記
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 執筆者: 清水 伸高 https://sites.google.com/view/nobutaka-shimizu/home NII主催のグラフコンペティション Graph Golfに助教とM2の先輩と僕の3人チームで参加して優勝し、12/10に札幌で開かれたCANDAR'15にて講演をしました。(めっちゃ高そうな盾とかもらいました！！！)ということでGraph Golfの問題内容や背景、および僕らのとった手法の概略について適当に書いていきます。 前提知識として知っておいてほしい単語は以下の2つくらいです。 グラフ(点と点が繋がってるアレのこと) 次数(頂点に繋がってる辺の本数のこと) 問題内容 自
最短経路の個数も一緒に数え上げる最短経路アルゴリズム - けんちょんの競プロ精進記録
ARC 090 E - Avoiding Collision で話題になったこともあり、簡単にメモします。 最短経路を求める DP 的処理をするとき、DAG上のDP だろうと、BFS だろうと、Dijkstra だろうと、以下のような緩和処理をやっています // Edge e の緩和 int dp[MAX_V]; // dp[v] := 始点 s から頂点 v への最短経路長 if (dp[e.to] < dp[e.from] + e.cost) { dp[e.to] = dp[e.from] + e.cost; } これをちょっと変えるだけで、最短経路の本数も一緒に数え上げられます。 // Edge e の緩和 int dp[MAX_V]; // dp[v] := 始点 s から頂点 v への最短経路長 int num[MAX_V]; // num[v] := 始点 s から頂点
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実
日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念 - アジマティクス
Ｑ：これは何の構造を表しているでしょう？ グラフ理論 上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。 （余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ ○○」や「グラフ理論 ○○」とググるよりも、「ネットワーク ○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています） さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例
二部グラフの最大マッチングと増加道 | 高校数学の美しい物語
グラフとは，点の集合と枝の集合からなる「つながり方」を表すモデルです。 二部グラフとは，点が 222 グループにわかれていて，同じグループ間はつながっていないようなグラフです。→グラフ理論の基礎
一般的なダイクストラ法 - kirika_compのブログ
概要 ダイクストラ法を使うと、単一始点 s から全ての頂点への最短距離が計算できるのは有名だね。これを少し拡張することで、「s からの最短距離と、それを実現する最短経路の個数」の組を、全ての頂点について計算することができるわ。 詳しく 少し天下り的だけど、以下の半環を考える。 (a, x) + (b, y) := a < b ? (a, x) : a > b ? (b, y) : (a, x + y), (a, x) * (b, y) := (a + b, x * y) この半環を使って、[Mohri2002]の方法でダイクストラ法を行うことにより、s-vの最短距離とs-vの最短経路の個数が全ての頂点vについて分かる。 ソースコードは以下の通り。 gist.github.com ARC090 E - Avoiding Collision で確かめた。 https://beta.atcode
競プロにおけるオイラー路とその応用について - Learning Algorithms
この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは？ ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラー路の構築 ・実装 ・例題 ・追加問題 ・最後に はじめに この記事では、オイラー路の基礎、そして主に競技プログラミングで使えるその応用についてできるだけ詳しく書きます。 最初の方は基礎的な定義や解説を書いているので、オイラー路とは何かをすでにご存知の方は、無向オイラー路の構築あたりからどうぞ。 説明で出てくるグラフは特に断らない限り連結で、多重辺や自己辺は基本的にあってもよいものとします。 また、もし必要があればこの記事に載せたコードはすべて自由に使って頂いて構いません。 例題で扱った問題は、はまや
『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
(UPD 11/15) 下の記事を書くにあたってやらかしたこととか、 返ってきた辛辣な反応を見て、いろいろ言いたくなったんですが、 自分の過ちがどんどん浮き彫りになった気がします。それはまた今度書きます。 個人的にPSP経由の解法はカットが苦手な人にはオススメだと思うので、 そういう人はぜひ試してほしいです。 次記事とか次々記事あたりは面白いんじゃないでしょうか。 - こういうツイートをした。 『昨日のARCに関してなんですが、個人的には、『燃やす埋める』という概念はそろそろ消え去るべきだと思っています。なぜかというとProjectSelectionの形そのものを覚えれば瞬殺だからです。だからみんな http://tokoharu.github.io/tokoharupage/docs/formularization.pdf のp7とかwikipediaのページを読んでほしい』 珍しく腹が
グラフ・ネットワーク分析で遊ぶ(3)：中心性(PageRank, betweeness, closeness, etc.) - 渋谷駅前で働くデータサイエンティストのブログ
ビジネス的に重要度が高いのがこの辺の話題ではないかな？ということで、今回は中心性(centrality)の話題を取り上げてみようと思います。参考文献はいつも通りこちら。 ネットワーク分析 (Rで学ぶデータサイエンス 8) 作者: 鈴木努,金明哲出版社/メーカー: 共立出版発売日: 2009/09/25メディア: 単行本購入: 5人 クリック: 62回この商品を含むブログ (9件) を見る データセットはこれまで通り前々回適当に生成したグラフのものと、C elegansと、さらに以前使った『レ・ミゼラブル』の人物相関図を対比のために併用しようと思います。 そもそも中心性とは 『ネットワーク分析』p.41にはこんなことが書いてあります。 中心性は、ネットワークにおける各頂点の重要性を評価したり、比較したりするための指標である。例えば、交通ネットワークでは、ある地点から他の地点へ移動するための道
2部グラフにおける最大マッチングの個数と最小点被覆の個数の一致 - komiyamの日記
蟻本に載っていた事実だけど、理解するのに時間がかかった。 まず、前段階として|マッチング| <= |点被覆|であることを確認しよう(これは一般のグラフで成り立つ)。これは、マッチングに含まれる辺を被覆するのに最低限マッチングと同じだけの点が必要だから。なので|最大マッチング|<=|最小点被覆|となる。 具体的に最小点被覆を構成してみよう。2部グラフにsinkとsourceつなげて最大流を流し、最大マッチングを作る。このとき、残余グラフでsourceから到達不可能な左側の点集合と到達可能な右側の点集合の和集合Xが最小点被覆になっている。以下ではこれを示す。 もっと具体的に考えてみよう。図のように色を付ける。最大マッチングに含まれる辺は赤。そうでなければ黒。 左から右にいくときは黒だけ通れる。右から左にいくときは赤だけ通れる。赤い辺がついていない左の点を出発点にできる。 ここで次の2つを調べて
最小費用流の負辺除去 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。 この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくなるのでは思います。 （2019-06-27に若干書き換えました） 追記 (2021-08-15)： ポテンシャルを求めるのが簡単な場合にはそれを使って負辺除去する方が楽です。 この記事の方法はグラフが複雑だったり、思考停止したいとき用かなぁ。 例題 最小費用流への認識 最小費用流は「始点 S から終点 T に水を流す」という問題に見えがちですが、それは少し本質とずれています。 水の例えを用いつつ言うならば「頂点間で水をやりとりして過不足を補い合う」という感じでしょうか。 実装の際に始点と終点があった方が分かりやすいことがあるだけで、定義上は必要なものでは
Linear-time Kernelization for Feedback Vertex Set - wataの日記
https://arxiv.org/abs/1608.01463 が ICALP 2017 に採択されたので内容の解説をします． 概略 取り除くと残りが無閉路になる頂点集合を Feedback Vertex Set (FVS)と言い，与えられた無向グラフの最小FVSを求める問題をFVS問題と言います．これは有名なNP困難問題で，FPTアルゴリズムという理論アルゴリズムの研究分野で盛んに研究されており，PACE Challenge*1 というFPTアルゴリズムの実性能を競うコンテストの記念すべき第一回目 (2016年) の題材として選ばれました (ちなみに2017年のコンテストは 5/1 締め切りでまだ間に合うので興味のある方はぜひご参加ください)．この問題に対して，答えが$k$ (頂点数$n$に対してかなり小さいと想定)の時に $4^k n^{O(1)}$ 時間で動作するアルゴリズムを以前
組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サンタコンペで二度全完した話
組合せ最適化でクリークを解く - Qiita
http://www.logopt.com/python_learning/wp-content/uploads/2014/05/mipproblem2.pdf