miscalc のブログ

主に競プロの話をします

競プロで使う Dilworth の定理

大学の授業で Dilworth の定理が出てきたので、この機会に（競プロer 的な視点から）まとめてみたいと思います。

例題 1

atcoder.jp

長さ N の数列 A = (A_1, A_2, \ldots, A_N) がある。 N 個それぞれの整数に対して、色を 1 つ選んで塗る。ただし、次を満たす必要がある：

  • A_i と A_j（ i \lt j）が同じ色で塗られているならば、 A_i \lt A_j

このとき、最小で何種類の色を用いればよいか？ N \leq 10^5

最小パス被覆

A = (2, 4, 3, 6, 1, 5) という例で考えてみましょう。まず、二次元平面上に (i, A_i) をプロットしてみます（横軸が i で、縦軸が A_i です）。

次に、これらをグラフの頂点と考えます。 (i, A_i) に対応する頂点を頂点 i と呼ぶことにします。 i \lt j かつ A_i \lt A_j のとき、 i \rightarrow j の辺*1を張ります。つまり、「左下から右上」なものすべてにその向きで辺を張ります。こうしてできるグラフを G とします。

ここで、この G は DAG（Directed Acyclic Graph：有向非巡回グラフ。閉路が存在しない有向グラフのこと）であり、さらに

  • i \rightarrow j の辺、 j \rightarrow k の辺がともに存在するならば、 i \rightarrow k の辺も存在する

ことに注意です。これは

  • 頂点 i から頂点 j（ i \neq j）にたどり着けるならば、頂点 i から頂点 j への（直接の）辺が存在する

と思ってもいいです（こちらのほうが直感的かも）。この性質のことを、この記事では（後で紹介する半順序集合との対応になぞらえて）推移律 と呼ぶことにします。

このときもとの問題は、「同じ色で塗られている頂点の間には、必ず辺が存在する」という条件を満たすように各頂点に色を塗り、そのうえで使う色の個数を最小化すること、と言い換えられます。たとえば次のように 3 色で塗れて、これが最適です*2。

なお、ここで同じ色で塗られた頂点集合のように、

  • その頂点集合に含まれるどんな異なる 2 頂点の間にも、辺が存在する

という条件を満たす G の頂点集合は、 G の パス と対応します（下図）。ここで G の推移律が効いています。

そう考えると、この問題は「 G の頂点をパスに分割*3するとき、パスの個数を最小化する」問題といえます（パスへの分割を パス被覆、サイズ（パスの数）が最小のパス被覆を 最小パス被覆 といいます）。

最大独立集合

ここで、下図の斜線を引いた頂点について考えます。

斜線を引いた頂点は、どの異なる 2 つについても辺が張られていません。ですから、これらはすべて違う色で塗る必要があります。

なお、この斜線を引かれた頂点の集合のように、

  • その頂点集合に含まれるどんな異なる 2 頂点の間にも、辺が存在しない

という条件を満たす G の頂点集合のことを、 G の 独立集合 といいます。また、サイズが最大の独立集合を 最大独立集合 といいます。上の考察をこの言葉を使って言い換えると、 G が推移律を満たす DAG ならいつでも、次が成り立つといえます。

\begin{align} (G \ の最小パス被覆のサイズ) \geq (G \ の最大独立集合のサイズ) \tag{1} \label{dilworth_geq} \end{align}

Dilworth の定理

実は、\eqref{dilworth_geq} よりも強い主張である次が、 G が推移律を満たす DAG ならいつでも成り立ちます：

\begin{align} (G \ の最小パス被覆のサイズ) = (G \ の最大独立集合のサイズ) \tag{2} \label{dilworth_eq} \end{align}

上の例でいうと、斜線を引いた 3 頂点は違う色で塗る必要があるが、実は全体を塗るのもそれに使った 3 色で事足りる、ということですね。これが Dilworth の定理 です*4*5。証明は、例題 2 のほうで重要になってくるのでいったん後回しにします。

これを使うことで、最小パス被覆問題を、最大独立集合問題に変換できるというわけです。今回の問題では、最大独立集合のサイズは単調非増加部分列の長さの最大値であり、LIS と同様に O(N \log N) で計算できます。

