无向图的应用外文翻译资料

 2022-08-09 20:07:42

英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

无向图的应用

摘要：带编号的无向图正成为一个越来越有用的数学模型家族，拥有广泛的应用。他们发现在各种编码理论问题中的应用，包括良好的雷达类型码、同步集码和具有最佳自相关特性的卷积码的设计。它们促进整数的最优非标准编码。它们还被应用于x射线晶体学分析中歧义的确定，通信网络寻址系统的设计，最佳电路布局的确定，以及加法数论中的问题。人们试图在一个统一的框架内系统地介绍所有这些不同的应用程序，并指出其他应用程序的存在，并提出进一步研究的方向。

1，简介

有向图的顶点和边的数字赋值问题已有大量的文献，但对无向图的这类考虑相对较少。这种差异是由于人们对编号有向图在现实世界中的应用产生了广泛的兴趣(例如，[11 -[4]])。尽管如此，在许多不太为人所知的情况下，有效的模态同样是用无向图来表达的。

本文考察了一类广义的整数赋值到图的顶点和边的各种应用。我们将给出各种基本定义，并讨论这一统一系列模型的一些应用。

图Gamma;由一组顶点和一组边组成。每条边必须连接两个不同的顶点，并且不能有多于一条边连接任何顶点对。如果一个非负整数 Psi;(u)被分配给每个顶点u，那么它们的顶点被编号。Gamma;本身就是一个编号的图，如果每条边e的值为Psi;(e) = lPsi;(ul) - Psi;(uz)l，其中u1和uz是e的端点。显然，在没有额外约束的情况下，每个图都可以被无限多种方式编号。因此，利用编号图模型需要附加约束，这些约束描述了所研究的问题。

这些必要的约束条件自然地出现在研究各种各样看似毫不相关的实际应用中，而编号图正是为这些应用提供了数学模型。这一理论的一些具体体现如下。

1)脉冲雷达和导弹制导的某些重要的良好非周数编码的设计等价于对完备图的编号，使所有的边数都是不同的。然后，节点数确定脉冲传输的时间位置。相应的雷达脉冲和导弹制导码问题已经研究了几年(例如，[51])。非常相似的模式也被用来提供一种有效的容量编码[61]。

2)利用b符号字母表中的n位向量对0到bn - 1之间的整数进行编码的非自然方法被设计出来，以最小化单个数字中错误发生的严重性。这些编码已经成为一个广泛的文献(例如，[7]-[01])的主题。

3)从x射线衍射数据中确定晶体结构一直是晶体学家关注的问题。现在人们开始理解这一程序所固有的模棱两可之处[111 - 131]。在某些情况下，同一衍射信息可能对应一个以上的结构。这个问题在数学上等价于确定生成预先指定的边数集的适当图的所有个数。

4)在一个小型的通信网络中，为每个用户终端分配一个节点号可能是有用的，这取决于约束条件:所有连接的边(通信油墨)接收不同的数字。这样，任意两个通信终端的数量(通过简单的减法)明确地指定了连接路径的链路号;相反，路径号唯一地指定它所连接的用户终端对。

其他应用程序的编号图包括高精度光学测量系统的设计用于自动钻孔机[14],角同步码[15]的设计,设计最佳的组件的布局对于某些电路板之间的几何图形[16],和确定配置简单的电阻网络可以用来供应的任何一组指定的阻力值[171]- [191]。

数字图的解释也适用于数学的其他领域。一些最重要的数值结果来自于加法数论中的一些直尺问题与数字图之间的对应关系(例如，[201，[211])。

2，编码理论的应用

到目前为止，编码理论可能已经在编号图领域激发了更多的努力，并且比其他任何单一应用领域使用了更多的结果。回顾这一观察结果可以更好地理解，因为几乎没有以前的研究结果正式在编号图上下文中提出。据我们所知，只有一项研究利用了编号图的原始公式。我们从那项工作开始调查。

A，一个整数的最优非标准编码

1954年，Kautz[8]研究了数字计算机和信息处理机器代码设计中的“最小化混淆”问题。虽然冗余被设计成代码来检测，并且在某些情况下用于在消息的编码、传输和解码中连接最可能的错误模式，但是一些错误模式确实可以通过未保护传递。提高误差校正和检测可靠性通常是以降低信息传输率为代价实现的。

计算机和许多其它数据处理系统因其极低的噪声水平和严格的可靠性要求而具有良好的性能。消息周期中的任何错误都是罕见的，单个消息中的多个错误实际上是不存在的。由于这些错误很少发生，Kautz提出了一种通过增加冗余来降低信息传输速率的替代方法。他建议通过明智地将信息分配给码字来尽量减少错误所造成的混乱。这种思想是基于将一个n位二进制代码建模为一个n维立方体。每个轴都有0或1个值，因此每个码字都由立方体的一个角表示。图1列出了与三维立方体相关的23个码字。在传递预期的消息时出现的任何一个错误都会导致接收到的码字与接收到的码字之间的距离为1，即接收到的码字与接收到的码字之间的距离为1。，接收n个邻居之一的预期信息。

Kautz认识到，在不同的情况下，根据不同的标准来确定消息对码字的最佳分配。一个偶然的数字错误可能是允许的，如果它是“足够小，例如。在美国，收到“15”比收到“27”要好，而实际上“19”才是你想要传达的信息。在其他情况下，最好是使错误接收的消息尽可能地与预期的消息不同。例如，当字母“e”传达错误时，接收字符串“bxt”比“bit”更可取。不一致的上下文表示可能未被检测到的事件。

当消息是数字时，此技术的量化非常简单。当收到不是问,“混乱指数”被定义为△ij=| ai-aj |。如何分配的整数编码的分析以△ij的函数最小化的应用程序空间通信最初提出的Golomb[23], 1963年在由哈珀在1964年拍摄的。Harper[8]、[16]、[24]、[25]解决了为几个不同的标准函数分配2”数字消息到2n个码字的问题。他获得了以下优化问题的算法和分析结果：

1)最小化 sum;ine;j△ij

