次限制拟阵基的排序算法

§1 引言本文对一般的拟阵,给出在一个子集上具有次限制所有拟阵基的排序算法。著名的“greedy”算法是求连通图最小权的支撑树的好算法。在连通图上特别指定了一个顶点,求在该顶点次限制的最小权的支撑树,Glover—Klingman也给出了好算法。Burns—Haff给出了图的支撑树权的大小进行排序的生成算法,并且指出能够把它推广为拟阵基的排序算法。本文对一般的拟阵,给出在一个集上具次限制的所有拟阵基的按权的大小进行排序的生成算法。     

准模糊图拟阵的相邻的次限制最小基

模糊拟阵的基图是模糊拟阵的基本概念.在准模糊图拟阵的基础上,给出了准模糊图拟阵基图的相邻的次限制最小基的一些性质.将为深入研究模糊拟阵的内在本质,进一步研究模糊拟阵的算法奠定了基础.     

准模糊图拟阵的次限制最小基

模糊拟阵的基图是模糊拟阵的基本概念.在准模糊图拟阵的基础上,给出了准模糊图拟阵基图的次限制最小基的一些性质,这将有利于进一步研究模糊拟阵的其它性质.     

求第K棵树形图的算法

本文利用拟阵交的交错序列思想，并借助改进的求第ｋ最短路的算法，给出了求第ｋ最小树形图的算法，时间复杂度为Ｏ（ｋ３｜Ａ｜３）．     

闭模糊拟阵模糊基的判定

通过讨论闭模糊拟阵的导出拟阵序列和模糊基的结构,找到了判定闭模糊拟阵的模糊基的一个充要条件。根据此充要条件,给出了从导出拟阵序列得到闭模糊拟阵的模糊基的一种算法。     

关于模糊拟阵的模糊秩研究

本文受正规模糊拟阵启发,定义了普通模糊拟阵的正规模糊基概念;然后利用基子集套方法,证明了闭模糊拟阵存在正规模糊基,在同一模糊拟阵中的正规模糊基的模糊势相等,正规模糊基的模糊势是同一模糊拟阵中的模糊基的最大模糊势等性质。通过这些性质,给出了用正规模糊基描述的闭正规模糊拟阵的充要条件。还利用这些性质,得到计算正规模糊基模糊势的公式;最后拓展普通拟阵的秩定义了一般模糊拟阵的模糊秩。通过模糊拟阵的闭包概念,证明了模糊拟阵的模糊秩等于正规模糊基的模糊势,并得到计算模糊拟阵模糊秩的公式。同时,详细讨论了模糊拟阵模糊秩的许多性质,还对利用模糊拟阵模糊秩研究模糊拟阵做了一点尝试。模糊秩是模糊拟阵的固有特征之一,通过模糊秩来研究模糊拟阵,或者从模糊拟阵来讨论模糊秩都有大量工作可以做。     

关于模糊横贯拟阵表示的初步研究

本文首先讨论了模糊子集族的全体模糊部分横贯能够形成模糊横贯拟阵的条件,得到两个充要条件。第一个充要条件使用截短模糊子集族来进行描述;第二个充要条件是通过部分横贯的指标集单射兼容这个概念来描述。然后研究了模糊横贯拟阵的表示形式,得到了三个结论。一是任何模糊横贯拟阵都有"精简表示",而且构造了从一个表示寻找精简表示的方法;二是模糊横贯拟阵的表示的模糊子集个数不小于导出拟阵的最大秩;三是一致模糊横贯拟阵的任何表示都包含"最小表示",也给出了求这个"最小表示"的方法。     

广义拟阵的约简与近似算子

广义拟阵作为拟阵结构的拓广形式之一,在许多领域扮演着重要的角色.为了将广义拟阵理论进一步地拓广,首先基于覆盖粗糙集,提出可约广义拟阵的定义,并给出相关的算法和实例.其次,为了实现不同广义拟阵知识层面上知识的表述,将拟阵中秩强映射的定义推广到广义拟阵中,并且基于此定义,对于广义拟阵提出一种特殊的秩强映射——保基秩强映射....     

准模糊图拟阵基图的最大权基与字典序最大的基

模糊拟阵的基图是模糊拟阵的基本概念.在准模糊图拟阵的基础上,给出了准模糊图拟阵基图的最大权基与字典序最大的基的性质,这将有利于模糊拟阵从基础研究逐渐转向应用研究.     

关于模糊拟阵的独立子集套和独立集函数

本文的研究方法主要是将模糊拟阵问题转化为普通拟阵问题来研究的方法。本文首先建立独立子集套概念,并使用这个概念和独立集函数概念构建了闭模糊拟阵的充要条件和模糊独立集的充要条件;然后,本文仔细分析了模糊基的性质,找到了一个使用独立子集套和独立集函数来描述的模糊基的充要条件;最后,利用模糊基的这个充要条件提出并证明了闭正规模糊拟阵的充要条件。     