（補足）半順序集合とそのグラフ表現

半順序集合の定義

半順序集合 とは、集合 P *6とその上の二項関係 \preceq の組 (P, \preceq) であって、

  • 反射律：どんな a \in P に対しても、 a \preceq a
  • 推移律：どんな a,b,c \in P に対しても、 (a \preceq b かつ b \preceq c) ならば a \preceq c
  • 反対称律：どんな a,b \in P（ a \neq b）に対しても、 a \preceq b と b \preceq a の両方は成り立たない

を満たすもののことをいいます。気持ち的には、不等号っぽい比較が（定義されていれば）いい感じにできる、という感じだと思えばよさそうです。今回の問題の (i, A_i) も、二項関係 \preceq を

  • (i, A_i) \preceq (j, A_j) \Leftrightarrow i = j または (i \lt j かつ A_i \lt A_j)

で定義したときに、半順序集合をなします。

半順序集合のグラフ表現

上で考えたように、半順序はグラフ（より具体的には、推移律を満たす DAG）で表現できます。ちゃんと書くと、 P の要素に対応する頂点をもつ有向グラフ G であって、

  • a \preceq b（ a,b \in P, a \neq b）のとき、 a に対応する頂点から b に対応する頂点に有向辺が張られている

ものを考えます。このとき、反対称律は G が DAG であることに、推移律は G の推移律に対応します。

半順序集合の言葉での Dilworth の定理

P の部分集合 C が 鎖（chain）であるとは、 C の異なる 2 つの要素をどのようにとってきても、 \preceq による比較が可能であることをいいます。より形式的には、「どんな x,y \in C に対しても x \preceq y または y \preceq x が成り立つ」と書けます。これは G のパスに対応します。

P の部分集合 A が 反鎖（antichain）であるとは、 A の異なる 2 つの要素をどのようにとってきても、 \preceq による比較が不可能であることをいいます。より形式的には、「どんな x,y \in A, x \neq y に対しても x \preceq y とはならない」と書けます。これは G の独立集合に対応します。

有限半順序集合 (V, \preceq) において、

\min(V \ を鎖に分割したときの鎖の個数) = \max(V \ の反鎖のサイズ) \tag{3} \label{dilworth_poset}

が成り立つ、というのが（本当の）Dilworth の定理です*7。これは（当然ですが）上の \eqref{dilworth_eq} に対応します。

グラフで表現したときに推移律を満たす DAG になっている、という思考をするよりも、半順序集合をなしていると捉えるほうが直感的な場面も多いと思ったので、紹介しました。

例題 2

atcoder.jp

文字列 S がある。 S の連続部分文字列のうちで回文であるものをいくつか選びたい。ただし、次を満たす必要がある：

  • 選んだ回文のうち 2 つであって、一方が他方の連続部分文字列であるものが存在してはいけない

このとき、最大で何個の回文を選べるか？ |S| \leq 200

ABC-Ex ではあるものの、ここまでの内容を理解していればそう身構える必要はないと思います。

文字列の集合に対して、一方の文字列が他方の文字列の連続部分文字列である、という二項関係を定義すると、これは半順序集合をなします。よって、文字列の集合として S の連続部分文字列である回文の集合をもってくると、求めるものはその反鎖のサイズの最大値です。これは Dilworth の定理から、鎖に分割するときの鎖の個数の最小値になります。

Dilworth の定理を使う向きが例題 1 と逆になっていますね。

最小パス被覆の、二部グラフの最大マッチングへの帰着

先ほどもみたように、「鎖に分割するときの鎖の個数の最小値」はグラフの言葉でいうと「最小パス被覆」です。実は、DAG の最小パス被覆は二部グラフの最大マッチングに帰着します。

二部グラフとは？ 頂点を 2 グループに分けるとき、「同じグループに属する 2 頂点の間には、辺が存在しない」ようにできるグラフのことです。

グラフのマッチングとは？ グラフの辺をいくつか選ぶ方法であって、「どの頂点も、選んだ辺のうち異なる 2 つ以上の辺の端点になっていることはない」ようなもののことです。このうちサイズ（選んだ辺の数）が最大のものが最大マッチングです。

