图论——差分约束系统2————[个人笔记1.0]

我会带着你远行 2023-06-12 11:23 38阅读 0赞

##### 一、差分约束系统： #####

在一个差分约束系统中， 线性规划矩阵A的每一行包括一个1和一个-1 ， 其他的都为0。因此，由 Ax <= b 所给出的约束条件变为m个 涉及n个变量的 差额限制条件， 每个约束条件是如下所示的简单线性不等式：
    	xj - xi <= bk

##### 二、引理： #####

设向量x = (x1,x2,x3,…xn)为差分约束系统 Ax <= b 的一个解， 设d为任意常数， 则 x+d = (x1+d, x2+d, x3+d, …xn+d) 也是该差分约束系统的一个解。

(2)证明: 对于每一个xi和xj, 我们由 (xi+d) - (xj+d) = xi- xj。 因此， 若向量x 满足 Ax <= b, 则向量 x+d 也满足该条件。

##### 三、约束图( 差分约束系统 与图的关系) #####

> (1) 在一个 Ax <= b 的约束系统中， 我们可以一个约束系统看作是一个图。 图中每个节点vi 对应n个未知变量中xi中的一个。  
> 途中每一条有向边对应着m个不等式中的一个。 约束图包含一个额外的节点v0,  
> 用来保证图中至少存在一个结点，从其出发可以到达所有其他的结点。

(2)定理：\[约束系统的解的情况\]  
给定差分约束系统Ax <= b, 设G = (V,E)是该差分约束系统所对应的约束图。如果图G不包含权重为负值的环路， 则 x = (d(v0, v1), d(v0, v2)… d(v0, vn))是该系统的一个可行解。 如果图G包含权值为**负值的环路, 则 该系统没有解**。

①如果存在负环路 ———— 无解
    ②如果不存在负环路 ———— 存在解

(3)定理的证明：

如果约束图不包含权重为负值的环路， 任意一条边（vi, vj）∈ E， 根据三角不等式  d(v0, vj) <=      d(v0, vi)+ w(vi, vj), 即d(v0, vj) - d(v0, vi) <= w(vi, vj)。 因此， 如果 设 xi= d(v0, vi), xj = d(v0, vj), 则xi   和xj满足对应边(vi, vj) 的差分约束条件 xi - xj <= w(vi, vj)。
    
    
    
    
     如果约束图包含权重为负值的环路， 则差分约束系统没有解：
    
    	设权重为负值的环路 c<v1, v2, v3, vk>这里 vk = v1。环路c对赢得约束条件：
    		x2 - x1 <= w(v1, v2)
    		x3 - x2 <= w(v3, v2)
    		.....
    		xk-1 - xk-2 <= w(xk-2, xk-1)
    		xk - xk-1 <= w(xk-1, xk)
    
        假设存在向量x 满足 上述不等式。 
    	    则, 不等式左面相加 等于0
    	    因为, c为负环路
    	    所以 不等式右之和 w(c) < 0
    	    又因为 左面 <= 右面 
    	    所以 0 <= w(c)
    	    这与 w(c) < 0 相矛盾
    	    所以无解