文章目录
 
一、常见的关系的性质
二、关系的性质示例
三、关系运算性质

 

 

 

 

 
一、常见的关系的性质
 
 

 
在 自然数集 
     
      
       
        
         N
        
        
         =
        
        
         {
        
        
         0
        
        
         ,
        
        
         1
        
        
         ,
        
        
         2
        
        
         ,
        
        
         ⋯
         
        
         }
        
       
       
        N=\{ 0, 1,2, \cdots \}
       
      
     N={0,1,2,⋯} 上 , 如下关系的性质 :
 

 

 
1. 小于等于关系 ：
 

 
小于等于关系 :
 
符号化描述 : 
     
      
       
        
         ≤
        
        
         =
        
        
         {
        
        
         <
        
        
         x
        
        
         ,
        
        
         y
        
        
         >
        
        
         ∣
        
        
         x
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         y
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         x
        
        
         ≤
        
        
         y
        
        
         }
        
       
       
        \leq = \{ <x, y> | x \in N \land y \in N \land x \leq y \}
       
      
     ≤={<x,y>∣x∈N∧y∈N∧x≤y}
 
关系性质 : 自反 , 反对称 , 传递
 

 

 
2. 大于等于关系 ：
 

 
大于等于关系 :
 
符号化描述 : 
     
      
       
        
         ≥
        
        
         =
        
        
         {
        
        
         <
        
        
         x
        
        
         ,
        
        
         y
        
        
         >
        
        
         ∣
        
        
         x
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         y
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         x
        
        
         ≥
        
        
         y
        
        
         }
        
       
       
        \geq = \{ <x, y> | x \in N \land y \in N \land x \geq y \}
       
      
     ≥={<x,y>∣x∈N∧y∈N∧x≥y}
 
关系性质 : 自反 , 反对称 , 传递
 

 

 
3. 小于关系 ：
 

 
小于关系 :
 
符号化描述 : 
     
      
       
        
         <
        
        
         =
        
        
         {
        
        
         <
        
        
         x
        
        
         ,
        
        
         y
        
        
         >
        
        
         ∣
        
        
         x
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         y
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         x
        
        
         <
        
        
         y
        
        
         }
        
       
       
        < = \{ <x, y> | x \in N \land y \in N \land x < y \}
       
      
     <={<x,y>∣x∈N∧y∈N∧x<y}
 
关系性质 : 反自反 , 反对称 , 传递
 

 

 
4. 大于关系 ：
 

 
大于关系 :
 
符号化描述 : 
     
      
       
        
         >
        
        
         =
        
        
         {
        
        
         <
        
        
         x
        
        
         ,
        
        
         y
        
        
         >
        
        
         ∣
        
        
         x
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         y
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         x
        
        
         >
        
        
         y
        
        
         }
        
       
       
        > = \{ <x, y> | x \in N \land y \in N \land x > y \}
       
      
     >={<x,y>∣x∈N∧y∈N∧x>y}
 
关系性质 : 反自反 , 反对称 , 传递
 

 

 
5. 整除关系 :
 

 
整除关系 :
 
符号化描述 : 
     
      
       
        
         ∣
        
        
         =
        
        
         {
        
        
         <
        
        
         x
        
        
         ,
        
        
         y
        
        
         >
        
        
         ∣
        
        
         x
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         y
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         x
        
        
         ∣
        
        
         y
        
        
         }
        
       
       
        | = \{ <x, y> | x \in N \land y \in N \land x | y \}
       
      
     ∣={<x,y>∣x∈N∧y∈N∧x∣y}
 
关系性质 : 反对称 , 传递
 

 
$x|y$ 中的 $|$ 符号是整除的意思 , $x$ 整除 $y$ ;
 
 
$x$ 整除 $y$ , $x$ 是除数 (分子) , $y$ 是被除数 (分母) ; $\frac{y}{x}$
 
 
$y$ 能被 $x$ 整除 , $x$ 是除数 (分子) , $y$ 是被除数 (分母) ; $\frac{y}{x}$
 
 
整除关系中 , 一定要注意 , 只能非 $0$ 整除 $0$ , $0$ 不能整除非 $0$ , 即 $0$ 只能作被除数 , 不能作除数 ;
 
 
参考 : 【集合论】二元关系 ( 特殊关系类型 | 空关系 | 恒等关系 | 全域关系 | 整除关系 | 大小关系 ) 三、 整除关系
 

 

 
6. 恒等关系 :
 

 
恒等关系 :
 
