目錄

曼哈頓距離與切比雪夫距離的相互轉(zhuǎn)化

prufer序列

---

1. 曼哈頓距離 與 切比雪夫距離 的相互轉(zhuǎn)化

曼哈頓距離

|x1?x2|+|y1?y2|=max(x1?x2+y1?y2,x1?x2?y1+y2,?x1+x2+y1?y2,?x1+x2?y1+y2)|x1?x2|+|y1?y2|=max(x1?x2+y1?y2,x1?x2?y1+y2,?x1+x2+y1?y2,?x1+x2?y1+y2)
與某一個點(diǎn)的曼哈頓距離均為d的所有點(diǎn)構(gòu)成了一個以該點(diǎn)為中心的對角線長度為2d的菱形。

切比雪夫距離

max(|x1?x2|,|y1?y2|)=max(x1?x2,x1+x2,y1?y2,y1+y2)max(|x1?x2|,|y1?y2|)=max(x1?x2,x1+x2,y1?y2,y1+y2)
與某一個點(diǎn)的切比雪夫距離均為d的所有點(diǎn)構(gòu)成了一個以該點(diǎn)為中心的邊長為2d的正方形。

兩種距離之間的轉(zhuǎn)化

由于兩種等距離的形狀均為正方形，因此可以通過旋轉(zhuǎn)坐標(biāo)系來互相轉(zhuǎn)化。

(1)曼哈頓距離->切比雪夫距離

將所有的點(diǎn)做變換(x,y)(x,y)->(x+y,x?y)(x+y,x?y)。

證明

令x3=x1+y1,y3=x1?y1,x4=x2+y2,y4=x2?y2x3=x1+y1,y3=x1?y1,x4=x2+y2,y4=x2?y2
|x1?x2|+|y1?y2|=max(x1?x2+y1?y2,x1?x2?y1+y2,?x1+x2+y1?y2,?x1+x2?y1+y2)=max(x3?x4,y3?y4,?y3+y4,?x3+x4)=max(|x3?x4|,|y3?y4|)|x1?x2|+|y1?y2|=max(x1?x2+y1?y2,x1?x2?y1+y2,?x1+x2+y1?y2,?x1+x2?y1+y2)=max(x3?x4,y3?y4,?y3+y4,?x3+x4)=max(|x3?x4|,|y3?y4|)

(2)切比雪夫距離->曼哈頓距離

將所有的點(diǎn)做變換(x,y)(x,y)->(x+y2,x?y2)(x+y2,x?y2)。

證明

令x3=x1+y12,y3=x1?y12,x4=x2+y22,y4=x2?y22x3=x1+y12,y3=x1?y12,x4=x2+y22,y4=x2?y22
max(|x1?x2|,|y1?y2|)=max(x1?x2,?x1+x2,y1?y2,?y1+y2)=max(x3+y3?x4?y4,?x3?y3+x4+y4,y3?x3+y4?x4,?y3+x3?y4+x4)=|x3?x4|+|y3?y4|max(|x1?x2|,|y1?y2|)=max(x1?x2,?x1+x2,y1?y2,?y1+y2)=max(x3+y3?x4?y4,?x3?y3+x4+y4,y3?x3+y4?x4,?y3+x3?y4+x4)=|x3?x4|+|y3?y4|

---

2.prufer序列

定義

prufer序列是一顆帶編號的無根樹的編碼表示方式，一顆具有nn個節(jié)點(diǎn)的帶編號的無根樹有唯一的長為n?2n?2 的prufer序列。

因為每種帶編號的無根樹對應(yīng)唯一的prufer序列，所以prufer序列也被用作無根樹的計數(shù)。

–如下圖的無根樹的prufer序列為–

3,5,1,33,5,1,3

1.如何從一個無根樹得到prufer序列？

找樹的編號最小的葉子節(jié)點(diǎn)，然后將與葉子節(jié)點(diǎn)相連的節(jié)點(diǎn)編號加入到prufer序列中去，然后刪掉這個葉子節(jié)點(diǎn)。重復(fù)上述過程直到樹上只剩2個節(jié)點(diǎn)為止，即得到長為n?2n?2的prufer序列。

顯然prufer序列是唯一的。

2.如何從prufer序列恢復(fù)一顆無根樹？

找到prufer序列中未出現(xiàn)過的，編號最小的點(diǎn)，這個點(diǎn)即為最遠(yuǎn)一次被刪除掉的，把這個點(diǎn)與prufer序列中的第一個點(diǎn)相連，并彈出prufer中的這個點(diǎn)，重復(fù)上述操作，prufer序列處理完成后，剩余兩個點(diǎn)直接連到一起即可。

3.重要性質(zhì)

1. prufer序列中每個編號出現(xiàn)的次數(shù)+1等于該編號的點(diǎn)在無根樹中的度數(shù)。

2. nn個點(diǎn)的無向完全圖計數(shù)為n(n?2)n(n?2)

3. nn個點(diǎn)，每個點(diǎn)的度數(shù)為D1,D2,...,DnD1,D2,...,Dn，則prufer序列的種數(shù)為(n?2)!(D1?1)!(D2?1)!...(Dn?1)!(n?2)!(D1?1)!(D2?1)!...(Dn?1)!

例題

nn個點(diǎn)中，其中有mm個點(diǎn)的度數(shù)是未知的，求生成樹的種數(shù)？

記remainremain為剩余出現(xiàn)次數(shù)
remain=(n?2)?(Di1?1)?(Di2?1)?...?(Din?m?1)remain=(n?2)?(Di1?1)?(Di2?1)?...?(Din?m?1)

先把mm個點(diǎn)看成是一種點(diǎn)。
這樣答案就是(n?2)!(Di1?1)!(Di2?1)!...(Din?m?1)!remain!(n?2)!(Di1?1)!(Di2?1)!...(Din?m?1)!remain!
而實(shí)際上剩余次數(shù)remainremain里面的點(diǎn)可以隨意填，形成各種不同的排列，即答案要乘以mremainmremain

因此最終的答案就是：
(n?2)!(Di1?1)!(Di2?1)!...(Din?m?1)!remain!mremain(n?2)!(Di1?1)!(Di2?1)!...(Din?m?1)!remain!mremain

其他計數(shù)類型

1.有標(biāo)號有根樹的計數(shù)

nn?2?n=nn?1nn?2?n=nn?1

2.無標(biāo)號無根樹的計數(shù)

3.無標(biāo)號有根樹的計數(shù)

---

總結(jié)

以上是生活随笔為你收集整理的曼哈顿距离与切比雪夫距离的转化及prufer序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。