研究模糊拟阵的一种新方法

本文根据模糊集合的表示方法,在模糊拟阵中提出"基子集套"概念。然后,利用"基子集套"概念描述了闭模糊拟阵的模糊基结构,并给出了闭模糊拟阵的充要条件、闭正规模糊拟阵的充要条件和准模糊图拟阵的充要条件。     

关于模糊横贯拟阵的最大表示

本文利用横贯拟阵的最大表示及其性质来定义和研究模糊横贯拟阵的最大表示问题。首先,推广横贯拟阵的最大表示概念定义横贯拟阵的p-最大表示。同时解决了p-最大表示的存在性、唯一性和算法等问题;然后,再推广横贯拟阵的最大概念定义模糊横贯拟阵的最大表示。证明了模糊横贯拟阵的最大表示也是简洁表示,最大表示的截短子集族是导出横贯拟阵的p-最大表示以及其它性质和结论;接下来,利用这些研究结果,通过简洁表示和p-最大表示概念提出并证明了模糊横贯拟阵的表示是最大表示的充要条件;最后,根据这个充要条件证明了模糊横贯拟阵的最大表示总是存在并且唯一。给出了从模糊横贯拟阵的一个表示计算最大表示的算法,而且证明了这个算法的有效性。     

准模糊图拟阵基图

在准模糊图拟阵的基础上,提出准模糊图拟阵的基图,并讨论准模糊图拟阵基图的性质和特征。     

准模糊图拟阵基图的性质

模糊拟阵的基图是模糊拟阵的基本概念.在准模糊图拟阵的基础上,讨论了准模糊图拟阵基图的一些基本性质,得到了相关的几个结论,这些结论有利于进一步研究模糊拟阵的其它性质.     

超拟阵的独立集公理、基公理和圈公理

Dunstan等在1972年首先提出了超拟阵的概念,用以将定义拟阵的承载集合从有限集推广到偏序集.Barnabei等在1998年研究了另一种偏序集上的拟阵结构,即偏序集拟阵.由有限分配格和有限偏序集之间的对应关系可知,偏序集拟阵就是分配格上的超拟阵.本文研究超拟阵的公理系统,建立模格上的超拟阵的独立元公理,证明模格上超拟阵的中间基性质和基的交换性质并用这两个性质分别刻画了模超拟阵.最后指出了Barnabei等给出的分配超拟阵圈公理中的一个错误,重新提出并证明分配超拟阵的圈消去性质并建立了分配超拟阵的圈公理.作为圈消去性质的一个应用,本文证明了分配超拟阵中覆盖基的元素包含唯一的圈.     

强[0,1]-拟阵

本文研究一类特殊的[0,1]-拟阵,即强[0,1]-拟阵,它属于G-V模糊拟阵类和H模糊拟阵类之交,证明了强[0,1]-拟阵的模糊基交换性定理。     

闭正则模糊拟阵的子拟阵的正则性

研究了闭正则模糊拟阵的子拟阵的正则性等性质.得到了闭正则模糊拟阵的两种子拟阵的正则性等性质,即k-子拟阵为闭正则模糊拟阵,限制子拟阵不是闭正则模糊拟阵,给出了闭正则模糊拟阵的收缩拟阵为闭正则模糊拟阵等结论.     

拟阵限制下合作对策解的传递性

Vincent Feltkamp研究了Shapley解和Banzhaf解的公理性．Bilbao等人又对拟阵限制下的Shapley解的性质进行了讨论．本文在此基础上主要研究了拟阵限制下的合作对策Shapley解，并利用传递性、交换性、概率有效性和P-哑元性等四条公理证明了拟阵限制下合作对策Shapley解的唯一性．进而证明了拟阵限制条件下简单对策Shapley解的唯一性．最后给出了拟阵限制下合作对策的Banzhaf解的唯一性定理．     

准模糊图拟阵基的交换

本文讨论了准模糊图拟阵基的交换定理,在此基础上给出了基有序的准模糊图拟阵的一些性质.     

组合拓扑方法在图论和拟阵理论中的一些应用

本文介绍组合拓扑方法在图和拟阵中的一些应用。 一个简单图在任意给以定向后可以看成是一个一维复形,它是n维复形的一种特殊情况。文章先就n=1的情况,简要地介绍n维复形上的一些极值问题,说明图上作业法和奇偶点图上作业法怎样可以用组合拓扑方法统一起来加以处理;怎样可以从所给的一组循环基出发来求连通图的最小支撑树等。其次,介绍由一维循环群和边缘群分别引出的图上的多边形拟阵和割集拟阵,随后在介绍了n维抽象复形的概念以后,除了叙述n维复形上的极值问题以外,并就简单图,拟阵和n维复形间的一些基本的联系作了说明。举了应用例子,其中包括用配对复形来给出Ramsey数的另一定义,用二维链概念来引出一个与平面四色定理等价的命题等。