符号化描述 : 
     
      
       
        
         
          I
         
         
          N
         
        
        
         =
        
        
         {
        
        
         <
        
        
         x
        
        
         ,
        
        
         y
        
        
         >
        
        
         ∣
        
        
         x
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         y
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         x
        
        
         =
        
        
         y
        
        
         }
        
       
       
        I_N = \{ <x, y> | x \in N \land y \in N \land x = y \}
       
      
     IN​={<x,y>∣x∈N∧y∈N∧x=y}
 
关系性质 : 自反 , 对称 , 反对称 , 传递
 

 

 
7. 全域关系 :
 

 
全域关系 :
 
符号化描述 : 
     
      
       
        
         
          E
         
         
          N
         
        
        
         =
        
        
         {
        
        
         <
        
        
         x
        
        
         ,
        
        
         y
        
        
         >
        
        
         ∣
        
        
         x
        
        
         ∈
        
        
         N
        
        
         ∧
        
        
         y
        
        
         ∈
        
        
         N
        
        
         }
        
        
         =
        
        
         N
        
        
         ×
        
        
         N
        
       
       
        E_N = \{ <x, y> | x \in N \land y \in N \} = N \times N
       
      
     EN​={<x,y>∣x∈N∧y∈N}=N×N
 
关系性质 : 自反 , 对称 , 传递
 

 

 
自反 , 反对称的关系 , 称为偏序关系 ;
 

 

 

 

 
二、关系的性质示例
 
 

 
关系图关系判定 :
 
① 自反 : 关系图中所有顶点 都有环 ;
② 反自反 : 关系图中所有顶点 都没有环 ;
③ 对称 : 两个顶点之间 有 $0$ 个或 $2$ 个有向边 ;
④ 反对称 : 两个顶点之间 有 $0$ 个或 $1$ 个有向边 ;
⑤ 传递 : 前提 $a\to b,b\to c$ 不成立 默认传递 , 前提 $a\to b,b\to c$ 成立 必须满足 $a\to c$ 存在 ;
 

 

 
1. 
     
      
       
        
         
          R
         
         
          1
         
        
        
         =
        
        
         {
        
        
         <
        
        
         a
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         a
        
        
         ,
        
        
         b
        
        
         >
        
        
         ,
        
        
         <
        
        
         b
        
        
         ,
        
        
         c
        
        
         >
        
        
         ,
        
        
         <
        
        
         a
        
        
         ,
        
        
         c
        
        
         >
        
        
         }
        
       
       
        R_1 = \{ <a, a> , <a, b> , <b , c> , <a,c> \}
       
      
     R1​={<a,a>,<a,b>,<b,c>,<a,c>} :
 

 
绘制上述关系的关系图 : 反对称 , 传递
 
 
自反/反自反 : 有的顶点有环 , 有的顶点没有环 , 自反和反自反都不成立 ;
 
对称/反对称 : 顶点之间都是 $1$ 条有向边 , 顶点之间只有 $0/1$ 条边 , 是 反对称 的 ;
 
传递 : $a\to b,b\to c$ 成立 , $a\to c$ 存在 , 传递性 成立 ;
 

 

 
2. 
     
      
       
        
         
          R
         
         
          2
         
        
        
         =
        
        
         {
        
        
         <
        
        
         a
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         a
        
        
         ,
        
        
         b
        
        
         >
        
        
         ,
        
        
         <
        
        
         b
        
        
         ,
        
        
         c
        
        
         >
        
        
         ,
        
        
         <
        
        
         c
        
        
         ,
        
        
         a
        
        
         >
        
        
         }
        
       
       
        R_2 = \{ <a, a> , <a, b> , <b , c> , <c,a> \}
       
      
     R2​={<a,a>,<a,b>,<b,c>,<c,a>} :
 

 
绘制上述关系的关系图 : 反对称
 
 
自反/反自反 : 有的顶点有环 , 有的顶点没有环 , 自反和反自反都不成立 ;
 
对称/反对称 : 顶点之间都是 $1$ 条有向边 , 顶点之间只有 $0/1$ 条边 , 是 反对称 的 ;
 
