关于汽轮机叶片动平衡的一个最优排序问题

本文讨论在汽轮机转子设计中提出的叶片最优排序问题.它可以转化为特殊的二次分配问题,但由于规模较大,一般的二次分配问题算法(如分枝定界法)难以应用.本文的主要结果是导出最优排列的一个必要条件,由此建立两种实用的启发式算法.一、问题的力学提法     

最优化原理的逻辑基础

五十年代 R.Bellmanl 提出最优化原理,奠定了动态规划的理论基础,并渗透到其它数学学科(如变分学、控制论),引起了算法研究的变革.然而,几十年来人们一直在寻求这一般原理的精确证明(参见[2]).这个证明的难点之一是最优策略的存在性.除此之外,在原理的运用上曾出现过种种模糊的认识.T.C.Hu和秦裕瑷甚至举甘:反例,说明其在某些情形不成立(不妨称之为动态规划“悖论”).因此,最优化原理的逻辑基础研究具有重要意义.作者曾在[6]中提出一种理论框架.本文将进一     

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

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

图的两类一般多项式

<正> 本文提出图的边覆盖多项式;它与 Farrell 提出的 F-多项式(点覆盖多项式)一起,可以概括图的若干重要多项式,如特征多项式、色多项式、树多项式、匹配多项式、结构多项式及本文的 Euler 多项式等.我们就这两类多项式,证明了两个一般形式的消去定理.然后,将赋权图及有向图的几种多项式纳入此框架之中,从而得到有关行列式、承袭式、特征多项式及赋权匹配多项式的若干结果.     

凸六角系统（Ⅰ）

1 引言六角系统(Hexagonal systems)的理论有着明确的化学背景而为人们所注意,关于它的研究最近有专著出版。本文引进一种特殊的六角系统——“凸的六角系统”(Convex Hexagonal systems)。对凸六角系统,讨论如何代码化、合同变换群、计数等问题,这都比较简单,对一般六角系统(非凸六角系统),可引进“凸包”的概念,使之成为凸六角系统的子系统,讨论其代码化、分类及计算等问题。本文还提供一种可以在计算机上实现的计算方案。     

P4—free平面图的路色数

本文证明了P_4-free 2-连通平面图的路色数为2。     

限位排列的一个图论方法

通常解分配问题(Assignment problem)、限位排列问题或相异代表系问题(S.D.R)的图论方法是将其化为求偶图最大对集或网络最大流问题。这些方法都只给出了一组解。本文运用置换及有向图的理论,得出求全部解的分枝围追算法。     

图的扩张与稀疏矩阵计算中的若干优化问题

本文研究从稀疏矩阵计算中提出的若干离散最优化问题,即带宽,树宽,路宽,侧廓,扩充侧廓及填充问题。实际上,它们是一类图扩张问题;这些问题同时来源于各式各样的课题,如图子式理论,VLSI电路设计,互联网络及分子生物学等,本文从图论观点着重讨论两种统一途径：图的标号及图的扩张。     

最大匹配图的围长

将一个图的所有最大匹配作为顶点集,称两个最大匹配相邻,若它们之一通过交换一条边得到另一个,由引所得图为该图的最大匹配图。本文研究了最大匹配图的围长,从而给出了最大匹配图是树或完全图的条件。     

最小填充问题的可分解性

起源于稀疏矩阵计算和其它应用领域的图G的最小填充问题是在图G中寻求一个内含边数最小的边集F使得G F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).作为NP-困难问题,该问题的降维性质已被研究,其中包括它的可分解性.基本的可分解定理是:如果图G的一个点割集S是一个团,则G经由S是可分解的.作为推广,如果S是一个"近似"团(即只有极少数边丢失的团),则G经由S是可分解的.本文首先给出基本分解定理的另外一个推广:如果S是G的一个极小点割集且G-S含有至少|S|个分支,则G经由S是可分解的;其次,给出了这个新推广定理的一些应用.