木の最大マッチングと貪欲法の最適性証明

はじめに

木の最大マッチングとは、直接辺で結ばれたいくつかの 頂点の組 ( 「ペア」と呼ぶ ) からなる集合であって、どの頂点も高々 つのペアに属するようなもののうち、もっともペアの多いものを言う。ここでは、木の最大マッチングが、再帰的に葉を選ぶことによって構成できることを示す。

木を辺集合としてみる

木の最大マッチングは、木の最大安定「辺」集合と言い換えられる。さて、ある木に対して、各辺に とラベル付けをしてみよう。そして木を、辺を要素とする集合とみなしてみる。このとき、頂点は「辺の部分集合」と言い換えられる。

このとき木の最大安定「辺」集合は、以下のように言い換えられる。

• 「各頂点、つまり辺の部分集合に対して、高々 つの辺だけを選べる」という制約の中で、もっとも多くの辺を選ぶ方法。

木の最大マッチング

貪欲法の言い換え

木の最大マッチングの貪欲法は次のように構成できる。

1. 葉であり、かつ隣にも頂点があるような頂点を一つ選び、隣の頂点とペアを構成する。このような頂点が存在しない場合は終了。
2. その後、ペアになった頂点とそれらに隣接する辺を木から削除し、1. に戻る。

先ほどの言い換えにおいて、葉の頂点の辺集合を無視して考えると、「辺の片方の頂点が葉である」 「辺はただ つの頂点、つまり辺の部分集合に属する」となる。

さて、明らかに、辺がただ つの部分集合に属する場合、その部分集合でその辺を選ぶことが最適である ( 各集合に対して高々 つの辺しか採用できないため ) 。したがってこの辺を選ぶ貪欲法は最大マッチングを構成できる。

例題

これでやっと、AtCoder Grand Contest 029 B - Powers of Two を安心して解ける ( 葉から貪欲にやればよい ) 。