流量证据、加权平均与两色图

VectorPaint最大流最小割:先核十的可行流,再用十的割给上界

用四顶点五有向边核容量、守恒和割向,再降一条容量得到最大六的控制,不把最短路线当最大流。

画一个虚构有向网络,让“最多能送多少”同时有可行流与上界两份证据。容量是同一抽象期间的流量上限,不是边长或到达时间。仅画一条最宽路线还不够:流可以分路,但中间顶点必须守恒,且任何边都不能超过各自容量。

先列四点五边的容量清单

顶点S为源、T为汇,中间A、B;只设S到A容量七、S到B五、A到B三、A到T四、B到T六,没有其他边。建议1800×1400像素,S在左,A上中、B下中、T右,箭头、容量、流值和割各分组,先存原稿。所有容量非负,本例整数;箭头方向不能省,A到B不暗示B到A也可送三。像素布局只为可读,边画得长不表示容量大,未列连接按无边处理。

每边用流值斜杠容量标注

取流值SA七、SB三、AB三、AT四、BT六,旁注7/7、3/5、3/3、4/4、6/6。斜杠前后是流与容量,不是分数概率,更不把7/7约成一丢失容量信息。逐边核零≤流≤容量,SB还剩二容量但不能因此立即把总流再加二。源输出七加三等十,汇输入四加六等十,先核这两个总数,再检查中间节点;只核总量相同仍可能在中间凭空创造或损失流。

A与B分别核入等于出

A输入七,输出AB三加AT四为七;B输入SB三加AB三为六,输出BT六,均守恒。把两份算式贴在对应节点外,不用一条“总守恒”横跨所有点代替。流可拆成S到A到T四、S到A到B到T三、S到B到T三,三条路径合十,任何共用边按各路径贡献相加。若把三条路径容量独立取满,会重复占用BT,先核共边再谈分配。当前网络没有环流,原有流也不代表实际管路或通信测试。 最大值也不等于每条边的流都唯一。例如另一份流SA五、SB五、AB一、AT四、BT六同样逐边不超限,A入五出一加四,B入五加一出六,总值仍十。把它另存为同值分配,不改容量表或最小割,说明两个不同流可达到同一上界。不能因第一份图用了SA七就宣布所有最优解必须把SA送满,也不以某条边尚有余量判断全网还能增流;最优值与具体实现是两个不同问题。

割只加从源侧到汇侧的容量

取源侧X={S,A,B}、汇侧只{T},跨出的边为AT四与BT六,割容量十。任何可行流的值不超过任一S到T割容量,因此本图上界十,已有可行十就达最大。上界与可行缺一不能只靠漂亮粗箭头宣布最优。割是顶点划分,不是用剪刀任意画一条线碰到几根边;若有反向跨割边,不把它的容量也正加进本课有向割容量。图例明确X含S而不含T。

枚举四个源侧集合复核最小割

四顶点中固定S在源侧、T不在,A、B各有两种归属,共四割。X={S}容量7+5=12;{S,A}为5+3+4=12;{S,B}为7+6=13,AB方向从外进内不计;{S,A,B}为4+6=10。最小十与可行流一致,清单没有遗漏其他分法。注意{S,B}不是七加三加六,逆向跨割AB不能重复收费。枚举只适合当前小图,扩大网络不因能画所有顶点就有相同的手算工作量保证。

capacity: SA=7; SB=5; AB=3; AT=4; BT=6
flow:     SA=7; SB=3; AB=3; AT=4; BT=6
A: 7=3+4; B: 3+3=6; value=7+3=4+6=10
cut capacities: {S}:12; {S,A}:12; {S,B}:13; {S,A,B}:10
control BT capacity=2
control flow SA=4; SB=2; AB=0; AT=4; BT=2
control value=cut({S,A,B})=6

降BT容量后流与上界同时改

另存只把BT容量六改二的版本,原BT流六已越限,旧总十必须撤销。新流SA四、SB二、AB零、AT四、BT二,A入四出四,B入二出二,总六可行;割{S,A,B}容量四加二等六,所以新最大六。源侧总容量仍十二,证明只看源出口会高估可送量。控制不移动节点或加边,先改容量标签再重算流与割,不能保留旧7/7等数字让两版条件混用。

按方向守恒割容量的顺序排障

若总流十二却汇只能收十,先查BT或AT越限;若端点都十而A不守恒,按每节点独立修,不移动标签掩盖漏边。割算成十六时先查反向边和重复容量,不能把当前流值当割容量。保留问题版,逐边读流斜杠容量,再从S追各路径,最后核四个分割集合。网络没有给费用,不能从最大十推断最便宜方案;也不把流量最大与S到T最短路径或连接全部点的最小树当同一目标。

重开交付可行流和相等上界

保存原生图、五边清单与四割账,导出SVG或PDF并另开PNG。适应窗口核源汇箭头,放大看3/5与3/3未互换、控制BT确为2/2。重开编辑稿隐藏最优字样,独立重核每边约束与A、B守恒,再用十或六的割恢复结论。交付两版条件与未做输出待办,不只交一条高亮路线。MIT资料核网络流定义和上界定理,不表示应用内置最大流求解器、真实容量检测或工程运行认证。

相关教程与资料

VectorPaint 五节点加权路线:先加边权再比较候选路径、VectorPaint 最小连接树:先连齐五节点,再比较四边总权。

方法来源:MIT 6.854:网络流与最大流最小割。来源核非负容量、节点守恒及有向割上界。五边网络、四割枚举与降容量控制均原创,流值不是成本或实测速率。

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