典型タグ

一般グラフの最小重み完全matching

奇cycleを含む一般グラフで全頂点をpairにし、weighted blossomまたは重み付きTutte多項式の最小次数からperfect matchingの重みを最小化する。

この典型を扱う単元: 一般グラフの最小重み完全matching

検索別名: minimum-weight perfect matching、weighted blossom、一般グラフ最小重み完全マッチング

未知問からこの典型を見つける手掛かり

扱う対象
  • odd cycle
  • perfect matching
  • 重み付き一般グラフ
使う手掛かり
  • degree stub
  • pairing cost
  • 二部でない
  • 全頂点をpair
保つ不変量
  • Tutte polynomial degree
  • alternating forest
  • blossom dual
求めるもの
  • 最小重みperfect matching
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

関連する典型

  • 二部matching・Hall・Kőnig: 二部性を使えるaugmenting path・Hall型議論と、odd blossomを扱う一般graph完全matchingを対比する。

学習成果と学習単位

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。