图的最优标号的临界性、可分解性及有关问题

【作者】 张振坤；

【导师】 林诒勋；

【作者基本信息】 郑州大学 ， 基础数学， 2006， 博士

【摘要】 图的最优标号是图论及组合最优化中涉及顺序结构的一个专题，由于得到应用领域的支持，并与其它理论课题发生密切联系，半个世纪以来受到众多学者的关注。设G=（V（G），E（G））是一个图，其中V（G）为顶点集，|V（G）|=n，E（G）为边集。一个双射f：V（G）→{1,2,…,n}称为图G的一个（顶点）标号，它表示图中所有顶点的一个顺序：当f（v_i）=i（i=1,2,…,n）时，π=（v₁,v₂,…,v_n）就是一个顺序。这个顺序可以表示稀疏矩阵计算中的行列顺序或消元顺序，也可以表示电路设计中的元件嵌入顺序或计算机互联网络的布列顺序。一个标号（或顺序）的优劣可以有不同的衡量指标；不同要求下的不同衡量指标便引出不同的组合最优化问题，如矩阵存贮量最小引出带宽及侧廓最小化、电路设计中的连线重叠最小引出割宽最小化，如此等等。这些最优标号问题与一些图论专题有密切关系，如最小填充及树宽与弦图扩张有关、最小侧廓及路宽与区间图扩张有关、最小扩充侧廓及带宽与单位区间图扩张有关等；在图子式理论中起着重要作用的树宽、路宽、割宽等都是典型的标号问题。 最优标号问题的研究内容，大致可分为算法性质及结构性质两方面。算法性质是指计算复杂性、多项式算法及近似算法的设计与分析等；结构性质包括参数的上下界、极值与极图、临界图结构、可分解性、特殊图表达式等。本学位论文主要围绕临界图结构及可分解性展开研究，同时对特殊图类的表达式及两个新模型进行探讨。在系统地掌握该领域的前沿研究工作的基础上，本学位论文主要取得如下四个方面的创新成果。 1．4-割宽临界树 图子式理论[74-78]的基本定理断言：任何对子式封闭的图类都存在有限的障碍集（obstruction set），使得图G属于此图类当且仅当不存在障碍H是G的子式。由此可以得到这个图类的禁用子图（子式）刻画。例如，平面图的障碍集为{K₅，K_3，3}。文献[2，81，84]中关于树宽和路宽临界图的结果也属于这种禁用子式刻画。文献中关于割宽临界图的研究较少，只有[45]给出了3-割宽临界图的刻画——共5个图，其中两个树。本文在此基础上作出推进，解决了4-割宽临界树的完整刻画问题。对给定的标号f，图G在标号f下的割宽是指而图G的割宽是指其中的最小值取遍G的所有标号f。图G称为k-割宽临界图，是指c（G）=k，对G的任意真子图G′有c（G′）＜k，且G是同胚极小的。我们得到：全部4-割宽临界树为图0所示的12棵树T₁，T₂，…，T₁₂。更多还原

【Abstract】 The optimal labeling problems for graphs is a special topic dealing with ordering structure in graph theory and combinatorial optimization. Because it has important applications and is in connection with other theoretic problems closely, it has been studied for more than half of centenary. Let G = （V（G）,E（G）） be a graph with vertex set V{G) and edge set E（G）, |V（G）| = n. A bijection f : V（G） → {1,2, ...,n} is called a labeling of G, which stands for an ordering of all vertices of G: if f（v_i） = i （i = 1,2, ...,n） , then π = （v₁,v₂,.....,v_n） is an ordering. The ordering π can represent not only an ordering of rows （or columns） or elimination ordering in computations of sparse matrices, but also an embedding ordering of elements in circuit designing, and an arrangement ordering of interconnection network of computers. There are different criteria to evaluate a labeling f; and different criteria with different demands induce different combinational optimization problems. For examples, the minimum of the amount of storage in a matrix induces the minimization of bandwidth and profile, the minimum of congestion of connected lines in circuit designing educes the minimization of the cutwidth, etc. These optimal labeling problems are in connection with some topics in graph theory immediately, for instances, the minimum fill-in and treewidth are in connection with chordal graph extension, the minimum profile and pathwidth are in connection with interval graph extension, the minimum extended profile and bandwidth are in connection with proper interval graph extension; the treewidth, pathwidth and cutwidth, which play important roles in graph-minor theory, are all typical labeling problems.The study of the labeling problems can be divided into two aspects: one is the algorithmic properties, the other is the structural properties. Algorithmic properties contain the computational complexity, the designs and analyses of polynomial time algorithms and approximation algorithms etc., while the structural properties include the upper and lower bounds of parameters, extremal values and extremal graphs, the structure of critical graphs, the decomposability properties and the expressions of special graphs, etc. This dissertation investigates the structure of critical graphs and the decomposability properties mainly, and discusses the expressions of special graphs and two new models as well. Based on a systematic survey of recent literatures, the dissertation obtains four aspects of creative results as follows.1. 4—cutwidth critical treesThe basic theorems in graph minor theory [74-78] claim: any minor-closed graph class has a finite obstruction set such that a graph G belongs to this class if and only if any obstruction H is not a minor of G. From this, the characterizations of the forbidden minors of this graph class can be obtained. For an example, the obstruction set of the planar graphs is {K₅,K_3,3}. The results更多还原