网站建设域名多少钱,长春网站建设多少钱,深圳市建筑工程交易服务,返利网一类的网站怎么做目录
曼哈顿距离与切比雪夫距离的相互转化prufer序列 1. 曼哈顿距离 与 切比雪夫距离 的相互转化
曼哈顿距离 |x1−x2||y1−y2|max(x1−x2y1−y2,x1−x2−y1y2,−x1x2y1−y2,−x1x2−y1y2)|x1−x2||y1−y2|max(x1−x2y1−y2,x1−x2−y1y2,−x1x2y1−y2,−x1x2−y1y2)|x_1 - x…目录
曼哈顿距离与切比雪夫距离的相互转化prufer序列 1. 曼哈顿距离 与 切比雪夫距离 的相互转化
曼哈顿距离
|x1−x2||y1−y2|max(x1−x2y1−y2,x1−x2−y1y2,−x1x2y1−y2,−x1x2−y1y2)|x1−x2||y1−y2|max(x1−x2y1−y2,x1−x2−y1y2,−x1x2y1−y2,−x1x2−y1y2) |x_1 - x_2| + |y_1 - y_2|
= max(x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y_2,-x_1+x_2-y_1+y_2) 与某一个点的曼哈顿距离均为d的所有点构成了一个以该点为中心的对角线长度为2d的菱形。
切比雪夫距离
max(|x1−x2|,|y1−y2|)max(x1−x2,x1x2,y1−y2,y1y2)max(|x1−x2|,|y1−y2|)max(x1−x2,x1x2,y1−y2,y1y2)max(|x_1-x_2|,|y_1-y_2|)
= max(x_1-x_2,x_1+x_2,y_1-y_2,y_1+y_2) 与某一个点的切比雪夫距离均为d的所有点构成了一个以该点为中心的边长为2d的正方形。
两种距离之间的转化
由于两种等距离的形状均为正方形因此可以通过旋转坐标系来互相转化。
(1)曼哈顿距离-切比雪夫距离
将所有的点做变换(x,y)(x,y)(x,y)-(xy,x−y)(xy,x−y)(x+y,x-y)。
证明
令x3x1y1,y3x1−y1,x4x2y2,y4x2−y2x3x1y1,y3x1−y1,x4x2y2,y4x2−y2x_3 = x_1 + y_1,y_3 = x_1-y_1,x_4 = x_2 + y_2,y_4 = x_2-y_2 |x1−x2||y1−y2|max(x1−x2y1−y2,x1−x2−y1y2,−x1x2y1−y2,−x1x2−y1y2)max(x3−x4,y3−y4,−y3y4,−x3x4)max(|x3−x4|,|y3−y4|)|x1−x2||y1−y2|max(x1−x2y1−y2,x1−x2−y1y2,−x1x2y1−y2,−x1x2−y1y2)max(x3−x4,y3−y4,−y3y4,−x3x4)max(|x3−x4|,|y3−y4|) |x_1 - x_2| + |y_1 - y_2|
= max(x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y_2,-x_1+x_2-y_1+y_2)
=max(x_3-x_4,y_3-y_4,-y_3 + y_4,-x_3+x_4) = max(|x_3-x_4|,|y_3-y_4|)
(2)切比雪夫距离-曼哈顿距离
将所有的点做变换(x,y)(x,y)(x,y)-(xy2,x−y2)(xy2,x−y2)(\frac{x+y}{2},\frac{x-y}{2})。
证明
令x3x1y12,y3x1−y12,x4x2y22,y4x2−y22x3x1y12,y3x1−y12,x4x2y22,y4x2−y22x_3 = \frac{x_1 + y_1}{2},y_3 = \frac{x_1-y_1}{2},x_4 = \frac{x_2 + y_2}{2},y_4 = \frac{x_2-y_2}{2} max(|x1−x2|,|y1−y2|)max(x1−x2,−x1x2,y1−y2,−y1y2)max(x3y3−x4−y4,−x3−y3x4y4,y3−x3y4−x4,−y3x3−y4x4)|x3−x4||y3−y4|max(|x1−x2|,|y1−y2|)max(x1−x2,−x1x2,y1−y2,−y1y2)max(x3y3−x4−y4,−x3−y3x4y4,y3−x3y4−x4,−y3x3−y4x4)|x3−x4||y3−y4|max(|x_1-x_2|,|y_1-y_2|) = max(x_1-x_2,-x_1+x_2,y_1-y_2,-y_1+y_2)
=max(x_3+y_3-x_4-y_4,-x_3-y_3+x_4+y_4,y_3-x_3+y_4-x_4,-y_3+x_3-y_4+x_4)
=|x_3-x_4| + |y_3 - y_4| 2.prufer序列
定义 prufer序列是一颗带编号的无根树的编码表示方式一颗具有nnn个节点的带编号的无根树有唯一的长为n#x2212;2" role="presentation" style="position: relative;">n−2n−2n-2 的prufer序列。 因为每种带编号的无根树对应唯一的prufer序列所以prufer序列也被用作无根树的计数。
–如下图的无根树的prufer序列为– 3,5,1,33,5,1,33,5,1,3
1.如何从一个无根树得到prufer序列
找树的编号最小的叶子节点然后将与叶子节点相连的节点编号加入到prufer序列中去然后删掉这个叶子节点。重复上述过程直到树上只剩2个节点为止即得到长为n−2n−2n-2的prufer序列。
显然prufer序列是唯一的。
2.如何从prufer序列恢复一颗无根树
找到prufer序列中未出现过的编号最小的点这个点即为最远一次被删除掉的把这个点与prufer序列中的第一个点相连并弹出prufer中的这个点重复上述操作prufer序列处理完成后剩余两个点直接连到一起即可。
3.重要性质
1. prufer序列中每个编号出现的次数1等于该编号的点在无根树中的度数。
2. nnn个点的无向完全图计数为n(n#x2212;2)" role="presentation" style="position: relative;">n(n−2)n(n−2)n^{(n-2)}
3. nnn个点，每个点的度数为D1,D2,...,Dn" role="presentation" style="position: relative;">D1,D2,...,DnD1,D2,...,DnD_1,D_2,...,D_n则prufer序列的种数为(n−2)!(D1−1)!(D2−1)!...(Dn−1)!(n−2)!(D1−1)!(D2−1)!...(Dn−1)!\frac{(n-2)!}{(D_1-1)!(D_2-1)!...(D_n-1)!}
例题
nnn个点中，其中有m" role="presentation" style="position: relative;">mmm个点的度数是未知的求生成树的种数
记remainremainremain为剩余出现次数 remain(n−2)−(Di1−1)−(Di2−1)−...−(Din−m−1)remain(n−2)−(Di1−1)−(Di2−1)−...−(Din−m−1)remain = (n - 2) - (D_{i1}-1) - (D_{i2} - 1) - ... - (D_{in-m}-1)
先把mmm个点看成是一种点。
这样答案就是(n#x2212;2)!(Di1#x2212;1)!(Di2#x2212;1)!...(Din#x2212;m#x2212;1)!remain!" role="presentation" style="position: relative;">(n−2)!(Di1−1)!(Di2−1)!...(Din−m−1)!remain!(n−2)!(Di1−1)!(Di2−1)!...(Din−m−1)!remain!\frac{(n-2)!}{(D_{i1}-1)!(D_{i2}-1)!...(D_{in-m}-1)!remain!} 而实际上剩余次数remainremainremain里面的点可以随意填形成各种不同的排列即答案要乘以mremainmremainm^{remain}
因此最终的答案就是 (n−2)!(Di1−1)!(Di2−1)!...(Din−m−1)!remain!mremain(n−2)!(Di1−1)!(Di2−1)!...(Din−m−1)!remain!mremain\frac{(n-2)!}{(D_{i1}-1)!(D_{i2}-1)!...(D_{in-m}-1)!remain!}m^{remain}
其他计数类型
1.有标号有根树的计数
nn−2∗nnn−1nn−2∗nnn−1n^{n-2}*n = n ^ {n-1}
2.无标号无根树的计数
3.无标号有根树的计数
