一個簡單的數學問題(tree的應用)

國小的時候，班導師常常有很多事情要跟學生家長聯繫，比如說臨時停課...在我國小的時候，通訊軟體還沒出現(甚至連智慧型手機都沒有)所以老師就必須一個一個打電話。

事實上，聰明一點的人就會想透過已經知道訊息的家長來幫忙傳遞訊息，如果我們假設一個家長在10分鐘內可以連絡班上3位同學的家長(當然，我們忽略那些難以聯繫的家長、還有不幫忙傳遞訊息的家長)如果班上有40人，大家很容易找到全班家長都知道訊息的最短時間是找等比級數的解，也就是(3^n-1)/(3-1) = 40的解，答案是4，也就是40分鐘。

在這邊提供一個簡單的證明，如果我們把家長還有老師想成是一堆點(vertex)，然後把有互相聯繫的家長(也就是點)連在一起(這就形成了邊 edge)。方便起見，我們把和老師聯繫的家長做編碼，我們因此可以得到像下面的圖。

像這樣的圖有一個名字-樹(tree)，一棵樹有根(root，在這個例子就是指老師)、有葉子(leaf，在這邊就是指最後被告知的家長)、有樹幹(這邊用的是詞彙是internal vertex，在例子裡面就是有幫忙傳遞訊息的家長)。在這棵樹當中，每個家長都剛好都傳給另外3個家長，這樣的樹就稱作是三元樹(3-nary tree)

證明其實很簡單，包含老師總共有40個點，所以至少有(40-1)/3=13層(level)。一「層」在這個例子裏面就是代表10分鐘，所以最短時間就是有多少層(單位時間)。

樹其實還有很多應用，像是用最少的次數測試一堆硬幣中的假硬幣，在這邊提供一個簡單的應用。