http://www.matrix67.com/blog/archives/5418#more-5418
在一棵樹中，任意兩個頂點之間的路徑都是唯一的。如果一棵樹有 n 個頂點，那么這棵樹總共會有 n(n-1)/2 條路徑（每兩個頂點都會確定出一條路徑來）。 1975 年， John Leech 提出了這么一個問題：有多少頂點數(shù)為 n 且邊上帶權(quán)的樹，使得圖中所有 n(n-1)/2 條路徑的權(quán)值之和正好是 1, 2, …, n(n-1)/2 ？Leech 本人給出了五個這樣的例子，其中四個如下圖所示，頂點數(shù) n 分別為 2 、 3 、 4 、 4 。第五棵滿足要求的樹擁有 6 個頂點，把它找出來將會是一個不小的挑戰(zhàn)，感興趣的讀者不妨嘗試一下，本文最后會公布答案。 Leech 注意到了 n = 5 時是無解的，但卻并沒有給出一個解釋。
1977 年， Herbert Taylor 給出了一個非常漂亮的解釋：如果一棵樹滿足上述要求，那么頂點數(shù) n 一定是形如 m2 或者 m2 + 2 的數(shù)。讓我們來看一看這個精妙的證明。
給定一棵樹后，首先按照下述原則對所有頂點進行紅藍二染色：如果某條邊的權(quán)值為偶數(shù)，則兩端的頂點同色；如果某條邊的權(quán)值為奇數(shù)，則兩端的頂點異色。這是總能辦到的，比如我們可以先隨便選一個頂點，把它染成紅色，然后從這個頂點出發(fā)，按照規(guī)則一點一點地推出其他頂點的顏色。由于整個圖是一棵樹，圖中沒有回路，因此往外推理的過程中不會走回已經(jīng)染過色的地方，因而不會有矛盾產(chǎn)生。如果用 r 來表示所有紅色頂點的數(shù)目，用 b 來表示所有藍色頂點的數(shù)目，則 r + b = n 。
注意到，如果一條路徑的權(quán)值之和為奇數(shù)，就說明這條路中有奇數(shù)條權(quán)值為奇數(shù)的邊，也就說明沿著這條路徑行走的過程中，頂點的顏色改變了奇數(shù)次。因此，兩個頂點之間的路徑權(quán)值之和為奇數(shù)，當且僅當這兩個頂點是異色的。這說明，權(quán)值之和為奇數(shù)的路徑一共有 rb 條。
如果所有 n(n-1)/2 條路徑的權(quán)值之和依次是 1, 2, …, n(n-1)/2 ，那么當 n(n-1)/2 是偶數(shù)的時候，權(quán)值之和為奇數(shù)的路徑應該有 (n(n-1)/2)/2 條；當 n(n-1)/2 是奇數(shù)的時候，權(quán)值之和為奇數(shù)的路徑應該有 (n(n-1)/2 + 1)/2 條。
在前一種情況中， rb = (n(n-1)/2)/2 ，即 4rb = n(n-1) 。于是：
n = n2 - 4rb
= (r + b)2 - 4rb
= r2 + b2 + 2rb - 4rb
= r2 + b2 - 2rb
= (r - b)2
在后一種情況中， rb = (n(n-1)/2 + 1)/2 ，即 2 · (2rb - 1) = n(n-1)。于是：
n = n2 - 4rb + 2
= (r + b)2 - 4rb + 2
= r2 + b2 + 2rb - 4rb + 2
= r2 + b2 - 2rb + 2
= (r - b)2 + 2
由于數(shù)字 5 既不是一個平方數(shù)，也不具有平方數(shù)加 2 的形式，因而 n = 5 是無解的。下圖則是 Leech 找到的那個 n = 6 時的解：
有趣的是，目前除了 Leech 本人找到的這五個解以外，還沒有人找到任何新的解。人們猜想 Leech 樹的數(shù)目是有限的，但目前還沒有人證明這一點。
參考資料：http://www.cut-the-knot.org/arithmetic/combinatorics/LeechTrees.shtml
聯(lián)系客服
