一般グラフの最小重み完全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を対比する。
学習成果と学習単位
一般グラフの最小重み完全matchingをweighted blossomまたは重み付きTutte多項式へ帰着し、存在判定だけでなく最小重みまで求められる。
一般グラフの最小重み完全matchingで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。