传递 : $a\to b,b\to c$ 成立 , $a\to c$ 不存在 , 传递性 不成立 ;
 

 

 
3. 
     
      
       
        
         
          R
         
         
          3
         
        
        
         =
        
        
         {
        
        
         <
        
        
         a
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         b
        
        
         ,
        
        
         b
        
        
         >
        
        
         ,
        
        
         <
        
        
         a
        
        
         ,
        
        
         b
        
        
         >
        
        
         ,
        
        
         <
        
        
         b
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         c
        
        
         ,
        
        
         c
        
        
         >
        
        
         }
        
       
       
        R_3 = \{ <a, a> , <b, b> , <a,b> , <b,a> , <c,c> \}
       
      
     R3​={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>} :
 

 
绘制上述关系的关系图 : 自反 , 对称 , 传递
 
 
自反/反自反 : 所有顶点都有环 , 自反性 成立 ;
 
对称/反对称 : 顶点之间都是 $0$ 或 $2$ 条有向边 , 顶点之间只有 $0/2$ 条边 , 是 对称 的 ;
 
传递 : 传递性 成立 ;
 
前提 $a\to b,b\to a$ , 对应存在 $a\to a$
前提 $b\to a,a\to b$ , 对应存在 $b\to b$
 

 

 
4. 
     
      
       
        
         
          R
         
         
          4
         
        
        
         =
        
        
         {
        
        
         <
        
        
         a
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         a
        
        
         ,
        
        
         b
        
        
         >
        
        
         ,
        
        
         <
        
        
         b
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         c
        
        
         ,
        
        
         c
        
        
         >
        
        
         }
        
       
       
        R_4 = \{ <a, a> , <a,b> , <b,a> , <c,c> \}
       
      
     R4​={<a,a>,<a,b>,<b,a>,<c,c>} :
 

 
绘制上述关系的关系图 : 对称
 
 
自反/反自反 : 有的顶点有环 , 有的顶点没有环 , 自反和反自反都不成立 ;
 
对称/反对称 : 顶点之间都是 $0$ 或 $2$ 条有向边 , 顶点之间只有 $0/2$ 条边 , 是 对称 的 ;
 
传递 : 传递性 不成立 ;
 
前提 $a\to b,b\to a$ , 对应存在 $a\to a$
 前提 $b\to a,a\to b$ , 不存在对应的 $b\to b$ , 这里传递性不成立 ;
 

 

 
5. 
     
      
       
        
         
          R
         
         
          5
         
        
        
         =
        
        
         {
        
        
         <
        
        
         a
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         a
        
        
         ,
        
        
         b
        
        
         >
        
        
         ,
        
        
         <
        
        
         b
        
        
         ,
        
        
         b
        
        
         >
        
        
         ,
        
        
         <
        
        
         c
        
        
         ,
        
        
         c
        
        
         >
        
        
         }
        
       
       
        R_5 = \{ <a, a> , <a,b> , <b,b> , <c,c> \}
       
      
     R5​={<a,a>,<a,b>,<b,b>,<c,c>} :
 

 
绘制上述关系的关系图 : 自反 , 反对称 , 传递
 
 
自反/反自反 : 所有顶点都有环 , 自反性 成立 ;
 
对称/反对称 : 顶点之间都是 $0$ 或 $1$ 条有向边 , 顶点之间只有 $0/1$ 条边 , 是 反对称 的 ;
 
传递 : 前提不成立 , 传递性 成立 ;
 

 

 
6. 
     
      
       
        
         
          R
         
         
          6
         
        
        
         =
        
        
         {
        
        
         <
        
        
         a
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         b
        
        
         ,
        
        
         a
        
        
         >
        
        
         ,
        
        
         <
        
        
         b
        
        
         ,
        
        
         c
        
        
         >
        
        
         ,
        
        
         <
        
        
         a
        
        
         ,
        
        
         a
        
        
         >
        
        
         }
        
       
       
        R_6 = \{ <a, a> , <b,a> , <b,c> , <a,a> \}
       
      
     R6​={<a,a>,<b,a>,<b,c>,<a,a>} :
 

 
绘制上述关系的关系图 : 没有任何关系
 
 
自反/反自反 : 有的顶点有环 , 有的顶点没有环 , 自反和反自反都不成立 ;
 
