论文部分内容阅读
在过去的三十多年里,随着计算机科学的迅速发展,图论也得到了飞速发展,而图论中发展最快的领域也许就是控制数理论的研究.有向图的核作为众多控制参数之一,由于它在现实世界中,例如博弈论、编码理论、逻辑学、选址科学等理论与实践中有着广泛而深刻的应用背景,受到了越来越多的研究人员的关注.
设图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.