# 编者信息 熊荣川 明湖实验室 xiongrongchuan@126.com http://blog.sciencenet.cn/u/Bearjazz Median-joining networks The median-joining network method begins by combining the MINIMUM-SPANNING TREES (MSTs) within a single network. With a parsimony criterion, median vectors (which represent MISSING INTERMEDIATES) are added to the network. Median-joining networks can handle large data sets and multistate characters. It is an exceptionally fast method that can analyze thousands of haplotypes in a reasonable amount of time and can also be applied to amino acid sequences. However, it requires the absence of recombination, which restricts the application of this method at the population level. 中间连接网 中间连接网络方法首先将最小生成树（ MST ）组合到单个网络中。用简约的标准，中值向量（代表缺失的中间物）被添加到网络中。中间连接网络可以处理大数据集和多状态字符。这是一种非常快速的方法，可以在合理的时间内分析数千个单倍型，也可以应用于氨基酸序列。然而，它要求不存在重组，这限制了该方法在群体层面的应用。 Posada D , Crandall K A . Intraspecific gene genealogies: trees grafting into networks . Trends in Ecology and Evolution, 2001, 16(1):0-45.
（1） 定义在一棵树里添加一条边，并在产生的圈里删除一条边叫做一次操作。（也就是说换掉一条边并且保证结果是树），则树 A 和 B 是无向图的两个生成树，则 A 可以通过若干次操作变成 B 。 证：把树看作边的集合，如果 B 中有一条 A 没有的边，则把这条边加到 A 上， A 产生一个圈中至少有一条是 B 中没有的边，把这条边删掉，则 A 仍然是生成树， A,B 集合相同的边多了一条，重复这个过程直到 A B 包含的边相同。 注：这个命题比较容易证，它告诉我们任何两棵生成树都可以通过不断换边得到。（重要的是换边的过程中始终保持是树。） 可以通过若干次操作，这个可以并没有特殊的含义，也就是说我们可以随便加一条 B 有而 A 没有的边，总可以找到一条合适的边删掉。 （2） 把一个连通无向图的生成树边按权值递增排序，称排好序的边权列表为有序边权列表，则任意两棵最小生成树的有序边权列表是相同的。（算法导论 23.1-8 ） 证：设最小生成树有 n 条边，任意两棵最小生成树分别称为 A, B, 如果 e 是一条边，用 w(e) 表示该边的权值。 A 的边按权值递增排序后为 a 1 , a 2 , a n w(a 1 ) w(a 2 ) w(a n ) B 的边按权值递增排序后为 b 1 , b 2 , b n w(b 1 ) w(b 2 ) w(b n ) 设 i 是两个边列表中，第一次出现不同边的位置， a i b i 不妨设 w(a i ) w(b i ) 情形 1 如果树 A 中包含边 b i ，则一定有 ji 使得 b i =a j , 事实上 , 这时有 w(b i )=w(a j ) w(a i ) w(b i ) 故 w(b i )=w(a j )=w(a i ) ，在树 A 的边列表中交换边 a i 和 a j 的位置并不会影响树 A 的边权有序列表，两棵树在第 i 个位置的边变成同一条边。 情形 2 树 A 中并不包含边 b i ，则把 b i 加到树 A 上，形成一个圈，由于 A 是最小生成树，这个圈里任意一条边的权值都不大于 w(b i ) ，另外，这个圈里存在边 a j 不在树 B 中。因此，有 w(a j ) w(b i ) ，且 ji ( 因为 a j 不在 B 中 ) 。于是，有 w(b i ) w(a i ) w(a j ) w(b i ) ，因此 w(a i )= w(a j ) = w(b i ) 。那么在树 A 中把 a j 换成 b i 仍然保持它是一棵最小生成树，并不会影响树 A 的边权有序列表，并且转换成情形 1 。 注：这个命题说明，如果无向图的边权都不相同，则最小生成树是唯一的。但是其逆命题不成立。即如果无向图的最小生成树唯一，则无向图的边权是可能有相同的。例子，比如原图本身就是一棵树，并且有两条边的边权相等。 （3） A,B 是同一个无向连通图的两棵不同的最小生成树，则 A 可以通过若干次（ 1 ）中定义的换边操作，并且保证每次结果仍然是最小生成树，最终转换成 B 。 证：做法和（ 2 ）类似，也是要找一条树 B 有但是树 A 没有的边。事实上（ 2 ）的证明过程情形 2 的部分，就已经找到这样一条边了。按照（ 2 ）中给出的方法，就可以把 A 转换成 B 。 注：上述证明过程证得了和（ 1 ）中类似的结论，但是此时的可以暂时有特殊 的含义，至少证明中需要以一定的规则选边。这显得有点不美观。那么，是否可以任意选边呢？考虑任意选边造成的后果：把任意一条 B 有而 A 没有的边加入到 A ，由于 A 是最小生成树，所以形成的圈里所有的边的权值都不大于新加的边，那么如果这个圈里没有其他的这种权值的边，换句话说，如果这个圈里的这条边是唯一权值最大的边怎么办呢？或者，如果这个圈里所有和这条边权值相等的边都也在 B 中，那么该如何保证换边后， A 和 B 相同的边数增多一条呢？下面证明，这些情况不可能出现。 （4） 一个连通无向图 G, 不会有一棵最小生成树包含 G 的一个圈中全部最大权值的边。 证：设图的节点集合是 V 。反证，假设有一棵最小生成树 T 包含 G 中某个圈的全部权值最大的边，设其中一条边是 e, 则在树中删掉边 e ， T-e 是不连通的，它把节点分成了两部分（连通分量）， A 和 B=V-A 。在原图 G 中，这条边在一个圈 C 里，且在 C 中权值是最大的。则 (C-e) 是 G 中一条路，这条路中有节点在 A 中，也有节点在 B 中，因此必然有一条边 e ，它一端在 A 中，一端在 B 中 , 显然它不在 T-e 中。于是把 e 加入到 T-e 中，这样形成的是一棵树 T 。（ |V|-1 条边的连通图显然是树），而由于 w(e)w(e) ，有 w(T)w(T) ，与 T 是最小生成树矛盾。 注：特别地，如果一个圈中权值最大的边唯一，则最小生成树不包含这条边。 （算法导论上习题 23.1-5 要证明：如果一条边是一个圈中权值最大的边，一定有一棵最小生成树不包含它。由这个结论可以立刻得出。当圈中最大权值的边唯一时，算法导论上这个命题稍弱。） 至此证明了任何两棵不同的最小生成树 A,B ，可以随意选一条 B 有而 A 没有的边，添加到 A 上，由（ 4 ）的结论，形成的圈里，至少有一条边和这条新加的边权值相同 , 并且它不在 B 中，删掉它。这样可以最终把 A 转化成 B 。 （5） 对于一个连通无向图的生成树，只考虑它的边权，形成的有序边权列表中，最小生成树是有序边权列表字典序最小的。（字典序就是通常的定义，两个序列 A,B 的字典序相同当且仅当 A=B 。否则，序列 A,B 出现最早位置的不相等的元素时，如果序列 A 的该位置元素更小，则序列 A 字典序小，反之，则序列 B 的字典序更小。如果直到一个序列结束都没有这样的位置，则较短的序列字典序小）。 证：设 A 是一棵最小生成树，而 B 是不是一棵最小生成树。利用 (2) 的结论，因为任何最小生成树的有序边权列表是相同的，所以可以用 Krusal 算法产生的最小生成树的有序边权列表。 Krusal 算法的优点是按边权顺序加边，并且当边权相等时，只要不形成圈，加哪条边都可以形成最小生成树。把 B 的边都按递增顺序排序： B 的边按权值递增排序后为 b 1 , b 2 , b n w(b 1 ) w(b 2 ) w(b n ) 用 Krusal 算法求原图的一棵最小生成树， 具体地，加第 i 条边时 (1 i n), 如果对该加的边 e ，有 w(e)=w(b i ), 则选择 b i 代替 e 加入。不可能出现 w(e)w(b i ), 因为 Krusal 算法是按边权由小到大考虑加边的，如果出现这种情况，说明，选择 b i 加入是不合法的会形成圈，而此时的图是树 B 的子图，这与 B 是树矛盾。 注：有了（ 2 ）的结论，结合 Krusal 算法的过程，知道 Krusal 算法加边的顺序构成的边权列表就是一个有序边权列表。于是，只考虑有序边权列表时，可以用 Krusal 算法产生的特殊的最小生成树代替任何一棵最小生成树。 如果一棵树是最小生成树，则对它采取一次（ 1 ）中的操作，显然，它的总权值不减。那么它的逆命题是不是成立？也就是如果说一棵生成树，对它采取一次（ 1 ）中的操作后，它的总权值不减，它是否是最小生成树？再换句话说，一棵非最小生成树，是否一定可以找到一条边进行（ 1 ）中的操作后，总权值会减小？这个命题看起来是显然的，但是是否有可能一棵非最小生成树当前无论怎样采取（ 1 ）中的操作都会造成总权值暂时的增大，而至少要操作两次，才能把权值降低呢？答案是不会的。 （6） 一棵树不是最小生成树，则一定存在一个（ 1 ）中描述的操作，使得操作之后，它的总权值减小。 证：设 A 不是最小生成树， A 的边按权值递增排序后为 a 1 , a 2 , a n w(a 1 ) w(a 2 ) w(a n ) 。利用 Krusal 算法，加第 i 条边时 (1 i n), 如果对该加的边 e i ，有 w(e i )=w(a i ), 则选择 a i 代替 e i 加入。直到第 j 次时 (1 j n) ，有 w(e j )w (a j ), 则仍加入 e j , 自此后仍执行普通的 Krusal 算法（即任意处理权值相同的边），这样生成的最小生成树 E ，有 w(e j )w( a j ) 且对所有 1 ij 有 e i =a i ，由于权值递增关系， e j 不在 A 中，那考虑把 e j 加入到 A 中形成的圈，圈里其他任意的边 a x , 若 w(a x ) w(e j )w (a j ), 则有 xj ，于是这些边是在第 j 步之前和 Krusal 算法一样加入的。因此，圈里至少有一条边 a y 满足 w(a y ) w (a j )w(e j ) （ y jx ） , 于是删除 a y 可以让 A 的总权值减小。 注：可见确实有这样的操作。于是立刻得出以下结论： （7） 一棵生成树不是最小生成树，则一定存在（ 1 ）中的操作，不断进行把它转换成一棵最小生成树，而且每次操作后权树的总权值都会减小。 证：由（ 6 ）知，存在一个这样的操作，任选一个这样的操作，总权值会减小。这样不断地进行下去，因为不同的生成树的个数是有限的，所以总权值不可能一直减小下去，也不可能无限逼近与一个常数，最终可以使其变成一棵最小生成树。 注：由此可知，这种操作也是任意选边的，并没有特殊性。如果把一个图的所有生成树看作节点，把对每个生成树进行一次（ 1 ）中定义操作看作形成的树作为它的邻居。 那么综合上述结论：形成的图是个无向连通图。任何局部最优解也是全局最优解 ( 只进行一次操作不能减小总权值，则是最小生成树，可以随意从任何一个非最优点，保持权值减小地逐步达到最优点 ) 。 （8） 如果一棵生成树，任何边都在某棵最小生成树上，则它不一定是最小生成树。 反例：考虑一个长为 2 ，宽为 1 的矩形。构造一个无向图，节点就是矩形顶点，边就是矩形的边，边权就是矩形边长。显然，原图有两棵最小生成树（两宽与一长），所有边都在某棵最小生成树上，但是有两棵生成树不是最小生成树（两长与一宽）。
标签: 最小生成树
