图的对偶带宽问题

图G的带宽问题是一般提法是：将图G嵌入于主图H，使得G的边的最大跨度达到最小，当图G表示一种冲突关系时，便提出如下的对偶问题；将图G嵌入于主图H，使得边的最小跨度达到最大，研究了对偶带宽问题的基本性质和计算复杂性。     

关于偶匹配可扩图中删去两个点

设G是含有完美匹配的简单图.称G是偶匹配可扩的,如果G中导出子图是偶图的匹配M都可以扩充为G的完美匹配.研究了在偶匹配可扩图中删去两个顶点后该图的性质.这些性质对于偶匹配可扩图的进一步研究会有帮助.     

铁路技术站调机运用模型及算法

研究铁路车站作业计划编制过程中,如何编制调机运用计划的关键问题,通过分析运用调机时区集合上的偏序结构特点,可以知道使用调机问题的实质是偏序集合的全序分解问题。利用偏序集合的传递性构造调机的有向图－图,再将调机运用问题转化有向图的有向路分解问题,对于传递图构造它对应的偶图－无向偶图,将传递图的向路分解问题转化为其对应偶图的匹配问题,最后,利用偶图最大匹配问题的算法解决调机运用问题。     

2×n排序问题最优解的充要条件

在两台设备n个工件的排序问题中,熟知的Johnson条件是:对加工排列(i_1,i_2,…,i_n)中任意的i_j,和i_k(j相似文献   

试论最优化原理的一般形式

本文提出最优化原理的一般形式,它由关于整体最优与局部最优的两个简单命题所组成。设(Ω,≤)为一偏序集,(Ⅰ) Ω的最大元x~＊是AΩ的最大元,当且仅当x~＊∈A;(Ⅱ) A的最大元x~＊是Ω的最大元,当且仅当A含Ω的最大元。这将构成Bellman最优化原理分枝定界原则及最优化领域中许多原理原则的统一基础。     

图的带宽问题的度序列方法

带宽问题由于其活跃的实际背景而受到重视。计多已有的工作都是试图建立带宽与其它图论参数之间的关系,特别是用各种图论参数来估计带宽的下界。这些结果往往是孤立地得到,而实际上却相互蕴含,甚至有不确切的。本文将从研究方法的角度,把这一领域的成果统一在“度序列方法”(即本文定理1,2及其对偶)之下,并对有关问题作出回答和评注。     

P-J型最优服务排序问题的线性规划方法

P-J型最优服务排序问题(见《应用数学学报》,1981年,No.1及本刊1981年,No.22),如用线性规划方法处理,比较简单。该问题所研究的服务形式实际上可以转化为一个二阶段分配过程。但无论哪一个阶段,都可纳入如下的线性规划模型:在约束     

对称旅行售货员问题局部搜索邻域的计数

旅行售货员问题(TSP)是图论、组合最优化和计算机科学中所熟知的.为了分析局部搜索算法的效果而提出如下的计数问题:给定完全图K_n的一个哈密顿圈C??,通过替换其中λ条边,可以得到多少个不同的哈密顿圈呢?[3]的作者已对非对称TSP解决了上述计数问题.本文将就对称TSP这一更困难情形给出相应的结果.     

评Banach火柴盒问题的一些解法

在目前许多的大学概率论教材和参考书(例如[1]～[4])中,都引述了一个著名的例子——Banach火柴盒问题。但,其中的解法是欠妥的。问题一个数学家,随身携带两盒火柴,当他要用火柴时,随意从其中的一盒中取出一根。假定开始时两个火柴盒中各有n根火柴。试问在某一次该数学家发现拿出的那盒火柴已经空时,另一盒中恰有r根(0≤r≤n)的概率是多少? 著作[1]是用古典方法解的,如下: