目錄:
樹的直徑:
樹的直徑的性質:?
性質1:直徑的端點一定是葉子節點????????????????
性質2:任意點的最長鏈端點一定是直徑端點。
性質3:如果一棵樹有多條直徑,那么它們必然相交,且有極長連續段(可以是一個點,交點為樹的中心)
性質4:樹T1的直徑為x,y,樹T2的直徑為s,t。現有一邊u,v與兩顆樹相連,新樹的直徑端點一點是x,y,s,t中的兩個
樹的直徑求解方法:
樹的直徑的端點
樹的中心
樹的中心求解:
樹的中心兩個性質:
????????證明:
公共點公共邊的求法:
總結:
一、樹的直徑的四個基礎性質
二、樹的直徑相關求解問題
樹的直徑:
定義:樹的直徑是樹上兩點間距離的最大值。即樹中最遠的兩個節點之間的距離被稱為樹的直徑,連接這兩點的路徑被稱為樹的最長鏈。
鏈1) 5- 7 - 8 -3
鏈2) 1- 4 - 7 - 8 - 3
直徑為17
樹的直徑的性質:?
性質1:直徑的端點一定是葉子節點????????????????
? ? ? ? 證明:假設直徑s-t外存在一點p相連->s-t-p st+tp>st<sp? ?不成立
性質2:任意點的最長鏈端點一定是直徑端點。
????????證明:
性質3:如果一棵樹有多條直徑,那么它們必然相交,且有極長連續段(可以是一個點,交點為樹的中心)
????????證明:
性質4:樹T1的直徑為x,y,樹T2的直徑為s,t。現有一邊u,v與兩顆樹相連,新樹的直徑端點一點是x,y,s,t中的兩個
證明:
?????????性質4分析:
uv連接后有兩種情況
1.新直徑不過uv,即現直徑為st或為xy。2.新直徑過uv,則現直徑為
max(vs,vt)+max(ux,uy)+uv。
這兩種情況都能保證新直徑端點為x,y,s,t中的任意兩個。新直徑為以上三個中最大值。
????????連邊uv求新樹直徑最小:
引理性質4可知:
st與xy不變,此時只能減下過uv的直徑大小。以max(vs,vt)為例,要使該值最小,則v應當在樹的中心位置,這樣vs與vt越均衡。
同理u也應該在T2的樹的中心位置。
????????連邊uv求新樹直徑最大:
與前面一致,以max(vs,vt)為例,要使得該值最大,則v應當選擇直徑端點位置。
因此uv選擇各自直徑的端點位置時,直徑最大。
樹的直徑求解方法:
引理性質2:任意點的最長鏈端點一定是直徑端點。
方法:隨意找一個點x,進行dfs找到最長鏈的端點s,再以端點s做第二遍dfs,此時可以找到直徑的第二個端點t。此時端點s到t的距離就是樹的直徑。
樹的直徑的端點
通過記錄父親節點的方式能夠把直徑上的所有點全部記錄下來。
在樹中,直徑端點是常用點(假設端點為s,t),我們樹上任意一點p所能到的最大距離,只有可能是到ps或pt
找到所有點到兩個直徑端點的距離方法
法一(樸素方法):
????????求出直徑端點后,以每個點為根做dfs,找到根節點到端點的距離。
????????復雜度O(N2)。
法二(優化方法):
????????第一次從任意點出發,必然能到達直徑的一個端點s。
????????第二次從s點進行dfs找到端點t,此時記錄所有點到s的距離。
????????第三次從t點進行dfs,記錄所有點到t的距離。
????????復雜度:O(n)
樹的中心
概念:以樹的中心為根時,從該根到每個葉子節點的最長路徑最短,使得路徑和平衡。
樹的中心求解:
????????我們現在已經知道求解任意一點到兩端點的距離,即根據性質2可很輕松得到每個點能到的最長路徑。求出每個點后的路徑后,一次遍歷便可知樹的中心點。
樹的中心兩個性質:
性質1:樹的中心一定在直徑上,且趨向于中點位置
性質2:樹的中心可以有一個(單中心),也可以有兩個(雙中心)
????????證明:
引理性質2,若樹的中心p不在直徑st上,st上有一點q與直徑聯通。中心點能到的最遠距離為:
max(qs,qt)+pq,若要使得該值最小,pq應當為0,因此p在直徑上。
同時為了讓max(qs,qt)更小,樹的中心要在直徑中點處。
直徑公共點證明與求解方法
以當一顆樹存在多條直徑時,引理性質3,公共邊一定連續,因此可以直接對公共點/邊進行求解
公共點公共邊的求法:
????????找到直徑左右端點s,t,從左往右遍歷直徑上的點進行
????????dfs,如果某點r在直徑外找到一點與到右端點t距離相同,點r右邊的點一定不是公共點。
????????同理,從右往左遍歷直徑上的點進行dfs,如果某點l在直徑外找到一點與到左端點s距離相同,l左邊的點一定不是公共點。此時,l->r就是我們直徑的公共點。
????????因此我們只需要找到公共點邊界l,r即可。使得l盡可能靠右,r盡可能靠左。