NISHIO Hirokazu
[Translate]
区間はマトロイドではない
区間の集合と「いくつかの区間をオーバーラップしないように選んだもの」の対は
マトロイド
ではない
XはYより小さいが、Yから1つを選んでXにオーバーラップしないように追加することができない
これはマトロイドの交換則に反している
Tweet
Related Pages
貪欲法
マトロイド
→
dp
×
重み付き区間スケジューリング問題
×
連立1次方程式
×
最小カット
×
最大独立集合問題
×
二部グラフの最大マッチング
×
dilworthの定理
×
区間スケジューリング
×
貪欲法
×
区間スケジューリング問題
×
マトロイド
×
マトロイド交差
×
有向全域木
×
カラフル全域木
×
指数時間アルゴリズム入門
→
O(2^n)から計算量を減らす問題
→
マトロイド
×
最大最小定理
×
増加道アルゴリズム
×
マトロイド交叉交差
→
マトロイド交叉
→
マトロイド
×
分割マトロイド
×
マトロイド交叉
×
増加道アルゴリズム
×
2部グラフ
×
最大マッチング
→
2部グラフの最大マッチングは,分割マトロイド対のマトロイド交叉
→
マトロイド
→
pseudoforest
"
Engineer's way of creating knowledge
" the English version of my book is now available on
[Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from
[Scrapbox]
at
11/23/2025, 5:50:29 PM
[Edit]