根据和译者联系后,根据提供P660页的关于内点的定义与其他国内教材不同。
《离散数学及其应用(原书第8版)》ISBN:978-7-111-63687-8内点定义如下图所示
因此
《离散数学及其应用(原书第8版)》ISBN:978-7-111-63687-8 第11章 11.1.3 树的性质 节
第664页的定理3应该表述正确。
原定理3表述如下:
定理3 带有i个内点的满m叉树含有n=mi+1个顶点。
例1:图1是满3叉树,如下所示:
图1是满3叉树,m=3,每个分支点连接3个节点
图的内点标注为红色,
内点个数i=13
根据定理3,图1的满3叉树的顶点有
n=mi+1 = 3×13+1=40
例2:图2是满2叉树,如下所示:
图2是满2叉树 m = 2,每个分支点连接2个节点
图的内点标注为红色,内点个数i=7
根据定理3,图2的满2叉树的顶点有
n=mi+1 = 2×7+1=15
如果采用《离散数学(第4版)》ISBN 978-7-302-61396-1的内点定义参考7.2 根树及其应用 7.2.1 根树及其分类 P179页
根树中入度为1,出度大于0的顶点称为内点。
在这种情况下,两本书关于内点的定义不同。公式需要调整为:
n=分支节点的总数×i+1=m ×(i+1)+1
图1表示为:
m=3
i = 12
n = m(i+1)+1 = 3x(12+1)+1 = 40
图2表示为
m=2
i=6
n=m(i+1)+1 = 2x(6+1)+1 =15
特此记录。