2)最大化 sum;ine;j△ij

3)最小化(max △ij);

4)最大化(min △ij)。

他还推测了一个解决方案;

5)最小化sum;ine;j△2ij。

这个解是由克里明斯等人独立推导出来的。

这些函数很容易解释的通信背景: sum;△ij的平均误差的大小是成比例的发生;max△ij是误差范围的大小;和sum;△2ij表示方差误差大小。Lindsey[9]总结了Harper的一些工作，展示了如何在编码不是二进制时进行优化。

克里明斯等人的研究表明，最小化平均误差大小的赋值也会最小化其方差。Stieglitz和Bernstein[26]指出，使平均值最小的编码并不局限于序列整数。Bernstein等人[27]考虑了所有误差模式的平均幅度误差的最小化。结果表明，当信道传输二进制数据的误码率足够小时，哈珀码是最优的。对于大多数实际情况，这个概率界是成立的。在其他图上最小化这个判据函数的数字也被研究过[28]-[30]。

一般情况下，图数据中使最大值最小化的数max△ij的性质被研究为“带宽”问题[31]-[36]，并被Chvatalova等人总结为[37]和Bloom[12]。将消息分配给△ij多维数据集的算法也适用于非数值消息的编码。在这种情况下,数字混乱指数最初必须分配给每一对(△ij)。当数组(ai，a)是非负对称时，上述算法可直接应用。当(△ij)不对称时，必须将Harper的结果修改为有向图。这些扩展还没有被研究过。

B，具有最小值不同步自相关函数的二进制代码

以下三个应用程序最初都不是在图形理论环境中提出的。然而，它们可以被看作是一个未完全解决的问题在一类有编号的图上的实现。

1）图模型:这些编码应用来源于完备图的最优数。该模型的应用要求每个边数是不同的。完全图的关于m边Km联系m点和(m2 - m)/2线参与的点对。该模型的应用要求每个边数是不同的。这样的一组边的编号是最优的，如果它最小化最大的边值，我们定义为G{Km}。

优化标记图的n边叫做优雅的如果它的顶点可以与不同的非负整数编号不超过n的方式分配给每条边一个从1到n的整数。这样的num白令海峡的存在(也称为评估)和它们的属性被Golomb调查[38],罗莎[39],Kotzig[40],和其他人并调查了Bloom[12]。图2显示了K4的优雅编号。然而，没有一个超过4点的完整图可以被优雅地编号。因此，Km的一般优化数是未知的。

Golomb在编码理论中发现了一个重要的等价性，即最小G(Km)的“半优雅”编码和一个特殊的尺子(包括两端)之间的等价性。划分标志的位置对应于Km的m模式上的数字。因此，Km的边数与一组测量值完全一致，这组测量值可以在Gardner[41]所称的Golomb直尺上的标记之间进行。这种类型的最短可能的尺子有长度G(Km)t。在K5的编号中，没有边的编号是6，用同样的尺子也不能直接测量长度6。m lt; 11刻度，[38]、[41]-[43]的所有最优标尺均已找到，并总结为Bloom和Golomb[22]。这些尺子在编码理论中有几个应用。然而，他们在编码文本中测量的是时间，而不是距离。

