プログラミングコンテストチャレンジブック 3-6 その3

3-6 ネットワークフローの続きです。今日も時間がなくて1トピックだけ。

• 一般マッチング
  • 二人組
    • 「はーい 2人で組をつくってー」という回答者の心をえぐりかねない問題
    • 「各生徒間の友人関係が与えられるので、最大でいくつの友人同士のペアが作れるか」与えられた友人関係にひとりも友人のいない生徒がいたらどうしようって思ってしまいます
    • 生徒をノードにして友人関係を辺としたグラフにする
    • 今回は各ノードに種類がないので二部マッチングに対して一般マッチングと呼ぶ
    • tutte 行列を用いた解法
      • 無向グラフを適当に有向グラフとして、辺 e に対して xe を対応させて t(u,v) を (u,v) が適当に選んだ向きと一致してたら xuv, 逆なら -xuv, 辺が存在しなければ 0 として行列を作って、その行列の行列式が恒等的に 0 ならグラフは完全マッチングを持たない

グラフについての用語

• マッチング
  • 辺集合 M <= E で互いに端点を共有しない
• 辺カバー
  • 辺集合 F <= E で、G のどの頂点も少なくとも1つの F に含まれる辺に接続している
• 安定集合
  • 点集合 S <= V で、S のどの2点も G において隣接しない
• 点カバー
  • 点集合 S <= V で、G のどの頂点も少なくとも 1つの S に含まれる頂点に接続している

• 孤立点のないグラフに対して |最大マッチング| + |最小辺カバー| = |V|
• |最大安定集合| + |最小点カバー| = |V|