用n位的二进制数来标识这个节点,使得相临的节点之间.doc

《用n位的二进制数来标识这个节点,使得相临的节点之间.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.1:证明：用n位的二进制数来标识这个节点，使得相临的节点之间只有一位不同，(乔浩)这是可以做到的（可用归纳法证明这一点）。下面分成两种情况进行讨论：1．当两点之间的距离为n时,我们可以假设标记是全0和全1的两个点，n条路径可表示为：00…00…00→00…00…00→…→00…0…0…00,直到1111…111。其中起始位置i可从1到n。2．当距离小于n时，我们总是可以找到一个分划，使得这两个节点在一个规模为2的hypercube网络中，鉴于hypercube本身结构的递归特性，我们可以用归纳法证明这两点之间存在n条顶点不相交的path。证毕。2.2:证明一个大小为的tornus可以嵌

2、入到大小为的hypercube中。(乔浩)证明：用关联矩阵的知识我们知道：设圈对应的关联矩阵为A,圈的为B,则的tornus的关联矩阵为C=,为kernonecker积，设大小为的hypercube的关联矩阵为M,的为N,则的hypercube为S=,显然如果,则,因为大小为的hypercube中包含大小为m的圈,所以是满足的。由于m=n=1,结论成立。用归纳法易证对于一切m>0,n>0成立。