划分拟阵

设e是一个非空有限集合，E₁，E₂，…，Em是E上的一个划分，di是一个正整数。如果I= {X⊆E：|X∩Ei|≤di，1≤i≤m}，则称M(E，I)是一个划分拟阵(partition matroid)。1

基本介绍划分拟阵是一种组合构形，它是由在有限集E={e1，e2，…，en}上的划分π导出的拟阵M。

若划分π把E分割为划分块B1，B2，…，Bm，并相应地设定非负整数d1，d2，…，dm，则E的子集I为划分拟阵的独立集，当且仅当对于i=1，2，…，m，均有|I∩Bi|≤di。

例如对于有向图G=(V，A)，A的子集I为这样一类集合：I中没有两条边同指向一个节点，以这样的I为独立集可得一划分拟阵，相应地，J为A的这样一类集合：J中没有两条边始于同一节点，以这样的J为独立集可得另一划分拟阵2。

举例说明例1 设E是一个有限集，∏是E的一个划分，即∏={E₁，E₂，…Ep}为E的不相交子集的集合，并且覆盖E。E的一个子集I称为是独立的(I∈F)，当且仅当I中任何两个元素不在∏的同一个集合里，即对一切j=1，2，…，p，|I∩Ej|≤1。则M∏=(E，F)为一个拟阵，并称其为划分拟阵3。

要证明M∏是一个拟阵，只要证明它有明确定义的秩函数即可。令J(A)={j≤p：Ej∩A≠∅)，读者容易验证，r(A)=|J(A)|是满足要求的秩函数。事实上，对于E的任一个子集A，我们可构造A的极大独立子集如下：对于使Ej∩A≠∅的每一个Ej，我们在Ej中选取A的一个元素，那么所选取的元素集合，就是A的一个极大独立集。例如，若E={e1，…，e8}，∏=，那么在M∏中的秩为3，A的极大独立集为，A的支撑

对每一个j，集合Ej中任意两个元素就构成M∏的一个圈。因此，{e2，e3}和{e6，e8}都是M∏的圈。

例2 给定一个有向图(V，A)，对每一孤a∈A有一个权w(a)≥0。希望找出A的一个最大权的子集B，使得B中任何两条弧都没有公共的终点。这是关于子集系统(A，B)的一个组合优化问题，其中A的一个子集B∈B，当且仅当B中任何两条弧都没有公共的终点。这一问题看起来很象无向图的匹配同题，但是它比匹配问题容易得多。例如在图1中，选取进入v1的弧时，只要挑选一个最大权的即可。因为选取进入一个点的任何一条弧，对于选取进入其它点的弧没有影响，故greedy算法能得到该问题的最优解。

例2中的子集系统，是划分拟阵的另一个例子。在图1上的有向图D中，设B是D中弧的一个集合，若B中任何两条弧都不指向同一个节点，则称B为独立集。这就等价于把D的弧进行划分，使得指向同一节点vj的弧之集合定义为Ej。在这个例子中，下述定义的∏为D的弧集的一个划分：

因此，这个系统是一个划分拟阵M∏(并称其为有向图D的入孤划分拟阵)，从而greedy算法能求例2的解是十分自然的了3。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学