《離散數學及其應用(原書第8版)》ISBN978-7-111-63687-8 第11章 11.1.3 樹的性質 節 第664頁的定理3的引申
定理3 帶有i個內點的m叉樹含有n=mi+1個頂點
見本人博文 內點定義不同的討論
如果對于一個m叉正則樹,即任意分支節點的兒子恰好有m個,公式該如何表述。
下圖繪制了一個5叉正則樹,如下所示:
根據《離散數學(第4版)》ISBN 978-7-302-61396-1內點的定義:
可以仍可以根據公式:
n=m(i+1)+1,n表述頂點個數,i表述內點數,
進行計算
m=5
i=3
n=m(i+1)+1 = 5x(3+1)+1 = 21
符合要求。
《離散數學及其應用(原書第8版)》第664頁中例9:
例9:假定某人寄出一封連環信。要求收到信的每個人再把它寄給另外4個人。有一些人這樣做了,但是其他人則沒有寄出信. 若沒有人收到超過一封信,而且若讀過信但是不寄出它的人數超過100個后,連環信就終止了,則包括第一個人在內,有多少人看過信?有多少人寄出過信?
解:這是一個4叉正則樹的問題。
將4叉正則樹定義連環信
葉子數:l = 100
m=4
i表述內點的個數
根據下列兩個公式:
公式一:n=m(i+1)+1
公式二:n=i+1+l (內點數+根+葉子數)
帶入
n=4(i+1)+1 = i+1+100
得到
i=32
n=133
因此,包括第一個人在內(圖的根),共有133人看過信,有32+1=33人寄出過信。