グラフとは，点の集合と枝の集合からなる「つながり方」を表すモデルです。 二部グラフとは，点が 222 グループにわかれていて，同じグループ間はつながっていないようなグラフです。→グラフ理論の基礎
二部グラフの最大マッチングと増加道 | 高校数学の美しい物語
グラフとは，点の集合と枝の集合からなる「つながり方」を表すモデルです。 二部グラフとは，点が 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日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは？ ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラー路の構築 ・実装 ・例題 ・追加問題 ・最後に はじめに この記事では、オイラー路の基礎、そして主に競技プログラミングで使えるその応用についてできるだけ詳しく書きます。 最初の方は基礎的な定義や解説を書いているので、オイラー路とは何かをすでにご存知の方は、無向オイラー路の構築あたりからどうぞ。 説明で出てくるグラフは特に断らない限り連結で、多重辺や自己辺は基本的にあってもよいものとします。 また、もし必要があればこの記事に載せたコードはすべて自由に使って頂いて構いません。 例題で扱った問題は、はまや
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 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
グラフとネットワーク - okamoto7の日記
明日から『グラフとネットワーク』という講義が始まるので，いろいろと思うことを書いておく． まず，このような授業をやることを依頼されて，それでシラバスとか考えて，立ち上がったわけだけども，この講義の名前が『グラフ理論』になりそうだったが，それは避けられた．もっとも，『グラフ理論』をやってもよいわけだし，私が『グラフ理論』の講義をすることもできるし，実際『グラフ理論』の講義もやったことがあるのだけれども，この『グラフとネットワーク』は「グラフ理論」の講義ではない．実際依頼された内容を考えれば『グラフ理論』などという名前を付けることは，学生に対して間違った印象を与えるだけで，害悪であるとさえ思える． よく大学の講義名に「○○」のあとに「理論」をつけて『○○理論』としてしまうものがあるが，それが本当に「○○理論」なのかどうかということを反省する必要がある．日本の大学において『グラフ理論』という名前
Googleの旅行アプリで使われている280年前のアルゴリズムとは？
By Celeste RC Googleが2016年9月20日にリリースした「Google Trips」は旅行に関する情報をまとめて管理できるアプリで、目的地までの移動方法や行き方、移動時間、観光地の場所や付近にあるレストランなど、さまざまな情報を元にして旅行の計画表を自動で作ることができます。Googleによれば、このGoogle Tripsに使用しているアルゴリズムは280年前のものを元にしているとのことで、その詳細をGoogleが公式ブログで明かしています。 Research Blog: The 280-Year-Old Algorithm Inside Google Trips https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html Google Trips - Google Pl
爆速ナンバーリンクソルバー（1）〜ナンバーリンクと充足可能性問題 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 先ほど、ブラウザで動くナンバーリンクソルバー（http://jkr2255.github.io/js_puzzle_solvers/numberlink.html）を公開しました。それについてまとめようと思ったのですが、1本の記事に書くには長すぎるので、少しずつ分けて書いていこうと考えています。 まずは、問題そのものである「ナンバーリンク」と、それの解法に使った「充足可能性問題」について解説します。 まず、「ナンバーリンク」って？ ナンバーリンクは、数独やクロスワードといった、（もともとは）紙と鉛筆で楽しむ「ペンシルパズル」の一種です。
2-SATと強連結成分分解 - naoya_t@hatenablog
ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。（ちなみにSRM464には出場している） SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみのあれです (x_0 ∨ ¬x_1) ∧ (¬x_0 ∨ ¬x_3) ∧ ... みたいな論理式（乗法標準形）を満たす真偽値 x_0, x_1, ... の組み合わせが存在するか否か。（存在する場合、その組み合わせを知りたかったりする） 上の例ではすべての節が(高々)2変数なので2-SATと呼ばれる。 （2-SATは線形時間で解けるらしい）。 論理和 x ∨ y が論理包含 ¬x⇒y （または ¬y⇒x）に書き換え可能なことを利用して、論理式を有向グラフに変換してみたり 出来上がっ
巡回セールスマンの計算量はO(n)というのはなんとなくわかるのですが動的計画法を使った時はO(n^2×2^n)というのが何故だ... - Yahoo!知恵袋
Ｏ（ｎ）で解けたら学術雑誌で大注目を浴びると思うのですが？ 動的計画法の肝は、同じ状態になるルートが多数あるとき一番いいルート以外切り捨てることです。 巡回セールスマン問題の状態は。 今まで通ってきた地点の組み合わせが２＾ｎで今いる地点がｎ通りなので。 動的計画法では ｎ*２＾ｎ通りの状態を考えこれらすべてから次の地点への移動を検証する必要があります。 これをｎ点回りおわるまで続けるのですが、この中で２＾ｎ通りでいらない状態を無視することで計算量をおとせます。 大雑把な計算量がｎ*ｎ*２＾ｎ となるわけです。
/proc/cpuinfo: 全点対間最短路を高速に求める
フィックスターズは今年も ACM ICPC つくば大会 にスポンサーとして協賛しております。今年はコンテスト後の懇親会でクイズを出題しているのですが、その問題準備の際に作ったはいいものの結局使われなかったコードが大量に出てきてしまったため、それらをまとめて簡単な解説とともに公開いたします。 全点対間最短路問題 全点対間最短路問題はN個の頂点を持つ有向グラフにおける任意の2点間の最短路を求める問題です。密なグラフの全点対間最短路を求めるアルゴリズムとしてワーシャル-フロイド法が広く知られており、以下のような非常にシンプルなコードで求めることができます。 // 入力: A[i][j] = 頂点iと頂点jを結ぶ辺の重み // 出力: A[i][j] = 頂点iから頂点jまでの最短路の重みの総和 for(int k = 0; k < N; ++k) for(int i = 0; i < N; ++
Hallの結婚定理とその証明 | 高校数学の美しい物語
まず，条件1を理解するためにマッチングについて説明します。 （追記：二部グラフの最大マッチングと増加道） マッチングとは端点がかぶらないように辺をいくつか取ってきたものです。また，マッチングの端点に属する頂点を「マッチングでカバーされている」と言います。 例えば，図では緑の辺がマッチングの一例です。頂点集合 UUU の中で上三つはカバーされていますが，一番下はカバーされていません。 VVV は全てカバーされています。 UUU の各頂点を男性，VVV の各頂点を女性，男性 aaa が女性 bbb とお互いに結婚してもよいと思うとき (a,b)(a,b)(a,b) に辺を引いたグラフを考えてみます。このときマッチングは結婚成立の一例を表しています。 すなわち条件1は， 「うまいマッチングを選べば男がみんな結婚できる」という条件になります。 次は条件2について説明します。 UUU の部分集合 A
最小カットについて - よすぽの日記
わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、 なんかいい感じのグラフを作ったらなんかそれの最小カットが答え というのがあります 最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り分けるという問題を考えます。燃やすと埋めるでも大丈夫です 最小カットで解ける問題というのは、実は 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある 罰金の最小値は？ という問題だけです。 これの解法は、 「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る SからTに最大流 流せた量が答え 処理できる条件は「Xが赤で、Y
Spaghetti Source - 木の直径
説明 非負の重みを持つ無向の木が与えられたとき，木の直径，すなわち最遠頂点間距離を求める． アルゴリズム自体はシンプルである．まず適当な頂点 s から探索を行い，最も遠い頂点 u を求める．次に u から探索を行い，最も遠い頂点 v を求める．このとき (u, v) は最遠頂点対である． 実行時間が O( E ) となることは明らかである．探索に深さ優先探索を用いれば，定数も（行数も）小さくすむ．そこで以下アルゴリズムの正当性を証明する． アルゴリズムの正当性のためには，木の最遠頂点対を x, y としたとき，x または y として s からの最遠頂点 u を選んでもかまわないことを証明すれば十分である．s からの最遠頂点を u とし，s からの経路で，u と x が分かれる点を t と置く．y の位置について，次のように場合わけを行う． y が s-t 間にある場合：y を s に取り直
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
組合せ最適化でクリークを解く - Qiita
http://www.logopt.com/python_learning/wp-content/uploads/2014/05/mipproblem2.pdf
色々なダイクストラ高速化
コスト行列とハンガリー法