グラフ上の最大マッチングを端から埋める

グラフ上の最大マッチングを端から埋める

• 

• グラフ上の最大マッチングを考えた時、位数1の点は最大マッチングに含まれると考えてよい

• 位数1の点を含む辺を「端の辺」、その辺の相手方を含む辺を「次の辺」と呼ぶことにする

  • 次の辺は一般のグラフでは0本以上

• ある最大マッチングを選んだ時

  • 1: 端の辺も次の辺も未選択(もしくは次の辺が存在しない)なら、端の辺を選択することでマッチング数が1増える
    • つまりそもそも最大マッチングではなかった
  • 2: 端の辺が未選択で次の辺が選択されてる時、選択を交換することで増減しない
    • よって交換したものも最大マッチングである
  • 3: 端の辺も次の辺も選択されてるのはマッチングではない
  • 1,2から、最大マッチングの中には端の辺が選択されてるものが必ず存在する
  • なので端の辺を選択して取り除いてよい
  • 制限されたグラフではこの「端の辺の取り除き」によって新たな端の辺が現れる
    • 一般のグラフでは成り立たない
    • 木の時に成り立つ: m_solutions2019D
    • 最大値の頂点が常に位数1のグラフ: AGC029B
    • ドミノ倒し的にすべてが解決する
      • 貪欲法