2)雷达类型代码：首先，让我们考虑一个简单的测试，使用图3中的五角尺。人们可以从这把尺子中产生一个雷达编码，方法是每次发射与尺子上的标记相对应的五个脉冲序列，即0 1 4 9 11。也就是说，第一脉冲和第二脉冲之间有一个单位时间间隔，第二脉冲和第三脉冲之间有一个三单位时间间隔，第三脉冲和第四脉冲之间有五个单位，最后两个脉冲之间有两个单位。信号的发射和返回之间的时间间隔是由所有输入信号的相关性决定的。对于输入的任何其他序列，与原始模板的序列最多可以有一个输入脉冲。在无噪声的情况下，未归一化的失同步自相关最大可达1。如图4(b)所示。

自相关的下降发生在6个时间单位，因为没有与6个单位偏移的脉冲序列同步位置对齐的脉冲。当然，6是原始标尺无法测量的11个或更少单位的唯一距离，也是编号Ks中唯一缺失的边数(图3)。

Eckler[5]研究了导弹制导码设计的相关编码问题。在机载导弹中，接收器将所有传入的信号通过延迟线。如果在与输入脉冲之间的实际时间间隔相对应的几个地方敲击线路，那么这些脉冲的总和将超过一个阈值，并启动一些控制动作。

这种导弹的命令代码包含两个或多个不同的命令。因此，在仪表方面，延迟线必须由对应于每个命令的脉冲之间的延迟的几组引线连接。为了使代码对随机干扰脉冲(如电风暴或干扰)不敏感，一个命令的脉冲之间的所有延迟必须与其他所有命令的延迟完全不同。为了使延迟线最小化和减少干扰发生的时间，最好使用尽可能短的码字持续时间。因此，Eckler计算了与n个不同命令相关联的d脉冲的d-1间隔。同步时，这些命令在导弹接收时给出高度d的自相关。不同步时，最大自相关为1，命令之间的无噪声互相关也不超过1。

这个问题对应于找到一组n个不同长度的标尺，每个标尺上都有d-标记。这些尺子上的记号只允许用一种方法测量长度。更重要的是，这些尺子中最长的必须尽可能短。另一种方法是，这个问题对应于尽可能完整地编号一个有n个分量的不连通图。每个组件都是d-1个顶点上的一个完全图。还有另一种表示是连接图，其中组件在一点连接。在图5中，我们展示了这些表示方法，用于构造具有最小持续时间序列的干扰不敏感、2消息、4脉冲导弹代码。

虽然Eckler没有解决他指定的代码的优化设计问题，但是他确实为许多这种类型的可行代码生成了区间。1967年，他的一些结果被Robinson和Bern stein重新计算，而另一些结果则在卷积编码的完全不同的环境中得到了改进。我们将在下一节讨论这个问题。

3）自正交码，卷积码的一类。在这一节中，我们在简要讨论了这种类型的“代数编码”之后，研究了Golomb定尺和自正交码之间的密切关系。

卷积码或递归码的编码器与块码的编码器不同。对于块代码，编码器将源消息分成长块，然后通过有噪声的信道对整个块进行编码和传输。对传统码来说，源码被分割成多个短块，这些短块的编码不仅依赖于该块中的消息，而且还依赖于前一个固定数目的N块。

卷积码通过其使用的解码方法自然地划分为类。在阈值解码中，从每个接收到的代码块及其前N个块计算一组“同步组”数字，以确定每个接收到的消息中的错误。如果综合症数字的大多数(阈值)“对接收数字中的错误进行投票，则在对包含错误的块进行编码之前对接收的数字进行补全。这种方法称为直接译码。反馈编码将阈值投票法扩展到证候数字本身的校正。虽然综合征更新提高了解码器的正确解码概率，如果解码错误之前没有发生，它降低了性能时，解码错误发生;因为单个数字中的这种错误也可能导致后续块中的数字被正确解码。这种错误传播和影响不能发生直接解码。

本文主要研究了多边形直接码设计的一个重要方面。关于卷积码更一般、更详细的讨论超出了本文的范围，可以在Peterson和Weldon[44]、Lin[45]和Berlekamp[46]的文章中找到。

1967年，Robinson和Bernstein[6]设计了一种构建自正交码的系统方法，该方法依赖于“差分三角形”的构造。这样的三分角是由d~l整数[0,a1, a2，hellip;,ad-2 ],其中0 lt; a1lt; hellip; lt; ad-2的一个或有界集的正差组成的。一个(n, n-1)的代码，每个块有n个比特，n-1信息比特可以由n-1个没有公共元素的差分三角形构成。当每个三角形都有(d-1 ,2)元素时，码字之间的最小距离是d。

用于形成(n, n-1) =(2,1)的编码的单个差分三角形可以被表示为对Kd-1变换格上的完全图的顶点进行编号，从而使其边缘上的所有数字都是不同的。在满足这一要求的图编号集合中，有些图编号比另一些图编号更适合设计代码。

(2,1)自正交码

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[238711]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章