拟阵交

拟阵交（matroid intersection）是在同一有限底集上，同时满足两个拟阵独立性约束的选择问题。典型目标是在公共独立集中选出元素最多的一个。两个约束各自有交换结构，并不意味着它们的交仍是一个拟阵。

例如，左侧人员 $u,v$ 与右侧任务 $x,y$ 之间只有三条允许指派：$a=ux,b=uy,c=vx$。人员每人至多接一个任务是一种分划拟阵，任务每项至多交给一人是另一种分划拟阵；两者同时成立恰好就是匹配。只选 $a$ 后不能直接再加边，但换成 $b,c$ 就能完成两项指派。这个例子说明单步只加不换的策略会停在非最大方案。

金色虚线 a 单独成匹配；绿色 b、c 共同给出更大的匹配。

公共独立集与上界证书

设 $M_1=(E,{ℐ}_1)$、$M_2=(E,{ℐ}_2)$ 是两个拟阵，目标为 $$max\{|I|:I\in {ℐ}_1\cap {ℐ}_2\}.$$ 公共独立集族仍有遗传性，但开头例子中的 $\{a\}$ 与 $\{b,c\}$ 违反增广公理，所以不能把交当作一个拟阵继续使用单拟阵结论。

记两者的秩函数为 $r_1,r_2$。对任意 $U\subseteq E$ 及公共独立集 $I$，把 $I$ 按是否落在 $U$ 内分开： $$|I|=|I\cap U|+|I\cap (E\setminus U)|\le r_1(U)+r_2(E\setminus U).$$ 第一项用第一拟阵的独立性，第二项用第二拟阵的独立性。于是若找到大小为 $k$ 的公共独立集，又找到 $U$ 使右端为 $k$，便已完整证明最优，不必枚举其他候选。

在上述三边例中，取 $U=\{a,b\}$。这两条边属于同一人员，所以 $r_1(U)=1$；余下只有 $c$，其第二拟阵秩为一。因此任意公共独立集大小至多二，$\{b,c\}$ 达界。

拟阵交定理进一步保证总能找到这样的证书： $$\underset{I\in {ℐ}_1\cap {ℐ}_2}{max}|I|=\underset{U\subseteq E}{min}[r_1(U)+r_2(E\setminus U)].$$ 上面的逐项分割只证明“≤”方向；一般的反向不等式需要拟阵交换路径论证，本篇引用该定理，不把一个达界算例当成其一般证明。它解释了为何除了一个好方案，还存在可核对的秩上界证书。

小底集上的完整精确求解

下面实现直接按大小递减枚举公共独立集，可用于核对小例子或新独立性判定器。输入 elements 为无重复、可哈希元素，independent1、independent2 接收一个 frozenset 并返回真假；它们应正确表示两个拟阵。返回最大公共独立集，不改写输入。程序的正确性甚至不依赖交换公理，但代价是指数枚举。

Python 3

from itertools import combinations

def matroid_intersection_small(elements, independent1, independent2):
    items = tuple(elements)
    if len(set(items)) != len(items):
        raise ValueError("elements must be distinct")
    for size in range(len(items), -1, -1):
        for choice in combinations(items, size):
            candidate = frozenset(choice)
            if independent1(candidate) and independent2(candidate):
                return candidate
    raise ValueError("the empty set must be independent")

edges = {"a": ("u", "x"), "b": ("u", "y"), "c": ("v", "x")}
def left_ok(choice):
    return len({edges[e][0] for e in choice}) == len(choice)
def right_ok(choice):
    return len({edges[e][1] for e in choice}) == len(choice)

answer = matroid_intersection_small(edges, left_ok, right_ok)
assert answer == frozenset({"b", "c"})
assert matroid_intersection_small([], left_ok, right_ok) == frozenset()
print(sorted(answer))  # ['b', 'c']

循环不变量是：开始处理大小 $s$ 时，所有大小大于 $s$ 的子集都已检查且不可行。因此第一次找到的可行集不可能被更大的可行集超过；大小为零时至少有空集，所以合法输入必然终止。共至多检查 $2^n$ 个子集；若一次判定耗时 $T(n)$，包括建立集合的成本后，时间为 $O(2^n(n+T(n)))$，额外存储为 $O(n)$ 加判定器空间。本例判定器线性扫描候选，故总体时间为 $O(n{2}^n)$。

变式。 删除边 $c$ 后，最大公共独立集大小为一。取 $U=E=\{a,b\}$，得到 $r_1(U)=1$、$r_2(\varnothing )=0$；代码会返回 $\{a\}$ 或 $\{b\}$ 中一个。证书同时说明缺少人员 $v$ 的边使第二项任务无法新增指派。

一般拟阵交存在基于交换图增广路径的多项式次独立性查询算法。路径上需要交替换出和换入元素，并选择无捷径的路径，不能把任意一串局部可换操作当成最终可行性保证。上述枚举代码刻意保留直接的正确性论证，适用范围是小底集；它的指数代价不代表拟阵交本身需要指数时间。若把第二个约束增加成多个任意拟阵约束，则也不能直接沿用两个拟阵的极小极大公式。