首页/二分图匹配model.bipartite-matching 页面信息 二分图匹配二分图中两两不共端点的边集;最大匹配与完美匹配可由最大流或两个划分拟阵的交刻画。标签 图论 / 二分图 / 匹配 / 网络流 / 拟阵模型设 𝐺=(𝐿,𝑅,𝐸) 是 二分图。若 𝑀⊆𝐸 中任意两条边没有公共端点,则称 𝑀 是匹配。|𝑀| 为匹配大小;大小最大的称为最大匹配,覆盖全部顶点的称为完美匹配。结构整数最大流可直接求最大匹配:源点向 𝐿 连容量 1,原边容量 1,𝑅 向汇点连容量 1;最大流值即最大匹配大小。把 𝐸 作为底集,按左端点和右端点分别作容量为 1 的划分拟阵,匹配恰为两个拟阵的公共独立集。构造与证明见 最大拟阵交。一般图匹配不能写成两个端点划分拟阵的交。