算法导论第二十三章习题解答

能用代码表示的都用代码表示，不能表示的写出思路，思路都没写的就是我也做不出来

“““
    1）
    反正法，设存在最小生成树T不包含边（u v），有切割（S V-S）使得 u in S and v in V-S
    则至少有边（x y）横跨此切割，以边（u v）替代（x y）得到最小切割树T‘
    由（u v）权重最小可知T‘的权重小于T，与T为最小生成树矛盾
    故假设不成立，T包含边（u v）
“““

“““
    2）
    有边 （u v） （w x） （y z） 都不在A中，权重分别为 1， 2， 3
    S包含 uwy，V-S包含vxz，则三条边都是安全的，但此切割的轻量级边只有（uv）
“““
“““
    3）
    反证法，设有分割（S V-S） ux in S and vy in V-S，
    有边（xy）（uv）w（xy） < w（u v），（xy）为轻量级边，
    有包含（xy）的T‘的权重 < 包含（u v）的T的权重故T不为最小生成树
    与已知相矛盾，故假设不成立，（uv）为轻量级边
“““
“““
    4）
    如有（ab）（bc）（ca）三条边，且w（ab）=w（bc）=w（ca）=1
    S={ab} V-S={c} 已有边 A={（ab）（bc）}为最小生成树，
    （ac）为切割的轻量级边，但A={（ab）（bc）（ca）}不为最小生成树
“““
“““
    5）
    显而易见，必然存在一条能替换掉e从而使得T的权重下降的边
“““
“““
    6）
    令每个切割的轻量级边包含在集合A中，图的最小生成树存在并包含A中所有的边
    如若不然，则对于最小生成树的切割T，可以将A中的边替换其树中横跨分割的边而使得w降低
    逆论断：若有唯一的最小生成树，则对于图的每个切割存在存在横跨该切割的唯一轻量级边
    反例 图中只有（ab）（bc）两条边，且w（ab）=w（bc）=1，有最小生成树：
       b
      / \
     a   c
    对于分割S={ac} V-S={b}则（ab）（bc）都是轻量级边，显然轻量级边不唯一
“““
“““
    7）
    若存在环，则必然可以去掉一条权重最大的边而保持连接所有节点的属性不变，
    若有负数的权重，则将所有的权重为负数的边都加入进来，可能会生成环。
“““
“““
    8）
    设T的序列L={a1a2...an} T‘的序列为L‘={b1b2...bn}
    从0到n知道遇到两个不相等ai != bi ai对应的分割在L‘中的边的权重为bj
    若 j < i则L‘不为序列，与已知矛盾
    若 j > i则可以用ai 替换 bj，权重会降低与T‘为最小生成树矛盾
    必有 ai = bi
“““
“““
    9）
    设 a in V-V‘ 在T中的叶子上。
    在G中去除a得到G‘‘，并在T中去除连接a的树边得到T‘‘ T‘‘为连通的。
    T为G的最小生成树，树中的每条边在分割中不可替换，则去掉a后T‘‘为G‘‘的最小生成树。
    逐步减少到T‘与G‘，T‘为G‘的最小生成树。    
“““

“““
    10）
    设（xy）横跨分割（S V-S） 由（xy）为T的边得出（xy）为分割的轻量级边，
    令w（xy）减小，（xy）依然为分割的轻量级边，（xy）依然为T的边，T依然为G的最小生成树。
“““

“““
    11）
    将这条边加入的T中必然会形成一个环，去掉这个环中的权重最大的边，得到一个新的最小生成树
“““

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3101  2017-01-18 14:57  chapter23\23.1-11.py

     文件       4580  2017-01-20 20:52  chapter23\23.2.py

     文件        124  2017-01-21 10:18  chapter23\23.2_1.py

     文件       2274  2017-01-21 16:57  chapter23\23.2_2.py

     文件       1142  2017-01-21 19:10  chapter23\23.2_3-8.py

     文件       1212  2017-01-21 21:48  chapter23\23_1.py

     文件       1079  2017-01-22 17:03  chapter23\23_2.py

     文件        666  2017-01-22 18:47  chapter23\23_3.py

     文件        257  2017-01-22 18:58  chapter23\23_4.py

     目录          0  2017-01-22 18:48  chapter23

----------- ---------  ---------- -----  ----

                14435                    10