（运筹学与控制论专业论文）有向图的核理论.pdf

! ! 塑生土鲞太堂亟主堂焦迨塞! 摘要 在过去的三十多年里，随着计算机科学的迅速发展，图论也得到了飞速发展， 而图论中发展最快的领域也许就是控制数理论的研究有向图的核作为众多控制 参数之一，由于它在现实世界中，例如博弈论、编码理论、逻辑学、选址科学等理 论与实践中有着广泛而深刻的应用背景，受到了越来越多的研究人员的关注 设图d = ( ua ) 是无环无多重弧的有限有向图，但是允许成对方向相反的弧 存在v 和a 分别为有向图d 的顶点集和弧集设s v 若y s 中的每一个 点均可通过一条弧指向s 中的一点，则称s 为d 的吸收集如果集合v 既是 独立集又是吸收集，则称k 为j 7 ) 的核1 9 4 4 年，v o nn e u m a n n 和m o r g e n s t e r n 在论述博弈论时介绍了有向图核的概念，这个概念来源于分配和控制理论 1 9 8 1 年，k w a i n i k 将核的概念推广到了( k ，z ) 一核上，其中k 2 ，f 兰1 有向图核理论的研究主要集中在各种有向图类核的存在性上然而，通过分 析有向图的结构性质来研究核的存在性不太容易于是，人们从另外一个角度进 行研究，发现了有向图d 及其线图l ( d ) 中半核( 拟核) 之间的关系因此，仍有 可能发现有向图及其线图中广义核的关系本文主要研究了有向图及其线图中的 广义核，主要工作分为两个部分： 第一部分，我们证明了下述结果：有向图_ d 存在自半核当且仅当其线图l ( d ) 中存在砖半核；d 中七_ 半核的数目少于或等于l ( d ) 中“半核的数目；d 中七一 拟核的数目少于或等于l ( d ) 中一拟核的数目；d 中“核的数目等于l ( d ) 中一 核的数目；刻画了仅存在一个一拟核的有向图这里k 芝2 第二部分，我们证明了：有向图d 存在( ，1 ) 核当且仅当其线图l ( d ) 存在 ( k ，z ) 一核；d 中( k ，f ) 一核的数日等于l ( d ) 中( 七，f ) 一核的数目；d 中( k ，? ) 一半核的 数目少于或等于l ( d ) 中( k f ) 一半核的数目；上述三种情况f 这里k 2 ，f 1 关键词： 有向图；核；拟核；k - 核；( ，1 ) - 核 ! ! 堕芏土塑盔堂亟主堂僮迨塞 ! ! a b s t r a c t w i t h i nt h el a s tm o r et h a nt h i r t yy e a r s ，c o n c u r r e n tw i t ht h eg r o w t ho fc o r n p u t e rs c i e n c e ，g r a p ht h e o r yh a ss e e ne x p l o s i v eg r o w t h p e r h a p st h ef a s t e s tg r o w i n g a r e aw i t h i ng r a p ht h e o r yi st h es t u d yo fd o m i n a t i o ni ng r a p h s a so n eo fm a n y d o m i n a t i o np a r a m e t e r s ，k e r n e l si nd i g r a p h sw h i c ha t t r a c ta t t e n t i o nf r o mm o r ea n d m o r er e s e a r c h e r s & r ea t t r i b u t a b l em a i n l yt oi t ss om a n ya p p l i c a t i o n st or e a lw o r l d p r o b l e m s ，s u c ha sg a m et h e o r y ；c o d i n gt h e o r y , l o g i ca n df a c i l i t yl o c a t i o n l e td = ( va ) b eaf i n i t ed i g r a p ht h a td o e sn o th a v em u l t i p l ea r c so rl o o p s ， b u tp a i r so fo p p o s i t ea r c sa l l o w e d ，w h e r evi st h es e to fv e r t i c e sa n dai st h e s e to fa r c s as e ts vi sa b s o r b e n ti fe v e r yv e r t e xo fv gh a sas u c c e s s o r i ns as e tk c vi sak e r n e li fki sb o t hi n d e p e n d e n ta n da b s o r b e n t t h e c o n c e p to fk e r n e l si nd i g r a p h sh a v et h e i ro r i g i ni nt h ec o n c e p t so fi m p u t a t i o n sa n d d o m i n a t i o nd e v e l o p e db yv o nn e u m a n na n dm o r g e n s t e r ni nt h ec o n t e x to fg a m e t h e o r yi n1 9 4 4 i n1 9 8 1 ，k w a n i kg e n e r a l i z e dt h ec o n c e p to f ak e r n e lt ot h ec o n c e p t o fa ( ，f ) 一k e r n e l ，w h e r ek 2 ，l 1 s t u d i e si nk e r n e lt h e o r yh a v ec o n c e n t r a t e dm a i n l yo nt h ee x i s t e n c eo fk e r n e l s i nv a r i o u sf a m i l i e so fd i g r a p h s h o w e v e r ，i ti sn o te a s yt os t u d yt h ee x i s t e n c eo f ak e r n e lb ya n a l y z i n gs t r u c t u r a lp r o p e r t i e so fad i g t a p h i na n o t h e ra t t e m p t ，t h e r e l a t i o n sb e t w e e ns e m i k e r n e l s ( r e s p q u a s i k e r n e l s ) o fad i g r a p hda n ds e m i k e r n e l s ( r e s p q u a s i k e r n e l s ) o fi t sl i n ed i g r a p hl ( d ) w e r ef o u n d s oi tm a yb ep o s s i b l e t of i n dr e l a t i o n sb e t w e e ng e n e r a l i z e dk e r n e l so fd i g r a p h sa n dt h o s eo ft h e i rl i n e d i g r a p h s i nt h i sp a p e r ，w es t u d yg e n e r a l i z e dk e r n e l si nd i g r a p h sa n dt h e i rl i n e d i g r a p h s ，a n dt h ef o l l o w i n gt w op a r t sa r eo u rm a i nr e s u l t s ： i nt h ef i r s tp a r t ，w ep r o v et h ef o l l o w i n gr e s u l t s ：ad i g r a p hdh a sak - s e m i k e r n e l i fa n do n l yi fi t sl i n ed i g r a p hl ( d ) d o e s ，a n dt h en u m b e ro fk - s e m i k e r n e l si nd i sl e s s t h a no re q u a lt ot h en u m b e ro fk - s e r a i k e r n e l si nl ( d ) ；t h en u m b e ro fk - q u a s i k e r n e l s ! ! 竖生土塑盔堂亟堂鱼迨塞! ! ! i ndi sl e s st h a no re q u a lt ot h a ti nl ( d ) ；t h en u m b e ro fk - k e r n e l si nd i se q u a lt o t h a ti nl ( d ) ；w ec h a r a c t e r i z ead i g r a p hw i t hp r e c i s e l yo u ek - q u a s i k e r n e l i nt h i s p a r tw ea s s u n - l e 22 i nt h es e c o n dp a r t ，w es h o wt h a tad i g r a p hdh a sa ( ，2 ) 一k e r n e li fa n d o n l y i fi t sl i n ed i g r a p hl ( d ) d o e s ，a n dt h en u l l l b e ro f ( 七，? ) 一k e r n e l si nd i se q u a lt ot h e n u m b e ro f ( k ，f ) 一k e r n e l si nl ( d ) ；t h en u m b e ro f ( k ，f ) 一s e m i k e r n e l si nd i sl e s st h a n o re q u a lt ot h a to f ( k ，f ) s e m i k e r n e l si nl ( d ) ；i na b o v et h r e ec a s e s ，z i nt h i s p a r tw ea s s u m ek 2 f 1 k e yw o r d s ：d i g r a p h ；k e r n e l ；q u a s i k e r n e t ；k - k e r n e l ；( 七，) - k e r n e l 原创性声明 本人声明：所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 签名：鲁勤 日期：2 吖年6 , e l 肟日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容 保密的论文在解密后应遵守此规定 签名：导师签名 日期：伽僻月厂日 建翻关 2 0 0 6 年上海大学硕士学位论文 第一章引言 本章主要介绍有向图核理论的产生背景、应用领域及其主要研究方向，最后 指出了本文所做的主要工作 1 1 有向图核理论的产生背景和应用领域 近几十年来，随着计算机技术和网络通讯技术的飞速发展，图论研究也呈现 出异常活跃的趋势由于在现实世界和理论研究中广泛而深刻的应用，图的控制 数理论成为其中发展最快的研究领域之一+ 有向图的核( k e r n e l ) 作为众多控制参 数之一，因为其涉及的问题是图论中重要的优化问题，理论内涵深刻，并可以归属 于“位置确定”类的数学问题，有着广泛的实际背景与应用前景，所以受到国内外 学者的重视 有向图的核的概念是v o nn e u m a n n 和m o r g e n s t e r n 5 2 】在1 9 4 4 年研究经济 学中的博弈论时提出的，也就是说这一概念最初来自于图论的外部有向图的核理 论不仅从图论本身的研究角度来看具有重要意义，而且在相关学科例如博弈论， 逻辑学和选址理论等领域也有重要的应用价值有向图的核理论能够愈来愈受到 国内外学者重视的原因是由于其内在的研究价值以及对相关学科的指导作用共同 决定的，归纳起来主要有以下三个方面的原因； ( 一) 有向图的核理论在现实世界和诸如“选址”、“设备定位”等数学模型研 究中有着广泛而深刻的指导意义现实中的许多问题模型都可以归结为有向图的 核问题( 有向图的解( s o l u t i o n ) 是d 的逆图d 。中的核，因此下述解的应用的例 子也可以看作有向图核的应用) 例如设d = ( v a ) 是有向图，顶点代表“位置”， 如果从位置u 可以到达位置w ，则存在一条从位置札到位置”的弧假设每个位 置都有一个权重，这里权重是与我们要研究的设备定位相关的一些参数选择位 置集合的一个子集s ，使得集合s 外面所有的位置都可以由s 中的位置经某一条 弧到达，这意味着所有的位置都能接受到s 中位置的“服务”令训( s ) 代表s 中 元素权重的总和这个集合s 就是有向图的解 ! ! ! ! 生土塑太堂亟堂焦迨塞 ! ( 二) 人们发现有向图的核与染色理论中的两个著名猜想一完美图猜想和l i s t 染色猜想密切相关1 9 8 8 年，b e r g e 和d u c h e t i7 】提出著名猜想：一个图是完美 图( p e r f e c tg r a p h ) 当且仅当它是核可解的( k e r n e l - s o l v a b l e ) 也就是这个图的正规 定向( n o r m a lo r i e n t a t i o n ) 存在核 1 9 9 2 年，m a f f r a y 4 b l 证明了这一猜想在线图 上是正确的1 9 9 6 年，b o r o s 和g u r v i c h 8 】利用博奕论证明了完美图一定是核可 解的至今，猜想的另一半仍未被解决l i s t 染色猜想可叙述为：每个图的边l i s t 染色数等于它的边色数，也就是每个线图的l i s t 染色数等于它的色数1 9 9 5 年， g a l v i n1 2 5 l 利用定向图的核巧妙的证明了上述猜想x 十- - 部图是成立的至此，人 们开始认识到有向图的核理论的重要性其实，有向图的核理论早在1 9 7 4 年就被 c h v g t t a l 和l o v & s z i l ：j 】所关注，他们证明了每个有向图必存在拟核( q u a s i k e r n e l ) ， 现在被称为”c h v g t a l l o v a s zt h e o r e m ”2 0 0 3 年，b o n d y l 5 1 给出了这一定理的一 个简化证明 ( 三) r u d e a n u 【5 0 i 于1 9 6 4 年，r o y l 4 9 1 于1 9 7 0 年用算法构造了有向图d 的 所有的核l o u l m 虹s 在f 4 4 1 中给出了用树搜索和动态规划寻找有向图的独立集 的算法f r a e n k e l 2 0 确定了一个有限的有向图d 是否存在核k 或者g r u n d y 函数9 的问题是n p 一完全问题甚至当d 是一个度数限制为o ( d ) 2 ，i ( d ) 2 ， o ( d ) + i ( d ) 茎3 时的有圈平面有向图这些结论是最好可能的( 当尸p 时) 如 果任何限制条件都是紧的时候，存在多项式算法要么可以计算出核k 和g ，要么 显示二者都不存在对这两个问题的证明使用的都是源自平面3 一适定问题的简单 的递归方法 和众多的理论一样，有向图核理论也来源产生于实践当中现实世界中深刻而 广泛的应用背景是这一理论能够受到国内外学者重视并得以快速深入发展的重要 原因之一目前，有向图的核理论的应用领域主要有博奕论、编码理论、逻辑学、 选址科学等等下面我们来看两个应用实例 博奕论用( 1 ) ，( 2 ) ，：( n ) 代表n 个局中人，假设这礼个局中人可以在一起 讨论从集合x ( “位置”的集合) 中选择点z 如果局中人( i ) 偏好于选择位置( a ) 而不偏好于选择位置( b ) ，我们记作a 2b 由于个体偏好可能不相容，因此有必 ! ! ! ! 生上塑盔堂亟堂焦迨塞 ! 要介绍有效偏好的概念如果存在一个由局中人组成的集合满足集合中的这些局 中人偏好位置a 而不偏好位置b ，则位置a 被称为相对于位置b 的有效偏好，或 a b 然而有效偏好不具有传递性，即a b ，b c 并不一定可以推出a c 考虑有向图d = ( va ) ，o ( x ) 代表相对于z 的有效偏好位置的集合令s 是 d 的一个核 v o nn e u m a n n 和m o r g e n s t e r n 建议位景选择可以限制到集合s 的 元素上因为s 是独立的，因此s 中不存在某个位置有效偏好于s 中的任何其他 位置；因为s 是吸收的，对于每一个位置z s ，s 中总存在一个位置是相对于z 的有效偏好，因此可以立即排除x ，不用选择 逻辑问题我们考虑由性质组成的集合p = 扫，p = ，) 和具有以下特征的定 理的集合q ：“由性质m 可以推出性质翰”根据pq 可以构造有向图d = ( k ) ， 这个有向图d 还要满足以下条件：存在顶点集p ，其中p ( ，p o ) ) 是一条弧( 有向 边) 当且仅当它遵循一个或多个q 中存在的由p ( t ) 可以推出) 的定理假设我 们想表示补图d 中没有弧足以表示某种确切的含义，更准确地说，对于每一条弧 如，g ) 且p g 而( p ，g ) 隹a ：我们指派一个学生一定要找到一个满足p 但是不满足 q 的例子( 即：找出由p 可以推出q 的反例) 在文f 9 中他们指派学生去列举所有可能( 成对) 的表述，从而确定了需要指 派的学生的最小数目可以在有向图口中表示出来他们也发现了这个数目对应于 有向传递图( t r a n s i t i v ed i g r a p h ) 中唯一核的基数 随着有向图的核理论研究的继续深入，新的应用领域仍然不断涌现 1 2 主要研究方向 近几十年来，有向图的核理论一直是图论研究中的热点之一这其中的研究 方向主要集中在以下几个方面： ( 1 ) 核，一核和( ，2 ) 一核的存在性，其中k 2 ，f21 ； ( 2 ) 核理论在染色理论中的应用； ( 3 ) 核理论在博奕论中的应用； ! ! ! ! 生土塑盔堂亟堂焦鲨塞 ! ( 4 ) 核完美临界图的构造； ( 5 ) 有向图核理论在相关学科中的应用研究等等 1 - 3 本文的主要工作 有向图的( k ，2 ) 一核( ( ，f ) 一k e r n e l ) 概念是核( k e r n e l ) 和拟核( q u a s i k e r n e l ) 概念 的推广，侧重对广义核的研究，这里k 2 ，2 l ，本文所做的主要工作是： ( 1 ) g a l e a n a - s a n c h e z 等在文3 1 中证明了有向图的核和拟核分别不超过其线 图( 1 i n ed i g r a p h ) 的对应集的数目；1 9 9 8 年，g a l e a n a - s a n c h e z 和l i 在 2 7 中给 出了几类广义核在有向图和它的线图之间的数量关系在上述基础上，我们找出 有向图的女一半核( k - s e m i k e r n e l ) 、k - 核( k - k e r n e l ) 和七一拟核( k - q u a s i k e r n e l ) 与其 线图的这些集之间的数量关系，刻画了仅存在一个一拟核的有向图 ( 2 ) 当有向图的围长至少为且f k 时，两个存在 ( k ，z ) 一核的有向图的运算 本文的主要结构是：第一章引言部分主要介绍了有向图核理论的背景及应用； 第二章给出了图论中有向图的一些基本概念和记号以及核问题的一些基本结论； 第三章中我们研究了有向图及其线图中的一半核，k 一拟核，k 一核这些集合之间的 关系，并刻画了仅有一个詹一拟核的有向图；第四章主要讨论了当f 时，两个存在 ( k ，f ) 核的有向图的运算 2 0 0 6 年上海大学硕士学位论文 5 第二章基本符号和结论 2 1 基本概念和记号 本文所讨论的图均是无环无多重弧的有限有向图，但是允许成对方向相反的 弧存在凡是文中未加定义的术语和符号，可参看文献1 ，3 ，4 1 为了叙述方便， 我们首先引入一些定义和记号设d = ( v ( d ) ，4 ( d ) ) 是有向图，其中v ( d ) 是非 空顶点集，a ( d ) 是不同的点的有序对的一个集合每一个这种有序对( z ，y ) 称 为d 的一条弧或者有向边对于弧( x ，) ，则称。为y 的头，y 为。的尾 如果d 中也存在弧( y ，z ) ，则称弧( x ，y ) 是可逆( 或对称) 弧如果( z ) a 而( y ，z ) 岳。4 ，则称( 岱，y ) 为非对称弧如果对于某一正整数k ，我们有一点序列 盯= ( x o ，z h ，z k ) 使得每一个z 。+ 1 都是甄的尾，则口是一条从x o 到x k 长度为 k 的有向迹如果所有的戤均不相同，则a 是一条有向路，记作x o - x 有向路 如果有向路盯= ( z o ，z ，孤) 中z o = z 女，则一是一个有向圈有向图d 的围 长是指d 中最短有向圈的长度，记作9 ( d ) 有向距离d d ( x y ) 是在有向图d 中 从x 到y 的最短有向路的长度 对于有向图d 中点z v ，x 的一外邻集，定义为o k 扛) = v ：1 d d ( x ，y ) s 砖k - 内邻集，定义为l k ( x ) = v ：l d d ( y ，z ) sk ) 而且如 果s v ，则我们记o k ( s ) = u 。；so k ( 5 ) ，l k ( s ) = u 。s ( s ) 特别地，0 1 ( z ) 和 ，( z ) 通常被称为z 的外邻集和内邻集另外，我们特别记0 ：d 女( z ) = y v ： d d ( x ，y ) = k ：k 1 ) ，岛( z ) = v ：d d ( y ，z ) = k ，k 1 ) d 中点z 的人度用 i d ( x ) = i 厶( z ) l ：出度用o d ( x ) = l o ，( z ) 1 表示如果顶点z 的出度o d ( x ) = 0 ，则称 z 为收点( s i n k ) 如果对任意z ，y s v 且。满足d d ( z ，y ) 三，k 2 ，则 称s 为b 距离独立集0 袭k - 稳定集) 当k = 2 时，s 即是通常所说的d 的独立 集 d 的线图l ( d ) = ( y ( 工( d ) ) ，a ( l ( d ) ) ) 以d 的弧集为顶点集且对任意弧 a l ，a 2 a ( d ) ，存在弧( a 1 ，a 2 ) a ( l ( d ) ) 当且仅当相应的弧a l ，a 2 在d 中可 以导出一条有向路，即弧a 1 的尾是弧a 。的头下文中我们用相同的符号表示弧 ! ! ! ! 生土竖盔堂亟堂焦迨塞鱼 o = ( z ，y ) a ( d ) 和点a a ( l ( d ) ) 如果h 是图d 中的一个弧集，则j h 也是 其线图l ( d ) 中的一个顶点集当我们想表示a ( d ) 是l ( d ) 的顶点集时， 就用标记e k 代替h 我们定义集合s v 为有向图d 的f 一控制集，如果对所有的v 譬s ，都存在一 条从s 中的某个点8 到v 的长度至多为f 的有向路，这里2 芝1 当f = 1 时，s 就 是通常意义上的控制集如果集合s 既是独立集又是控制集，则称s 为有向图的 解给定有向图d = ( k 4 ) ，则有向图d _ 1 称为d 的逆图，其中v ( d ) = v ( d - 1 ) 和( 茁，9 ) a ( d ) 当且仅当( y ，z ) a ( d 。) 有向图d 是强连通的，如果对于每 - x 十顶点z y ，存在从z 到的有向路，也存在从y 到z 的有向路称有向图_ d 是有向传递图，如果对y 中任意构成三角形的三个顶点z ，y ，z ，若存在( z ，y ) a ( y ，：) a 就存在( 。，z ) a 如图2 11 可 ，。 图2 1 1 ：有向传递图 如果有向图d 中只要存在弧( ，g ) a ( d ) 就存在弧( y ，z ) a ( d ) ，则称d 为对称有向图如果有向图d 的所有导出子图都存在核，则称d 为核完美图有 向图d 是核完美临界图，如果d 中不存在核而d 的每个真导出子图存在核我们 记a s y m ( d ) 为有向图口中的非对称边的生成子图无向图g 是完美图，如果对 g 的每一个导出子图日满足日中的色数等于最大团的阶数，即，x ( u ) = u ( h ) 有向图中的有向团的基础图是完全图有向图d 是正规的，如果_ d 中的每个 有向团都存在核，也称d 的基础图g 有一个正规定向 定义2 1 1 设集合s y ，若y s 的每个点都有尾在s 中，则s 是吸收集 如果集合v 既是独立集又是吸收集，则k 是核 我们注意到有向图d 的解即是d - 1 的核，因此往往将解的问题转化为核的 问题来处理核的这个概念之所以重要，是因为它直接产生于n 个局中人的合 作博弈论( c o o p e r a t i v en p e r s o ng a m e ) ，n i m - 型博奕论( n i m t y p eg a m e ) ，逻辑学 ! ! ! ! 生土鲞盘堂亟堂鱼监塞! 等，并且在理论上v o nn e u m a m n 和m o r g e n s t e r n 5 2 1 ，r i c h a r d s o n 4 8 1 ，d u c h e t 和 m e y n i e l 1 6 ，g a l e a n a - s 6 n c h e z 和n e u m a n n l a r a 2 8 等人已经对核进行了深入研 究h a y n e s 【3 4 】等人写了一份关于有向图核的综述，对有向图核理论的发展作了 大概的介绍k w a n i k 3 7 1 将核的概念推广到( 女，f ) 一核的概念如下： 定义2 1 2 设，f 为整数且k 三2 ，f 1 我们称j v ( d ) 为d 的( k ，2 ) 一核， 如果 口，j 是d 的七一距离独立集，即，对每个顶点对 z ，z 7 ) 至d ，z x 7 ，都有 d d ( x ，z ) 七 俐对每个顶点y v ( d ) 一j ，存在z j 使得d d ( y ，z ) f 特别地，( k ，k 一1 ) 一核也被称为七一核当七= 2 时，我们即得到了b e r g e 在 1 1 中定义的核我们也定义( k ，2 k 一2 ) 一核为如拟核( k - q u a s i k e r n e ) ，当k = 2 时，即 是c h v f i t a l 和l o v & s z 1 3 】介绍的通常意义上的拟核( q u a s i k e r n e l ) 定义2 1 3 有向图d 的k 一半核亿一s e m i k e r n e l ) s 是k 一距离独立集，且对任意一 顶点z v ( o ) s ，如果存在一条长度至多为k l 的s ，z 有向路，也存在一条 长度至多为一l 的z s 有向路，这里k 2 当k = 2 时，2 一半核是n e u m a n n l a r a 在 4 6 】中介绍的半核显然，七核是 七一半核，但不是每个一半核都是k 核一半核的概念对于研究核在有向图中 的存在性有一定的作用 1 9 3 9 年，g r u n d y l 3 2 1 在无圈有向图上介绍了g r u n d y 函数的概念b e r g e 和 s c h i i t z e n b e r g e r 在 1 0 中将这个概念推广到任意有向图上为了研究一核，我们 进一步将这个概念推广如下： 定义2 1 4 设z l 且为整数，非负整函数g ( x ) 称为口的f 一外邻集g r u n d y 函数如果对每一个顶点z ，g ( x ) 是不属于集合 g ( 目) 旧0 f ( z ) ) 的最小的非负整 数 当对f = i 时，称2 一外邻集g r u n d y 函数为d 的g r u n d y 函数 1 - 外邻集g r u n d y 函数也被定义为函数g ( x ) 使得 ! ! ! ! 生土塑盔堂亟堂鱼鲨塞 ! r 9 ( 。) = m 0 满足对任意0 j 0 ，r20 ，2 rst ( r 1 ) 时n = t ( 1 + r + s ) + 2 r 如果r 是偶数，则有向图d ( n ，r ，s ) 是核完美图 ! ! ! ! 生土连太堂亟堂鱼迨塞! ! 定理2 2 1 3 ( 2 9 1 ) 如果r = l ，s 1 且( s 十2 ) 不整除n ，则d ( n ，r ，8 ) 是核完美 临界图 b e r g e 和d u c h e t i7 ) 提出一个猜想将完美图和核完美图联系了起来，并且这一猜想 的必要条件已经在文 8 中被证明 猜想2 2 1 ( 7 ) 无向图g 是完美图当且仅当g 的任何正规定向都存在核 k w a n i k 3 7 1 将核的概念推广得到了( k ，f ) 核的概念，并进行了大量的研究，一些结果 在文f 3 8 ，3 9 ，4 0 ，4 1 ，4 3 中体现g a l e a n a - s g n c h e z l 2 4 ，2 7 3 0 j ，c h v g t t a l ，l o v g s z 1 3 】 等人也在( 七，f ) 一核等广义核的存在性研究方面做出了很大的贡献 定理2 2 1 4 ( 1 3 ) 任何有向图都存在拟核，即( 2 ，2 ) 一核 定理2 2 1 5 ( 2 r ) 每个有向图都存在k - 拟核，即( k ，2 ( k 1 ) ) 一核，这里2 定理2 2 1 6 ( 【4 1 ) 每个有向图都存在( ，k ) 一核，这里k 2 定理2 2 1 7 ( 【2 4 ) 设d 是满足下列条件的有向图： 门，存在m o v ( d ) 使得对每一个顶点z v ( d ) 在d 的非对称生成子图 a s y m p j 中都存在一条从x 到? t t 0 的长度为h ；i ( m o d 七) 的。一m o 有向迹和一 条m o o 有向迹，这里0 茎i 兰 俐每一个有向圈7 且l ( - y ) o ( m o dk ) 满足下列条件之一： 陋j7 的每一条弧都是d 的对称弧； 阳j7 有至少k 条对称弧 则d 存在( ：f ) 核 在文3 3 中h a r m i n c 考虑了一个给定有向图d 的线图中核的存在性，他证 明了下述结果： 定理2 2 1 8 ( 3 3 ) 有向图d 中核的数目等于其线图l ( d ) 中核的数目 d u c h e t ，h a m i d o u n e 和m e 3 m i e l 1 ，l 推广了这个结果，g a l e a n a - s a n c h e z p a s t r a n a - r a m i r e z 和r i n c 6 n m e j i a 在【3 1 】中证明了下面的结果： 定理2 2 1 9 ( a 1 1 ) 如果d 是有向图且每个顶点的入度至少为1 ，则d 的拟核的 ! ! ! ! 生土堡盔主亟堂焦迨塞 ! ! 数目少于或者等于其线图l ( d ) 中拟核的数目 定理2 2 2 0 ( 2 7 ) 如果d 是有向图且每个顶点的入度至少为 当且仅当其线图l ( d ) 存在半核 定理2 2 2 1 ( 3 1 ) 如果d 是有向图且每个顶点的入度至少为 数目少于或者等于其线图l ( d ) 中半核的数目 1 ，则d 存在半核 1 ，则d 的半核的 定理2 2 2 2 ( 3 1 ) 如果d 是有向n 2 - 每个顶点的入度至少为1 ，则d 中g r u n d y 函数的数目少于或者等于其线图l ( d ) 中g r u n d y 函数的数日 g u t i n ，k o h 等人对存在拟核的有向图进行了刻画 定理2 2 2 3 ( 2 6 ) 有向图d 只存在一个拟核当且仅当d 存在收点且d 的每一 个非收点控制收点如果有向图d 仅有一个拟核q ，则q 是一个核且由d 中的 收点构成 定理2 2 2 4 ( 2 6 ) 设d 是不合收点的有向图则d 恰好存在两个拟核当且仅当 d 存在导出4 - 圈或2 圈e ，使得c 中没有任何点控制d v ( c ) 中的点且每一 个d v ( c ) 中的点控制c 中至少2 个相邻的点 g r u n d y 函数与有向图的核之间有着紧密的联系对于g r u n d y 函数也有相似 的结论：并不是所有的有向图都存在g r u n d y 函数，例如有向5 一圈就不存在g r u n d y 函数而图2 2 3 所示的有向图却存在不只一个g r u n d y 函数 o l o 图2 2 3 1 0 事实上，如果d 存在g r u n d y 函数g ，则d 存在核因为集合s = z ：z k g ( x ) = o ) 满足： ( 1 ) z s 号g ( z ) =