樹的中心

樹的中心是一個離心率最小的頂點。樹G中頂點X的離心率是頂點X與樹中任何其他頂點之間的最大距離。最大離心率是樹的直徑。如果樹只有一箇中心，則稱為中心樹；如果樹有多箇中心，則稱為雙中心樹。每棵樹要麼是中心樹，要麼是雙中心樹。

查詢樹的中心和雙中心的演算法

步驟1 - 從給定的樹中移除所有度為1的頂點及其關聯邊。

步驟2 - 重複步驟1，直到剩下單個頂點或由一條邊連線的兩個頂點。如果剩下單個頂點，則它是樹的中心；如果剩下由一條邊連線的兩個頂點，則它們是樹的雙中心。

問題1

找出以下樹的中心/雙中心：

解答

首先，我們將移除所有度為1的頂點及其關聯邊，得到以下樹：

再次，我們將移除所有度為1的頂點及其關聯邊，得到以下樹：

最終我們得到單個頂點'c'，演算法停止。由於只有一個頂點，這棵樹只有一箇中心'c'，這棵樹是中心樹。

問題2

找出以下樹的中心/雙中心：

解答

首先，我們將移除所有度為1的頂點及其關聯邊，得到以下樹：

再次，我們將移除所有度為1的頂點及其關聯邊，得到以下樹：

最終，我們剩下兩個頂點'c'和'd'，因此演算法停止。由於剩下兩個由一條邊連線的頂點，這棵樹的雙中心是'cd'，這棵樹是雙中心樹。

Mahesh Parahar

更新於：2019年8月23日

4K+ 瀏覽量

開啟你的職業生涯

完成課程獲得認證

開始學習