标签:拟阵
10 个条目
-
概念 拟阵对偶
把拟阵的每个基取补集,得到对偶拟阵;对偶的基与原拟阵的基互为补集,秩函数有 r*(A)=|A|-r(E)+r(E-A)。
2026-11-18 -
概念 贪心选择模型
选择型贪心的集合模型:按代价非减序加入可行元素;安全选择与交换论证给出正确性条件,拟阵是充分条件。
2026-11-17 -
概念 最大拟阵交
求两个拟阵的最大公共独立集;在交换图上找增广路,二部匹配是两个划分拟阵的交。
2026-11-17 -
概念 拟阵
有限集上满足遗传性与交换公理的独立集族;极大独立集称为基,秩是子集的最大独立集大小。
2026-11-17 -
概念 拟阵基定理
拟阵的所有基等势;基交换定理给出两个基之间的元素替换关系。
2026-11-17 -
概念 拟阵实例
常见拟阵模型:均匀、图、余图、双循环、线性、代数、划分、层、横截与 Gammoid,以及非拟阵例子。
2026-11-17 -
概念 二分图匹配
二分图中两两不共端点的边集;最大匹配与完美匹配可由最大流或两个划分拟阵的交刻画。
2026-11-17 -
把行列建成二分图,卡片是边;可行选择等价于伪森林,按权值降序用带环标记的并查集贪心求最大权伪森林。
2026-11-17 -
题目 分组选择
每组至多选一个带权元素,按权值降序加入;是贪心选择模型的最小入门题,也是划分拟阵的实例。
2026-11-17 -
题目 单位时间任务调度
每个任务耗时为 1、有截止期和利润,选择可准时完成的任务使利润最大;按利润降序用并查集找最晚空位。
2026-11-17