三分图上的匹配及其算法和应用

来源 :复旦大学 | 被引量 : 0次 | 上传用户：yjq123wlz

【摘要】

：

该文将二分图上的匹配概念推广到了三分图上,建立了最大匹配,最大加权匹配,最大b-Matching,最大加权b-Matching的数学模型.并运用基于拉格朗日松弛的分支定界方法进行求解,在

【作者】

：

陆三清

【机构】

：

复旦大学

【出处】

：

复旦大学

【发表日期】

：

2003年期

【关键词】

：

三分图匹配拉格朗日松弛图论数学模型管理决策

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

该文将二分图上的匹配概念推广到了三分图上,建立了最大匹配,最大加权匹配,最大b-Matching,最大加权b-Matching的数学模型.并运用基于拉格朗日松弛的分支定界方法进行求解,在算法的初始阶段通过启发式算法进行预处理给出一个比较好的初始下界.文章中还列举了几个三分图上的匹配在管理决策中的应用.

其他文献

Riemann-Liouville型分数微分系统的迭代学习控制问题

分数阶微分方程将整数阶微分方程拓广到任意阶微分方程，逐渐发展成为微分方程的一个重要分支，尤其适合描述带记忆和遗传现象的物理和力学过程。迭代学习控制技术作为智能控制和

学位

Riemann-Liouville分数微分系统迭代学习控制初态学习收敛性分析

粳稻超高产新品种松粳15的选育及栽培技术

松粳15是黑龙江省农业科学院五常水稻研究所1999年以松97-98为母本,东农V4为父本,杂交后代采用系谱法选育而成。2007年参加所内产量鉴定,决选后暂定名松06-308,2008～2009年参

期刊

高产新品种栽培技术超级稻品种系谱法选育区域试验积温带农作物品种审定杂交后代产量鉴定省农业科学院

小波变换在隐马尔科夫模型非参数估计中的应用

隐马尔科夫模型(Hidden Markov Model,简记为HMM)作为一种统计模型,在模式识别与随机信号处理中有着广泛的应有.小波理论是近年来兴起的一种崭新的信号分析理论,在许多信号处

学位

隐马尔科夫模型随机信号处理非参数密度估计小波正交级数分解尺度

可修混联系统的可靠性研究

该文用马尔可夫法,对可修串-并联系统和可修并-串联系统的可靠性进行了分析.文中在总结了分析这些系统可靠性的基本理论和方法后,针对由多个部件组成的一般串-并联系统和并-

学位

可修串-并联系统可修并-串联系统状态转移图转移概率矩阵

有关非线性可积系统的研究及孤立子方程的Darboux变换

该文分别构造了具有2个位势和3个位势的等谱特征问题.从等谱问题出发,利用屠格式导出了著名的广义Burgers方程族和一类新的MKdV-NLS方程族,及一族离散的非线性演化方程,且证

学位

非线性演化方程Hamilton结构Liouville可积非线性化可积耦合精确解Darboux变换

涉及分担值的正规定则

早在1907年P.Montel就提出了关于正规族的概念，他把具有某种列紧性的函数族称为正规族.近几十年以来，学者们在亚纯函数正规性问题方面已经得出了许多比较深刻的结果.本文在前人

学位

整函数亚纯函数正规定则正规族值分布

关于M序列的性质

该文对M序列(即 De Bruijn序列)进行了研究.M序列是一种伪随机码,具有良好的伪随机性,在密码学中有着很重要的应用.n级M序列的状态图就是n级德布鲁恩-古德(de Bruijn-Good)图

学位

M序列n级德布鲁恩-古德图反树剪接法升级法伪随机码

区间值模糊命题逻辑及其广义重言式

本文首先从有限区间值模糊命题逻辑出发,讨论其逻辑代数及广义重言式的性质;通过将S-型蕴涵修改为R-蕴涵,找出区间值模糊命题逻辑I[0,1]的最大子代数,并在其中将王国俊教授的

学位

模糊逻辑区间值模糊命题逻辑广义重言式可达广义重言式

非单调PRP型算法的收敛性研究

共轭梯度法因存储量小且收敛速度较快等特点常被用于求解大型优化问题.最早的共轭梯度法是由Hestenes和Stiefel在1952年为求解线性方程组Ax=b提出来的，即经典的线性共轭梯度法

学位

PRP方法非单调线性搜索全局收敛性

企业并购中支付策略及估值问题研究

该文分为五个部分:第一部分,主要讨论企业并购的动机与效应.企业并购的原始动机主要来自:1、追求利润的动机;2、竞争压力的动机.但现实生活中并购过程是一个多因素的综合平衡

学位

支付方式企业估值企业并购

三分图上的匹配及其算法和应用

与本文相关的学术论文