最大流問題や最小カット問題などについて記事を足す

[kmyk]

close #127 close #139 close #152 close #153

まだ作業中なのですがとりあえずプルリクの形にしておきます。 構成をひっくり返すことになるようなレビューコメントがあるならしてほしいですが、詳しいレビューはまだ待ってください。

プレビュー:

• https://kmyk.github.io/algorithm-encyclopedia-staging/maximum-flow-problem#noredirect
• https://kmyk.github.io/algorithm-encyclopedia-staging/minimum-cut-problem#noredirect
• https://kmyk.github.io/algorithm-encyclopedia-staging/moyasu-umeru-mondai#noredirect
• https://kmyk.github.io/algorithm-encyclopedia-staging/project-selection-problem#noredirect

[MiSawa]

燃やす埋めるやPSPに独立したページを与えることは考えましたか? 例えば「強連結成分分解のページに、2-SAT の問題定義と帰着の仕方の解説がある」と同型なことになっている気がします。(が、距離がだいぶ違う気もしなくはないです)

[kmyk]

燃やす埋めるや PSP に独立なページを与えるのは検討し漏らしていました。 「一方から一方へ帰着可能なだけの異なる問題」だと思えば分けたい気持ちは分かって、しかし距離が近すぎて「具体的な応用テクのひとつ」とか「最小カット問題の問題クラスの部分クラスであって名前が付いたもの」でしかないので埋め込んだ方がよいという気持ちもあります。たとえば「有限体のページに mod 1000000007 の場合の話題がある」のような構造です。

微妙なラインなはずでかなり迷っています。どちらがよいかの意見があれば言ってください。 いま以下のように書かれていて、このような説明の仕方 (帰着可能な異なる問題) でそのまま行くのなら独立なページを与えることになるのかなとは思っています。

競技プログラミングのコミュニティにおいて「燃やす埋める問題」という名前で呼ばれている問題は、最小カット問題に帰着できる問題のひとつである。

[MiSawa]

燃やす埋めるとかPSP自体で記事が立っていたりするのと、コストが非負とは限らない一般の場合でも、劣モジュラになるよう反転出来るならば云々のような話も入れたほうがよさそうだとかを考えると、独立なページを与える価値がありそうな気もします。 ただ、燃やす埋めるとPSPでひたすら同じような話が出てきそうで、どうしたもんかなぁという懸念もあり…

[kmyk]

燃やす埋める問題と project selection problem に独立したページを与えました。

ところで、一般の最小カット問題の話題なのに「燃やす埋める問題」という言葉を使っているように見えるブログ記事がいくつかあるように見えて対応に困っています。つまり、「最小カットは「頂点を (S, V \ S) に 2 分割して、s ∈ S, t ∉ S としたときに、{uv | u ∈ S, v ∉ S} の重み和を最小化せよ」という問題」なわけですが、この集合 S のことを「燃やす」と呼んで集合 V \ S のことを「埋める」と呼んで議論しているように見えるブログ記事があります。記号として「燃やす」と「埋める」を使えばなんでも燃やす埋める問題になるわけではないはずなのですが。

[noshi91]

燃やす埋めると最小カットが近すぎるのが原因だと思います。 燃やす埋めるの厳密な定義は多分存在しない？はずなので

[kmyk]

@noshi91 @MiSawa ひとまず完成と言える状態になったと思います。レビューよろしくお願いします。