压入与重标记算法中不存在顶点v∈V-{s,t},且h(v)=h(s)证明

假设存在顶点v∈V-{s,t},且h(v)=h(s)，意味着e(v)=0（因为无法有流量进入此点）,且这个顶点一定被重标记过，根据算导引理26.15（溢出的顶点可以被压入或重标记），可知此顶点重标记前（设为v’)为溢出顶点，那么e(v’)>0。 根据压入与重标记算法，对于v∈V-{s,t},e(v)>0,当且仅当压入操作可以改变一个溢出顶点v的溢出流量,然而我们假设的顶点在重标记后溢出流量发生变化，可以断定v∉V-{s,t}，与假设矛盾，可以证明我们假设这样的顶点存在是不正确的。