N 個の頂点 1, 2, \ldots, N をもつ DAG G を、 N 個の左側頂点 1, 2, \ldots, N と N 個の右側頂点 1', 2', \ldots, N' *8 をもつ二部グラフ H に対応させることを考えます。対応のさせ方としては、 G の i \rightarrow j の辺を、 H の i \ – \ j' 間の辺に対応させます。

このとき、

(G \ の最小パス被覆のサイズ) = N - (H \ の最大マッチングのサイズ) \tag{4} \label{pathcover_matching}

が成り立ちます。

この理由を説明します。まず、 G のパス被覆について、

(パス被覆のサイズ) = N - (パス被覆に含まれる辺の数) \tag{5} \label{pathcover_edge}

が成り立ちます。これは、パス被覆に使ったパスのどれについても、

(頂点数) = (辺数) + 1 \tag{6} \label{vertex_edge}

となっているからです。\eqref{vertex_edge} をすべてのパスについて足し上げると \eqref{pathcover_edge} になります。\eqref{pathcover_edge} は、「パス被覆のサイズを最小化することは、パス被覆に含まれる辺の数を最大化することと同じである」とも捉えられます。

次に、 G のパス被覆と H のマッチングは上図のように一対一対応します。つまり、

  • G のパス被覆について、使った辺に対応する H の辺を使ったものは H のマッチングです。

    • パス被覆に含まれる辺について、同じ頂点から出ている 2 辺や、同じ頂点に入っている 2 辺はないため、対応する H の辺についても端点を共有する 2 辺は存在しないことになるからです。

  • 逆に、 H のマッチングについて、使った辺に対応する G の辺を使ったものは G のパス被覆です。

    • マッチングに含まれる辺について、端点を共有する 2 辺は存在しないので、対応する G の辺について、同じ頂点から出ている 2 辺や、同じ頂点に入っている 2 辺はありません。ここで、 G は DAG なので、この辺集合はパス被覆をなします*9。

以上より、\eqref{pathcover_matching} が成り立つといえます*10。

これで、二部グラフの最大マッチングが解ければよいことになったので、この問題が解けました*11。細かい計算量評価はここではしません（気になる方はこちらを見るとよいです）が、少なくとも多項式時間にはなっていることがわかると思います。最大独立集合問題は一般のグラフでは NP-hard なのですが、推移律を満たす DAG という特殊ケースでは Dilworth の定理により多項式時間で解けるようになっている、というのはなかなかすごいことだと思います。

Dilworth の定理の証明

DAG の最小パス被覆が二部グラフの最大マッチングに帰着する、つまり、

(G \ の最小パス被覆のサイズ) = N - (H \ の最大マッチングのサイズ) \tag{3) (再掲}

という事実は、実は Dilworth の定理の証明の根幹の一つになっています*12。他に示すことは次の 2 つです。

(H \ の最大マッチングのサイズ) = (H \ の最小点被覆のサイズ) \tag{7} \label{konig}

(G \ の最大独立集合のサイズ) \geq N - (H \ の最小点被覆のサイズ) \tag{8} \label{mis_vertexcover}

これらが示せれば (G \ の最大独立集合のサイズ) \geq (G \ の最小パス被覆のサイズ) がわかります。\eqref{dilworth_geq}（ \leq のほうが成り立つこと）がすでにわかっているので、それとあわせて \eqref{dilworth_eq}（ = が成り立つこと）がわかります。

グラフの点被覆とは？ グラフの頂点をいくつか選ぶ方法であって、「どの辺についても、その端点の少なくとも一方が選んだ頂点に含まれる」ようなもののことです。このうちサイズ（選んだ頂点の個数）が最小のものが最小点被覆です。

二部グラフでの、最大マッチングと最小点被覆の関係（Kőnig の定理）

(H \ の最大マッチングのサイズ) = (H \ の最小点被覆のサイズ) \tag{7) (再掲}

これは一般の二部グラフで成り立ちます（Kőnig の定理*13 と呼ばれます）。

