建设大型网站建设中小企业管理培训课程

《离散数学及其应用（原书第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人寄出过信。