对称/反对称 : 顶点之间都是 $1$ 或 $2$ 条有向边 , 顶点之间只有 $0/1$ 条边是反对称 , 顶点之间只有 $0/2$ 条边是对称 , 上述对称/反对称都不成立 ;
 
传递 : 前提 $a\to b,b\to c$ , 不存在对应的 $a\to c$ , 这里传递性不成立 ;
 

 

 

 

 
三、关系运算性质
 
 

 
讨论问题 : 指定性质的关系 之间进行运算 , 其结果的性质 ; 如 自反的两个关系 进行逆序合成运算 , 结果扔是自反的 ;
 
下图中表格的含义是 : 如 第二列 “自反” 与 第三列 “$R_1\cup R_2$” , 交叉的表格位置 , 代表 关系 $R_1$ 与关系 $R_2$ 是自反的 , 其有序对交集是否是自反的 , 如果是 $1$ , 说明是自反的 , 如果没有值 , 说明不是自反的 ;
 

 
自反
反自反
对称
反对称
传递
$R_1^{-1},R_2^{-1}$
$1$
$1$
$1$
$1$
$1$
$R_1\cup R_2^{-1}$
$1$
$1$
$1$
$R_1\cap R_2$
$1$
$1$
$1$
$1$
$1$
$R_1\circ R_2,R_2\circ R_1$
$1$
$R_1-R_2,R_2-R_1$
$1$
$1$
$1$
$\sim R_1,\sim R_2$
$1$

性质1 线性性质
 
设 $f(x)$ 和 $g(x)$ 都在 $[a, b]$ 上可积， 
 则 $\forall k_1, k_2 \in R, k_1 f(x) + k_2 g(x)$ 也可积， 且有 
 $\int _{a} ^{b} [k_1 f(x) + k_2 g(x)] \mathrm {d} x = k_1 \int _{a} ^{b} f(x) \mathrm {d} x + k_2 \int _{a} ^{b} g(x) \mathrm {d} x$
 
证明：
 
