2024年4月6日发(作者：夕芳洁)
n
PM2I单级网络的最大距离为
2
.
证：
2
i
=
2
n
-1=-1mod
2
n
.
i
0
n
1
任何一个单元到单元j的正向距离可表示为:
k
i
2
i
(k
i
=0或1),因为该式能
i
0
n
1
表示1到
2
n
-1之间的任何一个二进制数k
n-1
k
n-2
…k
1
k
0
,即1到
2
n
-1之间的任
何一个距离.
这也说明从j出发通过PM2I网络可连至任何一个其它单元.
而
k
i
2
i
=
2
n
-1-
2
j
=(
2
n
-1-
2
j
)mod
2
n
=(-1-
2
j
)mod
2
n
,等式两边共
i
0
k
j
0
k
j
0
k
j
0
n
1
有n+1项.当n为偶数时,等式两边项数最少的一边的项数≤
边项数之和≥(
n
(否则, 等式两
2
nn
+1)+ (+1)=n+2,矛盾). 当n为奇数时,等式两边项数最
22
n1n1n1
少的一边的项数≤
(否则, 等式两边项数之和≥
+=n+1,矛盾).
222
n
所以PM2I单级网络的最大距离≤
.
2
若
a
i
2
=
b
i
2
i
(a
i
,b
i
=0或1),则a
i
=b
i
.否则,设a
j
为a
i
≠b
i
中编号最小的i,则
i
i
0i
0
n
1n
1
有
2
(1+
j
i
j
1
c2
i
n
1
i
j
)=0(
c
i
=-1,0或1).但
2
≠0, 1+
c
i
2
i
j
为奇数,所以等式左
i
n
1
i
j
1
边不可能为0,矛盾.
现在证明当n为偶数时,与j编号相距
2
2i
以及当n为奇数时, 与j编号相
i
0
n
2
2
距
2
2i
的单元k在PM2I单级网络的距离分别为
i
0
n
1
i
0
n
1
2
nn1
n
和,即
.
22
2
j到k的任一个最短路径d一定可表示为
b
i
2
i
(
b
i
=-1,0或1).因为若有两步
距离相同,设都为
2
j
,则方向相反时抵消,方向相同时可合并成
2
j
1
,因而可得
到一个更短的路径,与d是最短路径矛盾.
当n为偶数时有,
n
1
i
0
2
i
0
n
2
2
2i
=(
b
i
2
)mod
2
, -(
2
-1) ≤
b
i
2
i
≤
2
n
-1.
i
nn
n
1
i
0
n
1
i
0
当0≤
b
i
2
i
≤
2
n
-1时,
n
2
i
0
n
2
2
2i
+
b
j
1,0
j
n
1
2
j
=
b
k
1,0
k
n
1
n
1
i
0
2
k
(1)
当-(
2
-1) ≤
b
i
2
≤0时, (
b
i
2
)mod
2
=
2
+
b
i
2
i
,所以有:
ii
nn
n
1
i
0
n
1
i
0
2
i
0
n
2
2
2i
+
b
j
1,0
j
n
1
2
j
=
2
n
+
b
k
1,0
k
n
1
2
k
(2)
nn
现在证明
b
i
(0
≤i≤n-1)
中不为0的个数
≥
.否则若<,设等式左边第二个和
22
nn
式有r项,则等式右边和式的项数<-r或-r+1. 等式左边可看成二进制
22
数A=0101…0101加上一个含有r个1的n位二进制数B得到C.现在用数学
n
归纳法证明C含1的个数≥-r+1.当r=1时A加B后含1的个数不会减少,
2
nn
因而C含1的个数≥=-1+1,正确.假设r-1时结论正确,则当B含r个1
22
时,设B′为用0代替B中最左边的1得到的二进制数,则C′=A+B′中1的
n
个数≥-r+2.若B′中最左边的1与A中的0相对应,则C′中与B′中最
2
左边的1对应的位以左3位只可能是100或011, C′加上B中最左边的1
后得到的C最多使C′中含1的个数再减少1个,因而C中含1的个数≥
n
-r+1. 若B′中最左边的1与A中的1相对应, 则C′中与B′中最左边
2
的1对应的位左边的1位只可能是1,则C最多也使C′中含1的个数再减少
n
1个,因而C中含1的个数≥-r+1.所以归纳假设成立.
2
(1)或(2)式的左边求和后应与右边是同一个表达式,但左边对应二进制数含
nnnn
1的个数≥-r+1,而右边<-r或-r+1,矛盾.所以
b
i
中不为0的个数
≥
,
2222
n
所以j到k的最短距离是.
2
当n是奇数时,同理可证(此时A=1010…101).
2024年4月6日发(作者：夕芳洁)
n
PM2I单级网络的最大距离为
2
.
证：
2
i
=
2
n
-1=-1mod
2
n
.
i
0
n
1
任何一个单元到单元j的正向距离可表示为:
k
i
2
i
(k
i
=0或1),因为该式能
i
0
n
1
表示1到
2
n
-1之间的任何一个二进制数k
n-1
k
n-2
…k
1
k
0
,即1到
2
n
-1之间的任
何一个距离.
这也说明从j出发通过PM2I网络可连至任何一个其它单元.
而
k
i
2
i
=
2
n
-1-
2
j
=(
2
n
-1-
2
j
)mod
2
n
=(-1-
2
j
)mod
2
n
,等式两边共
i
0
k
j
0
k
j
0
k
j
0
n
1
有n+1项.当n为偶数时,等式两边项数最少的一边的项数≤
边项数之和≥(
n
(否则, 等式两
2
nn
+1)+ (+1)=n+2,矛盾). 当n为奇数时,等式两边项数最
22
n1n1n1
少的一边的项数≤
(否则, 等式两边项数之和≥
+=n+1,矛盾).
222
n
所以PM2I单级网络的最大距离≤
.
2
若
a
i
2
=
b
i
2
i
(a
i
,b
i
=0或1),则a
i
=b
i
.否则,设a
j
为a
i
≠b
i
中编号最小的i,则
i
i
0i
0
n
1n
1
有
2
(1+
j
i
j
1
c2
i
n
1
i
j
)=0(
c
i
=-1,0或1).但
2
≠0, 1+
c
i
2
i
j
为奇数,所以等式左
i
n
1
i
j
1
边不可能为0,矛盾.
现在证明当n为偶数时,与j编号相距
2
2i
以及当n为奇数时, 与j编号相
i
0
n
2
2
距
2
2i
的单元k在PM2I单级网络的距离分别为
i
0
n
1
i
0
n
1
2
nn1
n
和,即
.
22
2
j到k的任一个最短路径d一定可表示为
b
i
2
i
(
b
i
=-1,0或1).因为若有两步
距离相同,设都为
2
j
,则方向相反时抵消,方向相同时可合并成
2
j
1
,因而可得
到一个更短的路径,与d是最短路径矛盾.
当n为偶数时有,
n
1
i
0
2
i
0
n
2
2
2i
=(
b
i
2
)mod
2
, -(
2
-1) ≤
b
i
2
i
≤
2
n
-1.
i
nn
n
1
i
0
n
1
i
0
当0≤
b
i
2
i
≤
2
n
-1时,
n
2
i
0
n
2
2
2i
+
b
j
1,0
j
n
1
2
j
=
b
k
1,0
k
n
1
n
1
i
0
2
k
(1)
当-(
2
-1) ≤
b
i
2
≤0时, (
b
i
2
)mod
2
=
2
+
b
i
2
i
,所以有:
ii
nn
n
1
i
0
n
1
i
0
2
i
0
n
2
2
2i
+
b
j
1,0
j
n
1
2
j
=
2
n
+
b
k
1,0
k
n
1
2
k
(2)
nn
现在证明
b
i
(0
≤i≤n-1)
中不为0的个数
≥
.否则若<,设等式左边第二个和
22
nn
式有r项,则等式右边和式的项数<-r或-r+1. 等式左边可看成二进制
22
数A=0101…0101加上一个含有r个1的n位二进制数B得到C.现在用数学
n
归纳法证明C含1的个数≥-r+1.当r=1时A加B后含1的个数不会减少,
2
nn
因而C含1的个数≥=-1+1,正确.假设r-1时结论正确,则当B含r个1
22
时,设B′为用0代替B中最左边的1得到的二进制数,则C′=A+B′中1的
n
个数≥-r+2.若B′中最左边的1与A中的0相对应,则C′中与B′中最
2
左边的1对应的位以左3位只可能是100或011, C′加上B中最左边的1
后得到的C最多使C′中含1的个数再减少1个,因而C中含1的个数≥
n
-r+1. 若B′中最左边的1与A中的1相对应, 则C′中与B′中最左边
2
的1对应的位左边的1位只可能是1,则C最多也使C′中含1的个数再减少
n
1个,因而C中含1的个数≥-r+1.所以归纳假设成立.
2
(1)或(2)式的左边求和后应与右边是同一个表达式,但左边对应二进制数含
nnnn
1的个数≥-r+1,而右边<-r或-r+1,矛盾.所以
b
i
中不为0的个数
≥
,
2222
n
所以j到k的最短距离是.
2
当n是奇数时,同理可证(此时A=1010…101).