Assignment of Numbers to Vertices
Assignment of Numbers to Vertices
复制标题
给顶点分配数字
DOI：
10.1080/00029890.1964.11992272
复制
发表时间：
1964
影响因子：
0.5
通讯作者：
J. Lindsey
中科院分区：
文献类型：
--
作者：
J. Lindsey
在最近的一篇论文[1]中。哈珀讨论了以下问题。给定一个n维的立方体，如何将0到2“-1的整数赋给这个n立方体的顶点，以使分配给每个顶点的数的差的绝对值之和在所有相邻的顶点对上最小化？他证明了，最好的办法就是将n立方体视为由O和1‘S组成的2”n元组的集合，并将其二进制展开为n元组的整数赋给由n元组标记的顶点(尽管还有其他分配也是同样好的)。这个问题源于编码理论中的下列问题：为0到2“-1之间的数字分配n个0和1的元组，使二进制字词传输中出现的所有单个错误所造成的平均绝对数值误差最小化。使用k字母表中的符号而不是两个字母字母表中的符号，这个问题变成了最小化分配给所有相邻顶点对的数字的差值的绝对值之和的问题。如果两个顶点在除一个坐标之外的所有坐标上都一致，则称它们为相邻的。这里要分配的是从0到k”-1的数字。本文证明了Harper结果的适当推广。我们还将驳斥哈珀定理。
In a recent paper [1]. L. Harper discussed the following problem. Given a cube in n dimensions, how shall the integers from 0 to 2"-1 be assigned to the vertices of this n-cube in such a way as to minimize the sum, over all neighboring pairs of vertices, of the absolute value of the difference of the numbers assigned to each vertex? He proved that one can do no better than to consider the n-cube as the set of 2" n-tuples of O's and 1's, and assign to the vertex labelled by an n-tuple the integer whose binary expansion is that n-tuple (although there are other assignments that are as good). This problem arose from the following problem in coding theory: assign n-tuples of zero and one to the numbers from 0 to 2"-1 in such a way as to minimize the average absolute numerical error made due to all single errors which arise in transmission of the binary words. Using symbols from a k-letter alphabet instead of from a two letter alphabet, the problem becomes one of minimizing the sum of the absolute values of the differences of the numbers assigned to all pairs of neighboring vertices. Two vertices are called neighboring if they agree in all but one coordinate. Here the numbers from 0 to k"-1 are to be assigned. The proper generalizations of Harper's results are proved in this paper. We shall also reprove Harper's theorem.