论文摘要
图的布局问题是一类组合优化问题,它在一些科学领域诸如并行计算机网络体系结构的优化,超大规模集成电路的设计,信息检索,数值分析,计算生物学以及生产调度有着广泛的应用。给定一个图G=(V,E),它的标号是指它的顶点集V(G)到集合[|V(G)|]={1,2,...,|V(G)|}的一个双射。所有这些标号的集合称为图的标号集。图的目标函数是定义在图的标号集上的实值函数。图的布局问题即为：对给定的图以及一个目标函数,寻找图的顶点集中的一个标号,使得给定的目标函数达到最优值。给定图以及它的一个标号,任意一条边的两个端点标号的差的绝对值称为这条边的边长,图的线长是所有这些边的边长的和。显然,图的线长也是一种目标函数。图的线长问题即为找到图的一个标号使得它的线长达到最小值,图的线长问题是图的布局问题的一种。本文主要内容包括下面三个部分：(1)引入图的布局的基本概念和定义,并研究有关图的线长的一些性质。(2)只。∧G线长问题：研究只。∧G的线长达到最小值时对应的标号的性质,并根据它的性质给出只。∧G的线长与G的线长的关系。(3)pm⊙Pn的线长问题：研究Pm⊙Pn的线长达到最小值时对应的标号的性质,并根据它的性质给出Pm⊙Pn线长最优值的上下界。