二维带宽的浓度下界

二维带宽问题是确定图Ｇ在平面格子图中的一个嵌入，使最长的边尽可能短，本文研究若干个下界以及它们应用于带宽的估值。所有结果均建立在一种平面组合几何的方法之上，其中的浓度下界改进了文献（３）的结果。     

弦图的补图的最小填充

从图论观点讲,最小填充问题就是在一个图G中添加边集F,使得图G的母图G F是一个弦图而且所添边的边数| F|是最小的,其中最小值| F|称为图G的填充数,表示为f( G) .对一般图来说,最小填充问题是NP-困难的,但是对一些特殊图类来说,这个问题是在多项式时间内可解的.本文给出了弦图的补图-G的填充数f(-G) .     

最小树图的Hamilton性及全部最小树的生成

对给定的连通图G,树图T(G)的Hamilton性,首先由Cummins所证明。稍后,Kamae给出另一构造证明,并用于树的生成。本文将研究一个赋权图G所有最小树的一些性质。主要结果如下:(1)对任意赋权图G,证明了最小树图T_(min)(G)的Hamilton性;(2)根据构造性证明,给出生成全部最小树的算法。     

图的割宽总是的度序列方法

The cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges is minimized. This paper presents an approach based on the degree sequence of G for determining the exact value of cutwidth of typical graphs (e. g. , n-cube,cater-pillars). Relations between the cutwidth and other graph-theoretic parameters are studied as well.     

关于六角系统的极植问题

本文讨论六角系统中将宽度与直径结合起来的几个极值问题，并给出相应的极图构造。最后，指出并补正［４］中一个计数结果的不足。     

紧急网络中的最小饱和流问题

网络N中的一个流,如果沿前向已无法再增流,则称为饱和流,在交通拥挤或紧急疏散时,网络往往被一饱和流所堵塞。显然,这饱和流的值越小,网络的性能就越差。于是从网络分析的观点就提出最小饱和流问题。本文首先证明此问题NP－困难的。然后给出关于最小饱和流与最大流的关系及算法方面的结果。     

弦图扩张与最优排序

弦图是一类特殊的完美图,以具有完美消去顺序为特征．由弦图扩张引出一系列序列性组合优化问题,沟通了图论、数值分析及最优排序等领域的若干研究课题．本文将论述我们的一些观点和研究结果．     

偶匹配可扩性的极图问题(英文)

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.     

二维带宽的浓度下界（英）

二维带宽问题是确定图G在平面格子图中的一个嵌入，使最长的边尽可能短.本文研究若干个下界以及它们应用于带宽的估值.所有结果均建立在一种平面组合几何的方法之上.其中的浓度下界改进了文献[3]的结果.     

带工件相容约束的单机分批排序问题

The single machine parallel batch problem with job compatibility is considered to minimize makespan,where the job compatibility constraints are represented by a graph G.This problem is proved to be NP-hard.And when the graph G is limited to be a general bipartite,a complete bipartite and a complete m-partite graph,these problems are solved in polynomial time respectively.