1 第三章 互连网络 3
1 对于一颗K 级二叉树（根为0 级，叶为k-1 级），共有N=2^k-1 个节点，当推广至m-元树时（即每个非叶节点有m 个子节点）时，试写出总节点数N 的表达式
答： 推广至M 元树时，k 级M 元树总结点数N 的表达式为： N=1+m^1+m^2+
+m^（k-1）=(1-m^k)*1/(1-m); 3
2 二元胖树如图 3
46 所示，此时所有非根节点均有2 个父节点
如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树
试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络
答：8 输入的完全混洗三级互联网络
3 四元胖树如图 3
47 所示，试问：每个内节点有几个子节点和几个父节点
你知道那个机器使用了此种形式的胖树
答：每个内节点有4 个子节点，2 个父节点
CM-5 使用了此类胖树结构
4 试构造一个N=64 的立方环网络，并将其直径和节点度与 N=64 的超立方比较之，你的结论是什么
答：A N=64 的立方环网络,为4 立方环（将 4 维超立方每个顶点以 4 面体替代得到），直径d=9，节点度 n=4 B N=64 的超立方网络，为六维超立方（将一个立方体分为8 个小立方，以每个小立方作为简单立方体的节点，互联成 6 维超立方），直径 d=6，节点度 n=6 3
5 一个N=2^k 个节点的 de Bruijin 网络如图 3
48 所示，令ak 1 ak 2 ak 3
a1 a0 ，是一个节点的二进制表示，则该节点可达如下两个节点：ak 2 ak 3
a1 a0 0，ak 2 ak 3
a1 a0 1
试问：该网络的直径和对剖宽度是多少
答：N=2^k 个节点的 de Bruijin 网络 直径 d=k 对