まず、（二部グラフに限らず）どんなグラフでも、明らかに

(点被覆のサイズ) \geq (マッチングのサイズ) \tag{9} \label{konig_geq}

です。マッチングに含まれる辺について、その端点の少なくとも片方は選ばないと、点被覆になりません。これらの端点は重複して出てこないので（これはマッチングの定義からわかります）、マッチングのサイズと同じだけの個数の頂点は最低でも選ぶ必要があるということです。

次に、最大マッチングのサイズと等しいサイズの点被覆が存在することを示します。これがいえたら、（最小点被覆のサイズは当然この点被覆のサイズ以下なので） (最大マッチングのサイズ) \geq (最小点被覆のサイズ) がいえて、\eqref{konig_geq} とあわせて \eqref{konig} が示せます。

ここで、マッチングに使わない辺を黒、使う辺を橙で塗ることにしたとき、通る辺の色が交互になっているパスを 交互道 といい、交互道の中でも端点がいずれもマッチングに使われていないものを 増加道 といいます。最大マッチングには増加道は存在しません*14。なぜなら、もし存在したら、それに含まれる辺の色をすべて反転させることで、マッチングのサイズを 1 増やせるからです。

さて、最大マッチングをひとつとってきたとき、マッチングに使われていない左側頂点を黄色く塗り、そこから左側から右側へは黒い辺、右側から左側へは橙の辺を使って（言い換えると、黒 → 橙 → 黒 → 橙 → … という交互道を使って）到達可能な頂点を黄色で、到達不可能な頂点を白で塗ることにします。このとき、左側の白い頂点と右側の黄色い頂点をすべて選ぶと、これは点被覆になります。

なぜなら、これが点被覆にならないのは左側の黄色い頂点と右側の白い頂点の間に辺が存在する場合のみ*15ですが、そのようなことは起こらないからです。

  • もし左側の黄色い頂点と右側の白い頂点の間に黒い辺が存在したら、それを使って左側の黄色い頂点から右側の白い頂点に行けているはずなのでおかしいです。

  • もし左側の黄色い頂点と右側の白い頂点の間に橙の辺が存在したら、左側の黄色い頂点に行けているのはおかしいです（マッチングに使われているので最初には黄色く塗られませんから、右側の黄色い頂点から橙の辺を使って来たことになります。このときこの左側頂点を端点とする橙の辺が 2 本あることになってしまいます。マッチングのはずなのでおかしいです）。

この点被覆が、欲しかった「最大マッチングのサイズと等しいサイズの点被覆」です。これは、次のことからわかります。

  • 左側の白い頂点には、それを端点とする橙の辺がある。

    • もしなかったら、その頂点はマッチングに使われていないので最初に黄色く塗られるはずである。

  • 右側の黄色い頂点には、それを端点とする橙の辺がある。

    • もしなかったら、増加道が存在していることになる（マッチングに使われていない左側頂点から、交互道を使って、マッチングに使われていないこの右側頂点まで来たことになるので）。これは、最大マッチングであることに矛盾する。

  • 左側の白い頂点と右側の黄色い頂点を結ぶ橙の辺はない。

    • もしあったら、それを使って右側の黄色い頂点から左側の黄色い頂点に行けているはずである。

これで示せました。

最大独立集合と、二部グラフの最小点被覆の関係

(G \ の最大独立集合のサイズ) \geq N - (H \ の最小点被覆のサイズ) \tag{8) (再掲}

「 G の独立集合であって、サイズが N - (H \ の最小点被覆のサイズ) 以上のもの」が存在することを示します。これが示せれば、最大独立集合のサイズは当然この独立集合のサイズ以上なので、\eqref{mis_vertexcover} が成り立つといえます。これは \eqref{konig} を示すときに使った論法にもよく似ていると思います。

H の最小点被覆について、 G の頂点集合を次のルールで対応させます。

  • 頂点 i も頂点 i' もその点被覆に含まれていないとき、 G の頂点 i を選ぶ。

このとき、選ばれた G の頂点の集合は G の独立集合になっています（もしなっていなかったら、点被覆になっていません）。

