有向图的核理论

来源 :上海大学 | 被引量 : 0次 | 上传用户:hantao2007
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在过去的三十多年里,随着计算机科学的迅速发展,图论也得到了飞速发展,而图论中发展最快的领域也许就是控制数理论的研究.有向图的核作为众多控制参数之一,由于它在现实世界中,例如博弈论、编码理论、逻辑学、选址科学等理论与实践中有着广泛而深刻的应用背景,受到了越来越多的研究人员的关注. 设图D=(V,A)是无环无多重弧的有限有向图,但是允许成对方向相反的弧存在.V和A分别为有向图D的顶点集和弧集.设S(∈)V,若V-S中的每一个点均可通过一条弧指向S中的一点,则称S为D的吸收集.如果集合K(∈)V既是独立集又是吸收集,则称K为D的核.1944年,VonNeumann和Morgenstern在论述博弈论时介绍了有向图核的概念,这个概念来源于分配和控制理论.1981年,Kwa(s)nik将核的概念推广到了(k,l)-核上,其中k≥2,l≥1. 有向图核理论的研究主要集中在各种有向图类核的存在性上.然而,通过分析有向图的结构性质来研究核的存在性不太容易.于是,人们从另外一个角度进行研究,发现了有向图D及其线图L(D)中半核(拟核)之间的关系.因此,仍有可能发现有向图及其线图中广义核的关系.本文主要研究了有向图及其线图中的广义核,主要工作分为两个部分: 第一部分,我们证明了下述结果:有向图D存在k-半核当且仅当其线图L(D)中存在k-半核;D中k-半核的数目少于或等于L(D)中k-半核的数目;D中k-拟核的数目少于或等于L(D)中k-拟核的数目;D中k-核的数目等于L(D)中k-核的数目;刻画了仅存在一个k-拟核的有向图.这里k≥2. 第二部分,我们证明了:有向图D存在(k,l)-核当且仅当其线图L(D)存在(k,l)-核;D中(k,l)-核的数目等于L(D)中(k,l)-核的数目;D中(k,l)-半核的数目少于或等于L(D)中(k,l)-半核的数目;上述三种情况l<k.给出了两个存在(k,l)-核的有向图的运算,其中l>k.这里k≥2,l≥1.
其他文献
区域分解算法的思想最早是由德国数学家H.A.Schwarz于1870年提出来的.但是直到八十年代,由于该方法能将大型问题分解为小型问题、复杂边值问题分解为简单边值问题、串行问题分
本文讨论了几类二阶非线性椭圆型微分方程的区域振动性.本文所得结果推广了已有文献中相应的结论.此外,还通过一些实例,说明了相应准则的应用.全文共四章。 第一章为综述,简
继RSA之后,椭圆曲线的密码体制成为公钥密码体制的热点,目前正越来越广泛地应用于保密通信和数字签名。在椭圆曲线上建立密码体制主要依赖于椭圆曲线上离散对数问题(ECDLP)的困
BT是BOT的一种变形方式。BOT融资在实际运作过程中产生了许多变形,BT(Build建设-Transfer转让)就是BOT的一种历史演变,即政府通过特许协议,引入国外资金或民间资金进行专属于政府
期刊
学位
本文第一部分首先给出分布函数属于D(∧)吸引场的充要条件:(1)若F∈D(∧),则对任意的αm>0,m>1有1-∫x0x[∫x0y1…[∫x0yx-1(1-F(t))αmdt]αm-1…dy2]α1dy1∈D(∧) (2)若存在
本文主要研究非线性互补问题,提出了一个求解非线性互补问题的微分方程方法并进行了相应的数值实现。 第一章介绍了互补问题的背景。研究互补问题,大致分为理论和算法两大方