$f(x)$ 在 $[a, b]$ 上可积 $\Rightarrow \exists I_1 \in \mathbb R，$ 
 使得 $\forall \varepsilon \gt 0, \exists \delta_1 > 0$， 
 使得对于任意一种 $[a, b]$ 上的划分 $P$ 和任意 $n$ 个点 $\{ \varepsilon_i \in [x_{i - 1}, x_i]: i \in \mathbb N, 1 \le i \le n \}$ ， 
 只要 $\lambda = \max \{\Delta x_i: i \in \mathbb N, 1 \le i \le n\} \lt \delta_1,$ 
 便有 $|\sum _{i = 1} ^{n} f(\varepsilon_i)\Delta x_i - I_1| \lt \dfrac {\varepsilon} {2 (|k_1| + 1)},$ 
 $g(x)$ 在 $[a, b]$ 上可积 $\Rightarrow \exists I_2 \in \mathbb R，$ 
 使得对于上面的 $\varepsilon, \exists \delta_2 > 0$， 
 使得对于任意一种 $[a, b]$ 上的划分 $P$ 和任意 $n$ 个点 $\{ \varepsilon_i \in [x_{i - 1}, x_i]: i \in \mathbb N, 1 \le i \le n \}$ ， 
 只要 $\lambda = \max \{\Delta x_i: i \in \mathbb N, 1 \le i \le n\} \lt \delta_2,$ 
 便有 $|\sum _{i = 1} ^{n} g(\varepsilon_i)\Delta x_i - I_2| \lt \dfrac {\varepsilon} {2 (|k_2| + 1)},$ 
 取 $\delta = \min \{ \delta_1, \delta_2 \},$ 
 则对于任意一种 $[a, b]$ 上的划分 $P$ 和任意 $n$ 个点 $\{ \varepsilon_i \in [x_{i - 1}, x_i]: i \in \mathbb N, 1 \le i \le n \}$ ， 
 只要 $\lambda = \max \{\Delta x_i: i \in \mathbb N, 1 \le i \le n\} \lt \delta,$ 
 便有 $|\sum _{i = 1} ^{n} f(\varepsilon_i)\Delta x_i - I_1| \lt \dfrac {\varepsilon} {2 (|k_1| + 1)},$ 
 $|\sum _{i = 1} ^{n} g(\varepsilon_i)\Delta x_i - I_2| \lt \dfrac {\varepsilon} {2 (|k_2| + 1)},$ 
 因此 $|\sum _{i = 1} ^{n} [k_1f(\varepsilon_i) + k_2g(\varepsilon_i)] \Delta x_i - (k_1 I_1 + k_2 I_2)|$ 
 $= |k_1[\sum _{i = 1} ^{n} f(\varepsilon_i)\Delta x_i - I_1] + k_2 [\sum _{i = 1} ^{n} g(\varepsilon_i)\Delta x_i - I_2] |$ 
 $\le |k_1| |[\sum _{i = 1} ^{n} f(\varepsilon_i)\Delta x_i - I_1| + |k_2| |\sum _{i = 1} ^{n} g(\varepsilon_i)\Delta x_i - I_2|$ 
 $\le (|k_1| + 1) |[\sum _{i = 1} ^{n} f(\varepsilon_i)\Delta x_i - I_1| + (|k_2| + 1) |\sum _{i = 1} ^{n} g(\varepsilon_i)\Delta x_i - I_2|$
 
$\lt (|k_1| + 1) \dfrac {\varepsilon} {2 (|k_1| + 1)} + (|k_2| + 1) \dfrac {\varepsilon} {2 (|k_2| + 1)}$ 
 $= \dfrac {\varepsilon} {2} + \dfrac {\varepsilon} {2} = \varepsilon,$ 
 因此 $\forall k_1, k_2 \in R, k_1 f(x) + k_2 g(x)$ 也可积， 且有 
 $\int _{a} ^{b} [k_1 f(x) + k_2 g(x)] \mathrm {d} x =  k_1 I_1 + k_2 I_2 = k_1 \int _{a} ^{b} f(x) \mathrm {d} x + k_2 \int _{a} ^{b} g(x) \mathrm {d} x$
 
引理
 
闭区间上只有有限个点不为 $0$ 的有界函数必定可积，且 $\int  _{a} ^{b} f(x) \mathrm {d} x = 0$
 
证明：
 
设 函数 $f(x): [a, b] \rightarrow \mathbb R$ 在 $[a, b]$ 有界，且只在 $k  \in \mathbb N$ 个点不为 $0$， 

则 $\exists M > 0, \forall x \in [a, b], |f(x)| \lt M,$ 
 $f(x) = 0, \forall x \in [a, b] - \{x_1', x_2', \cdots x_k' \},$ 
 因此对于任意一种 $[a, b]$ 上的划分 $P$  

和任意 $n$ 个点 $\{ \varepsilon_i \in [x_{i - 1}, x_i]: i \in \mathbb N, 1 \le i \le n \}$ ， 
 最多在 $k$ 个点处函数值不为 $0$。 
 因此 $\forall \varepsilon \gt 0, \exists \delta = \dfrac {\varepsilon} {kM} > 0$， 
 使得对于任意一种 $[a, b]$ 上的划分 $P$  

和任意 $n$ 个点 $\{ \varepsilon_i \in [x_{i - 1}, x_i]: i \in \mathbb N, 1 \le i \le n \}$ ， 
 只要 $\lambda = \max \{\Delta x_i: i \in \mathbb N, 1 \le i \le n\} \lt \delta,$ 
 便有 $|\sum _{i = 1} ^{n} f(\varepsilon_i)\Delta x_i - 0|$ 
 $= |\sum _{i = 1} ^{n} f(\varepsilon_i)\Delta x_i|$ 
 $\le \sum _{i = 1} ^{n} |f(\varepsilon_i)\Delta x_i|$ 
 $\le \sum _{i = 1} ^{n} |f(\varepsilon_i)| |\Delta x_i|$ 
 $\le \delta \sum _{i = 1} ^{n} |f(\varepsilon_i)|$ 
 $\le \delta \cdot kM$ 
 $\lt \dfrac {\varepsilon} {kM} \cdot kM$ 
 $= \varepsilon$ 
 因此 $\int  _{a} ^{b} f(x) \mathrm {d} x = 0$
 
推论1
 
若函数 $f(x)$ 在 $[a, b]$ 可积，函数 $g(x)$ 在 $[a, b]$ 有界， 
 且 $f(x)$ 与 $g(x)$ 只在 $[a, b]$ 中的有限个点不相等， 
 则 $g(x)$ 在 $[a, b]$ 可积，且 $\int  _{a} ^{b} f(x) \mathrm {d} x = \int  _{a} ^{b} g(x) \mathrm {d} x$
 
证明：
 
$g(x) - f(x)$ 在 $[a, b]$ 有界，且只在 $[a, b]$ 中的有限个点不为 $0$ 。 

由引理，$g(x) - f(x)$ 在 $[a, b]$ 可积，且 $\int  _{a} ^{b} [g(x) - f(x)] \mathrm {d} x = 0$ 
 由性质1，$g(x) = [g(x) - f(x)] + f(x)$ 在 $[a, b]$ 可积， 
 且 $\int  _{a} ^{b} g(x) \mathrm {d} x = \int  _{a} ^{b} [g(x) - f(x) + f(x)] \mathrm {d} x$ 
 $= \int  _{a} ^{b} [g(x) - f(x)] \mathrm {d} x + \int  _{a} ^{b} f(x) \mathrm {d} x$ 
 $= \int  _{a} ^{b} f(x) \mathrm {d} x$
 
推论2
 
若函数 $f(x)$ 在 $[a, b]$ 可积，则 
 $\int  _{a} ^{b} [-f(x)] \mathrm {d} x =  - \int  _{a} ^{b} f(x) \mathrm {d} x$
 
证明：
 
$\int  _{a} ^{b} [-f(x)] \mathrm {d} x = \int  _{a} ^{b} (-1) \cdot f(x) \mathrm {d} x =  (-1) \int  _{a} ^{b}\cdot f(x) \mathrm {d} x =  - \int  _{a} ^{b} f(x) \mathrm {d} x$

原文地址：http://blog.csdn.net/yelbosh/article/details/7647860
 
 
什么是MST？MST就是Most Small Tree，应该就是最小生成树的意思吧，具体不是很清楚，MST性质就是最小生成树性质（以下简称MST性质），我们在看最小生成树的算法的时候，很多情况下都有关于这条性质的说明，比如，历史上最经典的Prim算法和Kruskal算法就是根据这个性质演算出来的Algorithm，MST性质的声明如下：
 

 最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。

 
 关于这个性质的证明过程，网上的资料不多，即使有，也不是很全面或者证明过程不够细节，我也是花了很长时间才弄清楚的，其实很简单，下面大家看看我是怎么证明的：
 
 为了方便下面的证明过程，预先做一些约定：
 
 
 
 ①将集合U中的顶点看作是红色顶点
 
 
 ②而V-U中的顶点看作是蓝色顶点
 
 
 ③连接红点和蓝点的边看作是橙色边
 
 
 ④权最小的橙色边称为轻边（即权重最"轻"的边）
 
 
 
 因此，MST性质中所述的边(u，v)就可简称为轻边。如下图： 
 

  
  
 
  
 
 
  用反证法来证明MST性质的正确性，假设G中任何一棵最小生成树都不含轻边(u，v)。则若T是G的一棵最小生成树，则它不含此轻边。
 
 
 
  由于T是包含了G中所有顶点的连通图，所以T中必有一条从红点u到蓝点v的路径P，而且路径P中必定包含一条橙色边(u'，v')连接红点集和蓝点集，否则u和v不可能连通。我们假设
  u-a-u'-v'-v 就是这样的一条路径，看下面的图：
 
 
 
 
 

  
  
 
  

   
 
  
 
 
   
 
 当把轻边（u，v）加入树T时，该轻边和P明显构成了一个回路。删去紫边（u'，v'）后回路亦消除，由此可得另一生成树T'。 如下：
 
 
 
 
 

  
  
 
  
 
  很显然，T'和T的差别仅仅在于T'用轻边（u，v）取代了T中权重可能更大的橙色边（u'，v'）。因为（u'，v'）的权重不可能比（u，v）小，由反证法的原理可知我们的前提条件里已经说明，所有橙色边里最小的一条边称为轻边，因为（u，v）是已经假定了的轻边，因此，必定有如下关系式：
  
 
 
 
 

  w（u，v）≤w（u'，v'）
  
 
  

   所以，
   w（T'）=w（T）+w（u，v）-w（u'，v'）   ≤  w（T）
 故此T'也是G的一颗最小生成树，但是它包含（u，v），这与假设是矛盾的，所以，MST性质成立！
 
  
 
 
 
 
 
 
 
 
 
 

  转自http://fdcwqmst.blog.163.com/blog/static/164061455201010392833100/
 

  其实个人觉得没必要这么麻烦，道理很简单，我们假设任何一棵最小代价生成树都不包含（u，v），由于树都是连通图，因而必定存在其他的边联通了顶点集U和V-U，并且这样的边必须只有一条，否则便会形成回路，因为顶点集U和V-U里面各个顶点也都是连通的，你画画看看便知道了。那么如果我们现在把轻边（u，v）加入这个树中，那么便形成回路了，那这个时候我们把原来的联通U和V-U的边去掉，这样形成的树是比原来的那棵最小生成树的代价还要小的，因为边（u，v）是连接两个点集之间的权值最小的边。所以这棵新的树才是最小生成树，但是它包含了边（u，v），所以与假设矛盾，结论成立。其实我们要证明的就是，对于两个点集，有最小的权值的边（u，v），如果该图的最小生成树不包括这条边的话，那么这棵树就 不是最小生成树。

一.影子价格
 
影子价格（shadow price），又称最优计划价格或计算价格。它是指依据一定原则确定的，能够反映投入物和产出物真实经济价值、反映市场供求状况、反映资源稀缺程度、使资源得到合理配置的价格。影子价格反映了社会经济处于某种最优状态下的资源稀缺程度和对最终产品的需求情况，有利于资源的最优配置。
 
当某种资源每增加一个单位，目标增加一定的单位，不同的资源有不同的边际贡献，这种资源的边际贡献就定义为该资源的影子价格。
 
二.互补松弛性质
 
举个栗子：
 
 
 
作者：覃含章
 链接：https://www.zhihu.com/question/27471863/answer/123244103
 来源：知乎
 
 
假设你是一个木匠，出售手工制作的木头桌子和木头椅子，简单起见，我们假定桌子的利润固定为一张10元，椅子为一把3元。生产一张桌子需要5单位木材和3单位时间，生产一把椅子需要2单位木材和1单位时间。且我们所有生产的桌子椅子都是能被卖掉的，先假设当月我们总共有200单位木材和90单位时间，现在你想要制定一个生产计划，让这个月的利润最大化。
 
那么这个生产计划问题显然可以用线性规划表达为如下，记作问题(P)：
 
 
利用线性规划的对偶理论，问题(P)的对偶问题表达为如下，记作问题(D)：
 
 
注意到原问题中变量代表生产桌子和椅子的数量，而在对偶问题中变量代表的是原材料木材和时间的价格，或者说，原问题(P)中约束(P1)和(P2)对应的影子价格。
 
原问题(P)求的是给定生产约束，如何生产能使利润最大化。对对偶问题来说，对象是即是给定商品的单位利润，如何通过合理对原材料定价来使成本最小化。而这两个问题，显然是同一个问题。
 
为了说明这一点，我们同样求解对偶问题，得到最优解是，即木材的单位影子价格是0，时间的单位影子价格是3.33，这意味着什么呢？这意味着我们有的木材份量过量了，再增加木材对我们的最优解没有影响（这也是为什么它的影子价格是0），然而我们的时间资源却非常紧俏，哪怕多增加1单位的时间我们的总体利润也能提升（我们可以多生产1/3张桌子...或者说增加3单位时间好了，就可以多生生产1张桌子...）！
 
对应原问题(P)中，对应木材资源的约束(P1)在最优条件下是松的（不等号严格成立），而(P2)则是紧的（不等号其实是等号）。我们不妨计算得到:
 
 
我们不妨计算得到,，果然如此！
 
这便是互补松弛性的定义。如果在最优条件下一个约束不等式是松的，那么这个约束对应的影子价格为0。反过来说，如果这个约束对应的影子价格严格大于0，那么这个约束不等式一定是紧的。
 
所以，当你解完问题(P)的时候你必然就知道，且(D1)是紧的（因为，注意(P)也是(D)的对偶问题），从而可以直接算出，即不用再放到solver就可以手算出(D)的解。