插值、统计与离散辨析

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

在五条许可边中找三条无共端点边,再删一边用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 五节点加权路线:先加边权再比较候选路径、VectorPaint 三对三连图:交叉不是节点,非平面性需要证明。

方法来源:MIT Mathematics for Computer Science §12.5: matching and Hall’s theorem。

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