この独立集合のサイズは「頂点 i と頂点 i' が、両方 H の最小点被覆に含まれる」ような i の個数によって変わってくるのですが、もしそのような i が存在しなければ、サイズは N - (H \ の最小点被覆のサイズ) に等しいです。

実は、 G が推移律を満たすときは必ずそうなることがわかる*16のですが、別にそうでなくてもいいです。もし「頂点 i と頂点 i' が、両方 H の最小点被覆に含まれる」ような i が存在したら、独立集合のサイズはそのような i の個数のぶんだけ増えます。

よって \eqref{mis_vertexcover} が成り立つことが示せました。

まとめ

例題 1 では、「鎖に分割するときの鎖の個数の最小値」を「反鎖のサイズの最大値」に変換して問題を解きました。この問題の設定において、変換後の問題が LIS という性質がよくて少ない計算量で解ける問題だったので、これが使えました。

例題 2 では逆に、「反鎖のサイズの最大値」を「鎖に分割するときの鎖の個数の最小値」に変換して問題を解きました。こちらは最小パス被覆になり、計算量が（例題 1 の制約では使えない程度には）かかりますが、いつでも二部グラフの最大マッチングを使って（多項式時間で）解ける問題でした。

また、半順序集合を表して得られるグラフ（つまり、推移律を満たす DAG） G と、それにうまく対応する二部グラフ H を考えたときに

  • G の最小パス被覆

  • H の最大マッチング

  • H の最小点被覆

  • G の最大独立集合

がすべて互いに対応する（しかも不等号ではなく等号の関係で！）ということをみました。この関係と、それに用いた仮定をまとめたのが下図です：

参考にしたものなど

*1:頂点 i から頂点 j に向かう有向辺のことをこう書くことにします

*2:ほかにも最適な塗り方はあります

*3:ちゃんと言うと、パスの集合であって、どの頂点もそのうちちょうど 1 つに含まれるようなものです

*4:ちょっと嘘です。本当は半順序集合に対しての定理のことをそう呼んでいる気がします（たぶん）。これについてはこの次の節で触れます

*5:この記事では詳細には触れませんが、似たような定理として Mirsky の定理というのもあります。主張だけ述べると、同じく推移律を満たす DAG G に対して、 (G \ の最長パスの頂点数) = (G \ を独立集合に分割するときの独立集合の数) というもの（と等価）です。最大のものをとってくる側と最小個数で覆う側がちょうど Dilworth の定理と逆転していることがわかると思います。こちらは Dilworth の定理に比べると証明が簡単です

*6:半順序集合の英語 partially ordered set（poset）の頭文字です

*7:こういうふうに、順序の話を先に導入して、後からグラフとつなげる、という流れのことが多い気がします？（あまり知らないので自信なし）この記事では、競プロer はグラフのほうが馴染みがある人が多いと思ったのでグラフの話を先に紹介していました

*8:これ以降、二部グラフの 2 グループを「左側」と「右側」のように呼ぶことにします

*9:入次数が 0 の頂点から始めて、辺が出ているうちは進め続ける、という感じでできます

*10:なお、 G が DAG ではない場合は G のパス被覆から H のマッチングへの対応づけはできますが、 H のマッチングから G のパス被覆への対応づけはできるとは限らないので、 \geq は成り立ちますが \leq は必ずしも成り立ちません

*11:二部グラフの最大マッチングの解法はここでは扱いませんでしたが、たとえば、最大フローに帰着させて求めることができます

*12:実際は、Dilworth の定理を証明するだけだったら \leq だけで OK です

*13:ケーニヒ と読みます

*14:逆に、増加道が存在しないマッチングは最大マッチングである、ということもいえます。証明はたとえば 二部グラフの最大マッチングと増加道 | 高校数学の美しい物語 に載っています

*15:他のパターンは「左の白と右の白」「左の白と右の黄」「左の黄と右の黄」を結ぶ辺の場合で、左の白、右の黄はすべて選ばれているので OK

*16:方針だけ書くと、頂点 i と頂点 i' を両方含む点被覆は、「頂点 i を除いても点被覆である」「頂点 i' を除いても点被覆である」のいずれかが成り立つ、ということがいえます