习题解答并行计算国家高性能计算中心（合肥）
国家高性能计算中心（合肥） 并行计算 习题解答
第二次作业·2.5前龙2.5一个N=2个节点的de Bruijnm网络如图 2. 35 所示。令 4-14-2a1ao 是一个节点的二进制表示，则该节点可达如下两个节点：a-2a--""aia0a--a-"aral011001101010111000110100图2.35N=8的deBruijn网络试间：该网络的直径和对剖宽度为多少？直径为从全0的节点到全1的节点的距离，为k2国家高性能计算中心（合肥）并行计算2026/9/22
国家高性能计算中心（合肥） 并行计算 2026/9/22 • 2.5 • 直径为从全0的节点到全1的节点的距离，为k 2 第二次作业
第二次作业·对剖宽度：·k为奇数时：·将节点可分为两组，一组中N(O)>N(1),设为A组，一组N(O)<N(1)，设为B组。对剖宽度即为A组和B组之问的边的数量。·由于每次最多只能增加或减少1个1，因此只需考虑边界条件，即A组的N(O)=N(1)+1和B组N(1)=N(O)+1·在A组边界条件中，与B组相连的节点一定以O开头。这样的节点数目为：c(k-D /2· 同理, B组中的节点数目也为C(k-1) /2/k-即对剖宽度为2*C(k-1) /2yk-2026/9/223并行计算国家高性能计算中心（合肥）
国家高性能计算中心（合肥） 并行计算 第二次作业 • 对剖宽度： • k为奇数时： • 将节点可分为两组，一组中N(0)>N(1),设为A组，一组 N(0)<N(1)，设为B组。对剖宽度即为A组和B组之间的边的数量。 • 由于每次最多只能增加或减少1个1，因此只需考虑边界条件， 即A组的N(0)=N(1)+1和B组N(1)=N(0)+1 • 在A组边界条件中，与B组相连的节点一定以0开头。这样的节 点数目为： • 同理，B组中的节点数目也为 • 即对剖宽度为2* 2026/9/22 3 k-1 /2 k-1 （ ） C k-1 /2 k-1 （ ） C k-1 /2 k-1 （ ） C
第二次作业·k为偶数时：·与为奇数时相比，增加了一组k为偶数时，除了①中两组，还有一组N(O)=N(1)，设为C组。·将C组分为再分为两组，一组以0开头，设为CO一组以1开头设为C1。Coe，其中满足红色和蓝色的连线的边的数量即为对剖宽度·从A到CO的连线，A中的节点需要满足的条件为：(1)开头是OO(2)N(0)=N(1)+2;。 满足(篇X2条件的节点数为:3·从CO到C1的连线，CO中的点需要满足的条件为：开头是01。满足条件的节点数也为2026/9/22A国家高性能计算中心（合肥）并行计算
国家高性能计算中心（合肥） 并行计算 第二次作业 • k为偶数时： • 与k为奇数时相比，增加了一组 • k为偶数时，除了①中两组，还有一组N(0)=N(1)，设为C组。 • 将C组分为再分为两组，一组以0开头，设为C0，一组以1开头 设为C1。 • 其中满足红色和蓝色的连线的边的数量即为对剖宽度 • 从A到C0的连线，A中的节点需要满足的条件为：(1)开头是00 (2)N(0)=N(1)+2;。满足这两个条件的节点数为： • 从C0到C1的连线，C0中的节点需要满足的条件为：开头是01。 满足条件的节点数也为 2026/9/22 4 ( 2)/ 2 2 − − k Ck ( 2)/ 2 2 − − k Ck
第二次作业· 即可求得对剖宽度为 4*C(k-2)/2/k-22026/9/225并行计算国家高性能计算中心（合肥）
国家高性能计算中心（合肥） 并行计算 第二次作业 • 即可求得对剖宽度为 4* 2026/9/22 5 ( 2)/ 2 2 − − k Ck