# VectorPaint二部图匹配：交替路重配三项任务，局部邻域不足就无解

语言：zh-CN
原文：[VectorPaint二部图匹配：交替路重配三项任务，局部邻域不足就无解](<https://allluckly.cn/guides/vectorpaint-bipartite-matching-alternating-path-hall-obstruction/>)
中文：[中文 HTML](<https://allluckly.cn/guides/vectorpaint-bipartite-matching-alternating-path-hall-obstruction/>)
English: [English HTML](<https://allluckly.cn/en/guides/vectorpaint-bipartite-matching-alternating-path-hall-obstruction/>)
发布于: 2026-11-17T00:00:00+08:00
内容更新于: 2026-11-17T00:00:00+08:00
署名：Bison

在五条许可边中找三条无共端点边，再删一边用Hall条件说明无法完美匹配。

给三个虚构对象和三项任务画许可二部图，匹配只能从已有边中选，且不能重复使用任一端点。先从一个卡住的局部选择沿交替路重配，再用删边对照说明左右数量相等也未必有完美匹配。图是手工关系示意，不假设应用内置自动排班或图论求解器。

## 固定两侧集合和五条许可边

左侧A、B、C，右侧1、2、3；边仅有A1、A2、B1、C2、C3，共五条，不因想完成任务而临时增加B2。图本身无向，边表示允许配对，不是先后依赖或实际传送方向。匹配要求所选任意两边不共端点；完美匹配覆盖全部六顶点，本例左右各三时需三条。先把许可表保存，分开节点、全部边、当前选择与搜索箭头层。对象和任务均抽象，不含真实人的能力判断、优先级或成本，后面也不把边长作为最优目标。

## 先画许可图再强调初始两边

建议1800×1500画布，A、B、C在(400,350)、(400,750)、(400,1150)，右侧1、2、3在(1400,350)、(1400,750)、(1400,1150)。先画五条细边，再用实线强调M0={A1,C2}，B与3未匹配。A2与B1在画面交叉处不加点，那不是第七顶点，匹配只看既定端点。当前两边不共端点所以有效，但还不完美；不要将“暂时选不到B的空闲邻点”直接等同不存在完美解。所有颜色之外再配线型，便于黑白阅读。

## 交替走许可未选边和已选边

从未匹配B出发，沿B1到任务1，再逆着当前A1到A，沿未选A2到2，再沿当前C2到C，最后沿未选C3到自由任务3。路径为B—1—A—2—C—3，五边按未选、已选、未选、已选、未选交替。方向箭头只说明搜索走法，不能被当原图新增有向边。每一步都必须在原许可表内，终点要是未匹配右点，不能走到已占点便停止宣布增广。先逐边核身份再改任何选择，防止把整条路径都加成同时占用的五个配对。 五步路上原未选边三条、已选边两条，翻转净增加一条，仍须检查端点唯一。若仅把B1加进原两边，会让任务一同时归A和B；真正修复必须连同A2、C3的重新分配完成，不能把路径箭头误当许可已经自动更新。

```
left={A,B,C}; right={1,2,3}
E={A1,A2,B1,C2,C3}
M0={A1,C2}
alternating path: B-1-A-2-C-3
remove={A1,C2}; add={B1,A2,C3}
M1={A2,B1,C3}
after deleting A2: S={A,B}; N(S)={1}; 1<2
```

## 翻转路径成员得到三边完美匹配

移除旧选择A1与C2，加入B1、A2、C3，得到M1={A2,B1,C3}，从两边增加到三边。逐个读A接2、B接1、C接3，左右六顶点都恰好出现一次；交叉线仍不产生冲突，只有共端点才冲突。这里B只能接1，继而A要接2、C要接3，也可直接验证这份完美匹配唯一，但不说任何二部图都有唯一解。旧稿与新稿并排保存，许可边不变，变化的是选择集合，不把未选边从底层永久删除。

## Hall条件检查所有左侧子集的邻域

Hall条件说有限二部图能覆盖全部左点，当且仅当每个左子集S的邻点数至少为|S|。本例单点邻域大小A为二、B为一、C为二；两点子集AB为二、AC为三、BC为三；三点ABC为三，七个非空子集均满足。空集自动满足，不是漏检查。这里两侧同大，覆盖左边也覆盖右边，成为完美匹配；一般左右不等时要保留“覆盖左点”的原话。邻点是去重后的不同任务，不能把A1与B1各算一次从而把任务1重复计数。 具体邻域可写N(AB)={1,2}，N(AC)=N(BC)={1,2,3}，全集邻域也是{1,2,3}。逐项写集合比只报七个大小更容易发现重计；集合大括号内的顺序不影响数量，重复任务编号只保留一次。

## 删A2后的局部障碍不能靠重排图形修复

另存故障图只删许可A2，A与B都只剩邻点1。取S={A,B}，|S|=2却|N(S)|=1，违反Hall条件，因此不可能覆盖全部左点，最多匹配两边。例如A1与C3有效，但B仍无去处。左右仍三比三，所有节点也都有至少一个邻点，说明只检查总数或没有孤立点都不够。把删边差异明显标出，不能把A挪到任务2旁边就当获得许可，更不能悄悄加回边后声称反例原本有解。无解属于约束，而不是绘图位置不美观。

## 按许可、共端点和邻域去重排障

三边选出却无效，先看是否某任务被两对象共用；路径翻转后只剩两边，查是否少加或多删一个交替成员；删边反例仍被判有解，核是否底层A2没有真正取消。交叉线误认节点时去掉多余点，不移动端点改原图。每次只修一个副本问题，重数五条原边或四条删边版边，再查选择与邻域集合。搜索箭头层不应改变许可表，应用中的对齐和分组也不执行Hall检验或自动求匹配，结论须来自外部有限模型。

## 重开交付许可图、翻转与障碍证据

保存原生稿，导出SVG或PDF另开，核M0两边、五步交替路、M1三边与删A2反例分框明确，S和N(S)数量可读。适应窗口看配对线型，放大确认交叉点没有多余圆点。重开可编辑文件让许可与选择独立修改，交付全部边表、七子集检查和无解子集，不只交三条漂亮连线。未执行的导出重开留待做，结果不代表真实人员安排、成本最优或应用具备自动匹配算法，也不以一次成功泛化所有图的可解性。

## 相关教程与资料

[VectorPaint 五节点加权路线：先加边权再比较候选路径](<https://allluckly.cn/guides/vectorpaint-five-node-weighted-routes/>)、[VectorPaint 三对三连图：交叉不是节点，非平面性需要证明](<https://allluckly.cn/guides/vectorpaint-complete-bipartite-three-by-three-nonplanarity/>)。

方法来源：[MIT Mathematics for Computer Science §12.5: matching and Hall’s theorem](<https://courses.csail.mit.edu/6.042/spring18/mcs.pdf>)。

版本与操作范围：2026年11月17日核[VectorPaint官方商店](<https://apps.apple.com/cn/app/id1587272880>)与[Apple公开查询](<https://itunes.apple.com/lookup?id=1587272880&country=cn&entity=software&timestamp=20261117-vectorpaint>)，公开1.0.8，最低iOS / iPadOS 17.0。使用已公开的形状、钢笔、贝塞尔节点、网格辅助线、对齐、图层分组、文字和保存输出手工绘图；入口按安装版本实际可见为准。计算、定义与复算在应用外准备，不推断内置公式、统计或图论求解能力。原生稿保留可编辑结构，SVG、PDF、PNG各按需要阅读检查，含导入位图的SVG或PDF不自动成为全矢量。画布与样本为原创教学设定，未执行真机或实物测量，未做的操作明确待做。

