Add 拟阵

[Great-designer]

页面英文名

matroids

我希望能添加的内容是

许多贪心算法以拟阵（Matroids）为理论基础。另外，并非所有的贪心算法都以拟阵为基础。

对于线性无关，有性质：

一个线性无关向量组的任意子集也线性无关。

如果X和Y是两个线性无关向量组，且X的秩小于Y的秩，则必存在一个y∈Y，使得X∪{y}是一个线性无关向量组。

1935年，美国数学家哈斯勒·惠特尼（Hassler Whitney）把以上两条性质进行了抽象推广，提出了拟阵概念。

一个拟阵是一个满足如下性质的有序对M = (S, I)，其中S是非空有限集：

遗传性质：I是S的子集的一个非空族，且若B∈I，且A⊆B，则A∈I。

交换性质：若A∈I, B∈I且|A| < |B|，则存在某个元素x∈B – A，使得A∪{x}∈I。

拟阵有许多案例，例如“矩阵拟阵”和“图拟阵”等等。

线性无关向量组的矩阵构成矩阵拟阵中的I。

森林构成图拟阵中的I。

S的子集的非空族，若满足遗传性质，称为S的独立子集。

给定加权拟阵M = (S, I)，计算S的具有最大权值w(A)的独立子集 A∈I ，称为拟阵M的最优子集。

对于具有正权函数的加权拟阵，贪心算法可以返回一个最优子集。

基于拟阵的贪心算法有很多，例如最小生成树的Kruskal算法，以及单位时间任务调度问题的算法。

Prim算法也是贪心算法的例子，但是不满足拟阵的遗传性质，故不属于基于拟阵的贪心算法。

我了解到的相关参考资料有

可以添加到“杂项”。

[jifbt]

赞同！建议与线性规划合并成组合优化，放在数学部分中。还有名称最好用单数 matroid，不用用复数形式。

推荐几篇文章：

• 从拟阵基础到 Shannon 开关游戏
• Matroid intersection in simple words
• Matroid optimization
• 拟阵学习笔记

[WilliamLi0623]

@Great-designer 看看贵校课件

[Great-designer]

@Great-designer 看看贵校课件

本校课件不能随便看，只放一个局部以证实确实是这样写的。如若不信，恕本人无法提供更多证据。

[Tiphereth-A]

working on this

拟阵这个概念在组合数学和图论中比较重要，个人认为有必要介绍一下