拟阵理论与通用贪心算法
拟阵的定义
拟阵(Matroid)一词最早于1935年被数学家Whitney使用,其是从矩阵的线性无关概念中提炼而来的,拟阵多种不同的等价定义,其基于子集系统的定义如下,第1~4定义了子集系统,拟阵是满足交换性质的子集系统:
1) 拟阵\(M\)是为二元组\((S,L)\);
2) \(S\)是有限集合;
3) \(L\)是由\(S\)的符合下述性质的子集组成的有限非空集;
4) 遗传性质:对任意\(B\in L\)与\(A\subseteq B\),都满足\(A\in L\);
5) 交换性质:对任意\(A\in L\)与\(B\in L\)。若\(|A|<|B|\),则存在\(x \in B-A\),使\(A\bigcup\{x\} \in L\);
在无向图\((V,E)\)上可定义图拟阵(Graphic Matroid),图拟阵与拟阵等价,故图拟阵也可定义拟阵:… 阅读全文