（基础数学专业论文）图的半强自同态.pdf

兰州大学2 0 0 7 届硕士学位论文 摘要 图的自同构把图与群联系起来，成为图论研究中的一个重要而有效的方法图 的自同态把图和半群联系在了一起。可望应用于图论研究中自同态、半强自同 态、局部强自同态、拟强自同态、强自同态和自同构构成图的自同态的分层图的 所有自同态、强自同态和自同构都构成幺半群，而所有半强自同态、局部强白同态 和拟强自同态一般不构成半群m b o t t c h e r 和u k n a u e r 提出了如下的一个公开问 题：图满足什么条件时，它的所有半强自同态( 局部强自同态、拟强自同态) 构成幺 半群? 显然要给出这个问题的一个普遍的回答是十分困难的本文我们主要就两类 图解答上述问题 第一章和第二章主要介绍研究背景、预备知识以及半强、局部强和拟强自同 态的有关基本结果 第三章讨论和刻画了n 棱柱的半强自同态、局部强自同态、拟强自同态和强 自同态证明了n 棱柱的拟强自同态都是强自同态，且它的所有半强、局部强、拟 强自同态都构成幺半群 第四章讨论和刻画了连通分裂图的半强、局部强和拟强自同态，分别给出了它 们形成幺半群的充要条件，在分裂图范围内回答了m b o r n ：h e r 和u k n a u e r 提出的 公开问题 关键词：分裂图，n 棱柱，自同态。半强自同态，局部强自同态，拟强自同态，强自同态 兰型盔兰! 竺：星堡圭茎垡丝苎 a b s t r a c t t h ea u t m o r p h i s m so f g r a p hc o i l n e c t sg r o u pw i t hg r a p ht h e o r y , a n db e c o m i n ga ni r a - p o r t a n ta n de f f e c tw a yi nt h es t u d y i n go ft h eg r a p ht h e o r y t h ee n d o m o m o r p h i s m so f g r a p hl i n k st h es e m i g r o n pt og r a p ht h e o r y , a n dw ee x c e p tt oa p p l y i ti ng r a p ht l l c 脚y h o - m o m o 删s m , h a l f - s t r o n g ，l o c a l s t r o n g ，q u 髂i s t r o n ga n ds t r o n ge n d o m o s p h i s mf o r mt h e l a y e r so ft h eh o m o m o r p h i s mo fg r a p h t h ee n d o m o m o r p h i s m s ，s t r o n g - e n d o m o r p h i s m s a n da u t o m o r p h i s m so fg r a p hf o r mm o n o i d s 。b u tt h eh a l f - s t r o n gl o c a l - s t r o n ga n dq u a s i s t r o n ge n d o m o r p h i w sc a n tf o r mm o n o i d sg e n e r a l l y m b o t t o h e ra n du 。k n a u e rr a i s e d a no p e nq u e s t i o n ：u n d e rw h i c hc o n d i t i o n sd ot h es e t sh e n d x l e n d x , q e n d xf o r m m o n o i d s 7e v i d e n t l y , t og i v et h ea n s w e rg e n e r a l l yi sd i f f i c u l t , s oi nt h i sp a p e r , w em a i n l y a n s w e tt h eq u e s t i o no nt w oc l a s s e so fg r a p h w em a i n l yi n l r o d u c et h eb k | 舢d ，p r e l i m i n a r i e sa n ds o m eb a s i c 他s 1 1 1 to fh a l f - s t r o n g ，l o c a l s t r o n g ，q l l a s i s t r o n ga n ds o n ge n d o m o r p h i s m si nc h a p t e r1a n dc h a p t e r 2 i nc h a p t e r3 ，w ed i s c u s sa n dc h a r a c t e rt h eh a l f - s 仰o n g 。l o c a l - s t r o n ga n dq u a s i - s t r o n g e n d o m o r p h i s m so f n - p r i s m , a n dp r o v e t h a tq u a s i - s t r o n ge n d o m o r p h i s m so f i ti ss t r o n g a l l t h eh a l f - s t r o n g ，l o c a l - s t r o n ga n dq u a s i - s t r o n ge n d o m o r p h i s m sf o r mm o n o i d sr e s p e c t i v e l y i nc h a p t e r4 ，w ed i s c u s sa n dc h a r a c t e rt h eh a l f - s t r o n g ，q u a s i s t r o n ge n d o m o r p h i s m s o fc o n n e c ts p l i tg r a p h ，a n dg i v et h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n su n d e rw h i c ht h e y f o r mm o n o i d s ，a n ds og i v ea na n s w e ro ft h eo p e nq u e s t i o nm b o t t c h e ra n du k n a u e r p o s e d i nt h es c o p eo f c o n n e c ts p l i tg r a p h k e yw o r d s ：s p l i tg r a p h , n - p r i s m s ，r e g u l a r , e n d o m o r p h i s m , h a l f - s t r o n ge n d o m o r p h i s m , l o c a l s t r o n ge n d o m o r p h i s m , q u a s i - s t r o n ge n d o m o r p h i s m , s t r o n ge n d o m o r p h i s m 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行 研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数 据、观点等，均己明确注明出处。除文中已经注明引用的内容外，不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究成果做 出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：筮垫! 芰 一日期： 竺塑： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州 大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校 保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查 阅和借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用任何复制手段保存和汇编本学位论文。本人 离校后发表、使用学位论文或与该论文直接相关的学术论文或成果时，第 一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：盘望堇：导师签名 兰州大学2 0 0 7 届硕士学位论文 第1 章序言 代数图论起源的年代已经无从知道，但它的重要性是毋庸置疑的代数 和图论这两种表面上似乎毫不相干的学科之间却存在着千丝万缕的联系某 些图论问题在考虑到一定程度之后，会发现这个问题用代数的方法解决更好 或从根本上就是一个代数问题同样，某些代数难题也会用图论的知识巧妙 的解决图及其自同构群的研究一直是图论中比较活跃的领域，也得到很多 很完美的结果而图之间的同构是图同态，特别的，一个自同构是一个图到它 自己的自同态但有许多的自同态不是自同构，因此图的自同态要比自同构 包含更多的信息。利用它可以得到更好的结果例如我们可以得到结论：图x 的色数是x 到坼有同态的最小数r 图的自同态要比自同构复杂得多，如 就这么一个简单的图，它只有一个自同构，却有1 0 1 个自同态，因此要找 出它的每一个具体自同态是很困难的事由于图的自同态关于映射的合成构 成一个幺半群，这样图及其自同态幺半群的研究也引起了图论学者和半群理 论学者的极大兴趣，而我们主要从三方面把半群和图论联系起来：图的自同 态，凯莱图，零因子图同其他数学分支讨论一个数学对象与它的保持运算的 自同态幺半群( 或自同构群) 一样，图与它的保持顶点相邻关系的自同态幺 半群的研究也是很有价值和意义的事实上讨论图的自同态幺半群就是要知 道图的组合结构与其自同态幺半群的结构之间的的本质联系利用图的自同 态幺半群的性质刻画图，或者利用图的组合性质把握变换半群乃至一般半群 的结构，给图论和半群理论注入新的活力文章【1 0 1 ， 1 1 】就是图及其自同 态幺半群方面的综述 而在图的自同态研究中，图的自同态正则性，图的强自同态一直是研究 的热点，也得出了很多很好的结果除此之外还有一些有特殊性质的自同态 兰州大学2 0 0 7 届硕士学位论文 如半强自同态在1 9 7 3 年h e l l 的文章和s a b i d u s s i 的文章中以全同态的名 字出现过。在1 9 7 8 年a n t c h e 和o l a m 的文章中以部分关联同态的名字出现 过。满局部强同态在1 9 8 0 年p u l t r 和t r n k o v a 的文章中出现过，而强自同态 是k c u l i k 的1 9 5 8 年的文章中首次考虑，当时的名字叫同态，之后被其他作者 引用而把图的自同态分为( 一般) 同态，半强自同态，局部强自同态，拟强自同 态强自同态。自同构是m i c h a e l b o t t c h e r 和u l r i c h k n a u e r 在1 9 9 0 年图的自 同态谱中首次定义并分类的其中图的强自同态由于有较好的性质已经有很 好的结果。而图的半强。局部强，拟强自同态由于其自同态构不成一个幺半群， 所以对它们的研究一直没有进展 m i c h a e l b o t t c h e r 和u l r i c h k n a u e r 在1 9 9 0 年图的自同态谱中提出了个问 题：图的半强，局部强，拟强自同态在什么条件下形成幺半群? 本文第四章通 过对分裂图的自同态研究。部分回答了这个问题本文第一二章首先介绍研 究背景、预备知识以及半强、局部强和拟强自同态的有关基本结果，在第三 章研究了n - 棱柱的所有自同态。为第四章作了些准备 2 兰州大学2 0 0 7 届硕士学位论文 第2 章预备知识 如果g 是一个图。我们把g 的点集记为v c g ) ，边集记为e g g ) 定义2 1 对于图g ，g ，如果y ( g ，) y ( g ) ，并且e ( g ，) 冬e g g ) ，那么图 g ，叫做g 的子图如果g ，是g 的子图，且g ，包含所有( z ，可) e ( g ) ，其中 z ，y g ，那么g ，是g 的一个导出子图 定义2 2 设x 与y 为两个图，为从v c x ) 到v c y ) 的映射如果，满足 z 和y 在x 中有一条边，蕴含着，( z ) 和y ( v ) 在y 中有一条边，那么，是一 个同态特别的，如果，是从x 到x 的同态，那么，就叫做x 的自同态我 们记e n d x 为图x 的所有自同态的集合 我们记f - 1 ( n ) 一p v ( g ) i ，( = a 如果a 是g 的一个子图，是g 的一个自同态。那么我们记，l 为，在a 上的限制 定义2 3 设g 是一个图，是g 的一个自同态g 的一个子图叫做g 在 ，下的自同态像，记作乃，如果v ( i i ) = ，( y ( g ) ) ，并且i f ( a ) ，只b ) ) e ( 0 ) 。 当且仅当存在c y - 1 ( ，( n ) ) ，d y - 1 ( ，( 6 ) ) 使得c ，d e ( g ) 其中o ，6 ，c ，d 都是g 中的点 定义2 4 设g 是一个图，e n d ( g ) 我们记力为v ( g ) 上由，所导出 的等价关系也就是说a ，b g ，( a ，b ) p f ，当且仅当y ( a ) = ，( 6 ) ，记作m 甜 定义2 5 设g 是一个图g 的一个子图叫做g 在p ，下的因子图，记 为g _ | 口，如果v ( c p 1 ) = v ( c ) p l ， 【口】肿， 6 】肿) e ( g p i ) ，当且仅当存在 c 【0 1 p ，d 【6 1p ， 使得 c ，田e ( g ) 我们定义i i ：v ( g p i ) 一v ( i i ) ，其中，( 吲以) = ，( z ) ，显然i i 有意义 定义2 6 设】s 是一个半群如果存在z s 。使得a l g a = a ，那么8 叫做正 则的，并且如果z = o 也成立，那么z 就叫做口的一个逆 我们都知道半群的每一个正则元都有一个逆元 兰州大学2 0 0 7 届硕士学位论文 定义2 7 如果个半群的所有元都是正则的，那么这个半群叫做正则的 定义2 8 如果半群s 中的一个元素a 满足o , 2 = a ，那么a 叫做s 的一个 幂等元 定义2 9 设s 是一个半群定义s 上的一个关系c ，使得( 8 ，厶如果 s 1 口= s 1 b 类似的，定义s 上的一个关系冗，使得( a ，6 ) 冗，如果a s l = b s l 显然冗和c 是s 上的等价关系定义7 l c = c n7 乙口= c v 冗这些等价关 系都叫做格林关系记矧c ( 冗，【n 1 咒) 为a 的关于c ( 冗，7 1 ) 的等价类 定义2 1 0 - 2 1 5 给出了图的自同态的一个分类。例子满足属于所定义的这 类同态，而不属于所定义的下一类同态箭头的末端是这个点的像，没标箭头 表示这个点是不动点令x 和y 为两个图，：x y 是一个映射，在例子 中x = y 定义2 1 0 如果同态，满足z ，一e ( x ) 蕴含着，( ) ，( 一) e w ) ，那么 映射，叫做一个( 一般) 同态， 符号：，h o m ( x ，y ) ，例 123 一厂i 台一台一毫 定2 2 1 1 如果同态，满足 ，( z ) ，f ( x 7 ) ) e ( y ) 蕴含着存在原像虿，z 也就是，( 牙) = ，( z ) ，s c ) = ，( z ，) ，使得 虿，孑) e ) ，那么，叫做一个半 强同态 符号：，h h o m ( x ，y ) ，例如 12 f 定义2 1 2 如果同态，满足 ，( z ) ，f ( x 7 ) ) e ( y ) 蕴含着对每一个，( z ) 4 兰州大学2 0 0 7 届硕士学位论文 的原像i x ，都存在，( 一) 的原像孑x ，使得 虿，孑) e ( x ) ，并且类似 的，对于，( 一) 的原像也要满足同样的条件，那么f 叫做一个局部强同态 符号：f l h o m ( x ，y ) ，例 12 l 二1 4 定义2 1 3 如果同态f 满足 ，( z ) ，) ) e ( y ) 蕴含着存在f ( x ) 的原 像z x ，满足善与，( 一) 的每一个原像都邻接，并且类似的，f ( e ) 的原像也 要满足同样的条件，那么，叫做一个拟强同态 符号：f q h o m ( x ，y ) ，例 12 定义2 1 4 如果同态，满足 ，( z ) ，( 一) e ( y ) 蕴含着，( 动的每一个 原像都与，( ) 的每一个原像邻接，那么，叫做一个强同态 符号：f s h o m ( x ，y ) ，例 1 2 定义2 1 5 如果，是一个双射，并且，以是一个同态，那么同态，叫做一 个同构 符号：f i s o ( x ，y ) 如果x = y ，那么我们把这些同态都相应的叫做自同态。或自同构，并且 显然有e n d x3h e n d x3l e n d x3q e n d x ) s e n d x ) a u t x 定义2 1 6 一条路是一个非空图p = e ) ，其中v = x o ，。l ，现 ， e = z o z i ，x l x 2 ，z 一1 钒 ，且所有的x i 互不相同，x o ，x k 叫做p 的端点 兰州大学2 0 0 7 届硕士学位论文 定义2 1 7 图g 中一条长度为的途径是一个非空点边交错序列 v o e o v l e l e k 1 ，使得e i = 地，饥+ 1 ) 对所有的i i ，i - i ( 一1 ) 有两 种情况： ( a ) i - 1 ( 啦! ) 冬 啦一1 ，龟+ 1 ，a 1 i 留+ 1 ) ， ( b ) f - 1 ( 一1 ) = 口i 一1 ，啦一3 ，) 或- 1 ( 一1 ) = a j + l ，叼+ 3 ，) 因为对- 1 ( 一1 ) 的任一种情况，f - 1 ( 一1 ) 中都存在一点在，- 1 ( ) 中 有一个点和它相邻接。所以，是半强的因为在情况( b ) 下。0 4 3 ，a 1 3 在- 1 ( ) 中不存在点和它相邻接，且即或锄在i - 1 ( 一1 ) 中也不存在 点和它相邻接，所以，不是局部强的在情况( a ) 下显然，是局部强的又 由( a ) 可得，满足若0 是从吼到砚+ 的k 长路，则kl 钍一1 ，且对任 意的o 。，a n i - 1 ( a d ，或a m ，a 。i - 1 ( 吼) ，都有，( o 。“) = ，( 肿f ) ，其 中1 i ，所 以j = i + 2 这样a i 和啦一1 ，田+ 1 相邻接，q + 1 与毗，o 件2 = 口j 相邻接 下面我们证i y ( 乃) i = 2 反之，假设还存在+ 1 y ( 乃) ，则( ，口0 1 ) e ( x ) 但只有m + 1 与啦，相邻接，而口件l 隹- 1 ( + 1 ) ，即在，- 1 ( + 1 ) 中 不存在点与1 - i ( 口，) 中的所有点相邻接，则，不是拟强的，矛盾所以我们 可以得到路x 的长度小于等于3 又因为若路的长度为1 ，所以q e n d x = a u t x ，因此x 的长度为2 或3 且若，( 啦) = f ( a j ) ，j i ，则歹= i + 2 充分性显然 命题3 1 5 设x 是一条路如果存在，s e n d x a u t x ，那么x 的长 度为2 ，且，( 口1 ) = ，( 口3 ) 证明显然若，s e n d x a u t x ，则，q e n d x a u t x 由命 题4 1 4 ，x 的长度为2 或3 若x 的长度为3 ，且，q e n d x a u t x ，显 然，隹s e n d x ，因此x 的长度为2 ，( 啦) = s ( a i + 2 ) ，即，( 0 1 ) = ，( ) 3 2 偶圈的半强自同态 命题3 2 1 设x = c h 为一偶圈如果f e n d x ，那么，h e n d x 1 0 兰州大学2 0 0 7 届硕士学位论文 证明令x = q 。为一偶圈， ，一 i ，则存在m = 0 一i ) 2 ( 显然m 为整数因为 由引理4 1 1 ，j l 为偶数) ，使得i f c 训p ，i = 1 ，且存在z = m + n ( m o c2 n ) ， 使得i 【o f 】盯i = 1 ，且f 【o d 以i = 2 ，对所有的k m ，j 所以从a m 到a l 的长 兰州大学2 0 0 7 届硕士学位论文 命题3 2 5 设x = 为一偶圈，e n d x 则，h e n d x 在 同样条件下若f l 研记x ，则，满足f = 拈，乃是从a i 到a i + k 的k 长路，ki n 一1 ，且对任意的，a n 6 - 1 ( 啦) ，或a m ，a n 6 - 1 ( 皿+ 1 ) ，都 有6 ( n ，叶f ) = j ( o 胂1 ) ，其中1 f k 如果存在f q e n d x a u t x ，当 且仅当x = q ，5 为恒等映射，或d ( 毗) = 6 ( 啦+ 2 ) 并且在同样条件下我们 有s e n d x = q e n d x 证明要证明，= 琵，只需要证明如果a m ，a nem 即那么 “，a n i 【口】且a m 而。州m 力我们先证口m + 1 ，a n 一1 嘲p ，且 a m 一1 ，a n + l 【0 】甜否则因为( a m ，口r ，件1 ) e ( x ) ，( ，( 口。) ，( 口。+ 1 ) ) e ( x ) ， a n f - 1 ( ，( ) ) ，没有f - 1 ( ，( + 1 ) ) 中的点和有边。由引理3 2 3 知，对 任意的a t ，a t + 1 厶，都存在6 - 1 ( 砚) 厶，和+ 1 6 以( 吼+ 1 ) l 由 引理3 2 3 知( o ：，+ 1 ) e ( x ) ，所以，是半强的 由引理3 2 3 知，对任意的砚，a t + l 1 6 ，我们只需要证明对任意 6 _ 1 ) s 厶，都存在+ 1 6 _ 1 ( m + 1 ) 厶使得( n ：，+ 1 ) e ( x ) ，反之 也成立由命题3 1 2 知，占为局部强的，当且仅当j ，是从口t 到坼k 的k 长路，kn 一1 ，且对任意的口。，a n 6 - 1 ( 啦) ，或n 。，a n 6 - 1 ( d 件1 ) ，都 有6 ( + 1 ) = 6 ( 0 ，l “) ，其中1 z k 若存在，q e n d x a u t x ，则因为d ( x ) = 2 ，所以l f - 1 ( 啦) i 2 ，因 此x = q ，= g ，或，( 啦) = ，( 啦+ 2 ) 显然q e n d x = s e n d x 3 ：3n 棱柱的半强自同态 命题3 3 1 设x 为一n - 棱柱，f e n d x 若，保持c j ，饼不变，则， l e n d x 若存在，v e n d x ，则，池) = ，( + 1 ) 或，心) = ，( 一1 ) 若， s e n d x ，贝u f a u t x 证明我们不妨设 ，( 啦) = ，( o ，+ 1 ) = 町，_ 1 ( 即) = 啦，+ 1 ，则，( 啦+ 1 ) = ，( + 2 ) = a 1 + 1或町一1 ，因此，_ 1 ( 口j + 1 ) = 啦+ l ，+ 2 ) 这种情况下显然，q e n d x 若，- 1 ( ) = 兰州大学2 0 0 7 届硕士学位论文 龟，+ ，1 - 1 ( 勺+ 1 ) = 吼+ 1 ，o ：+ + 1 ，且 k 1 ，则( 啦，龟+ 1 ) e ( x ) ，( + ，口，+ + 1 ) e ( x ) ，s - 1 ( q ) 和i - 1 ( a j + 1 ) 中没有其他边显 然，是局部强的若，s e n d x ，则，a u t x 推论”2 设x 是一个n 棱柱。且n 为奇数贝i j 日踟d x ，l e n d x 。 s e n d x 和q e n d x 都是一个幺半群 证明若n 为奇数，则e n d c 。= a u t c n 又由命题3 3 1 可得x 的任一个 自同态都是局部强的，自然就是半强的，所以h e n d x ，l e n d x 是一个幺半 群又因为s 酰d x = a 证x ，所以s e n d x 也是一个幺半群由命题3 3 1 ， 若，g q e n d x ，则乃或者为n 棱柱，或者为c ；，或者为c ：对所有的情况 我们都有，9 q e n d x 定理3 3 3 设x 为一n - 棱柱，n 为偶数，满足，l 矗为c 忭的局部强自 同态，同时把c ：作相应的变换，g 满足g ( a 1 ) = 9 ( + 女) ，1 k n 一1 ，则我 们可以得到l g l e n d x 证明由命题3 2 5 ，毛为g 或嚷不妨设，为g 的局部强自同态则如 果a ，b 玩，且( 口，b ) e ( x ) ，那么对任意的0 ，- 1 ( a ) ，都存在6 ，- 1 ( 6 ) ， 使得( 0 ，6 ，) e ( x ) 又因为对任意的8 ，( ，9 ) _ 1 ( ) ，都存在矿( g ) - 1 ( 6 ) ， 使得( o ，) e ) ，所以，9 是局部强的 定理3 3 4 设x 为一n 棱柱，n 为偶数则h e n d x ，l e n d x 都是一个 幺半群 证明由命题3 2 5 和命题3 。3 1 可以得到，如果，e n d x ，那么， h e n d x 这样h e n d x 是一个幺半群由命题3 3 3 ，l e n d x 也是一个幺半 群 定理3 3 5 设x 为一n 一棱柱，n 为偶数，h e n d x 若存在， q e n d x a u t x ，财亿= 4 ，6 为恒等映射，或6 ( 啦) = 6 ( 毗+ 2 ) ，且把c 盎做对 应的变换在同样条件下，我们有s e n d x = q e n d x 这样q e n d x ，s e n d x 兰州大学2 0 0 7 届硕士学位论文 都是一个幺半群 证明由命题3 2 4 和命题3 3 1 即可得证 1 4 兰州大学2 0 0 7 届硕士学位论文 第4 章分裂图的半强自同态 我们知道图的半强、局部强、拟强自同态一般不形成幺半群， 这些自同态的整体性质就比较弱，严重阻碍了对它们的迸一步研 究。m b o t t c h e r 和u k n a u c r 在【6 】中提出了一个公开问题：图满足什么 条件时，它的半强自同态( 局部强自同态、拟强自同态) 形成么半群? 显然， 对于这个问题，要给出一般性的条件比较困难，或者给出的条件比较“粗 糙”因此解决这一问题的途径应该是对于具体的图类给出具体的答案。 本节我们选取连通分裂图作为研究对象，研究连通分裂图的半强自同态、 局部强自同态和拟强自同态，最后给出连通分裂图的半强自同态( 局部强自 同态) 形成幺半群的条件，在连通分裂图的范围内解决了m b o t t c h c r 和u k n a u e r 提出的公开问题 除非特别说明，本节考虑的图都是有限的、连通的、没有重边和自环的 无向图 设x 是个连通分裂图且v ( x ) = k u s ，其中s = 讥，。， 是x 的 一个独立集，k = z l ， 是x 的一个极大完全集因此对任意 的讥s ，1 i 渤) i n 1 令g s = ( 可) iy 毋分别用h e n d x ， l e n d x 和q e n d x 表示x 的半强自同态。局部强自同态和拟强自同 态的集合设，刀舢对任意y 0 ，令群= l k ，一- 劬( z ) ，彰= n z e ! 一1 ( ) ( $ ) 为了研究连通分裂图的半强白同态，我们首先对一般图给出半强自同态 的一个判定定理 ， 引理4 1 设g 是一个图，e n d g 则，是半强自同态当且仅当对任 意的o 乃，( a ) = n ( a ) n i s 证明必要性：因为，是自同态，所以，( 艇) n ( a ) n 乃我们只需 证明n ( a ) n 乃g ，( 以) 对任意c n ( a ) n 乃，因为，是半强自同态，存 在b ，- 1 ( o ) 和d f - 1 ( c ) 使得( c ，d ) e ( g ) 。因此d n ( b ) 且c = ，( d ) 兰州大学2 0 0 7 届硕士学位论文 所以c ，( a ：) 从而，( 以) = n ( a ) n 乃 充分性：对任意a ，b 0 ，且( a ，b ) e ( g ) ，b ( 0 ) n 0 因此b ，( ) 。 也就是说存在d f - l ( 口) 以及c ( d ) 使得b = ，( c ) 于是存在d f 1 ( 口) ， c s - 1 ( 6 ) 使得( d ，c ) e ( g ) 所以，是半强自同态 引理4 2 设x 是一个连通分裂图，e n d x 则，是半强自同态当且 仅当对任意a s n i s 和任意口k n 乃且f - 1 ( 8 ) c s ，( 趣) = ( o ) n 乃 证明必要性由引理4 1 立即可得 充分性：设a ，b 乃，且( a ，e ( x ) 则b ( 口) n 乃分两种情况讨 论 ( 1 ) 如果o ，b k ，并且存在d f - 1 ( a ) n k ，6 ，( b ) n k 。那么( a t ，6 ，) e ( x ) 不失一般性，可以假设，- 1 ( 8 ) cs 由，( ) = n ( a ) n i ! 得b ，( ) ， 因此存在d s - 1 ( o ) 以及c n ( d ) 使得b = ，( c ) 也就是说存在d s - 1 ( o ) ， c ，一1 ( 6 ) 使得( d ，c ) e ( g ) ( 2 ) 如果a s ，b k ，由于，( a s ) = g ( a ) n 乃，因此b ，( a ) 根据引 理5 1 得证明，存在d f - i ( n ) ，c f - 1 ( 6 ) 使得( d ，c ) e ( x ) 综上所述，是半强自同态 接下来我们寻找使得日e 几d x 成为幺半群的条件 引瑶1 4 3 设x 是一个连通分裂图如果存在i ，j = 1 ，m ，l j 使 得 ) 妄g ( y j ) ，那么h e n d x 不能形成幺半群， 证明假设挑，协s ，弘协使得) c ( 协) ，又设z k 且巩叠 ( ) 令 m ，= 茹和如，= 协茹 则，和g 都是x 的幂等元自同态，因而是半强的显然珊= ( ，9 ) ( 玑) 乃 因为( ，9 ) “( 鲫) = y d 且( f g ) ( y ( y d ) = ( 挑) 妄( 鲫) = ( 协) n 乃，所以 1 6 兰州大学2 0 0 7 届硕士学位论文 根据引理4 2 知向不是半强自同态于是h e n d x 不成为幺半群。 引理4 4设x 是一个连通分裂图，帆是一个反链如果存 在y ，y l ，y t s ，t22 ，且l ( 鼽) l i ( 可) l 使得i ( 可) l = iu i = 1n c y , ) i ， 那么h e n d x 不能形成一个幺半群 证明不失一般性，我们只考虑t = 2 的情况假设a ，b ，c s 使 得l n c a ) ，i ( 6 ) f i i v ( c ) i 和l j v ( a ) u ( 6 ) l = i n ( c ) i 任取k 的自同构h 满 足h ( n ( a ) u ( 砷) = ( c ) 对于任意d s 口，6 ，存在z d k 使 得w d 簪( d ) 令 ， l ( z ) ，2 k ，( z ) ； c ， $ = 口，b ， lh ( x d ) ，口= d s 口，磅 则，是一个同态进一步由引理4 2 知，是半强的令g 是一个满 足g ( a ) = z 。保持其余的点不变的保核收缩则g 是半强自同态 显然c = ( 向) ( 6 ) 并且( s g ) _ 1 ( c ) = h 因为i ( 砷i i ( c ) l ， 所以( ，夕) ( ( 6 ) ) = ( 7 匆) ( ( 6 ) ) = ( ( 6 ) ) 三( c ) = n ( c ) n 巧g 因 此( ，9 ) ( a 9 ) ( c ) n 由引理4 2 得，9 不是半强的，从而h e n d x 不是 幺半群 引理4 5 设x 是一个连通分裂图如果存在y l s ，使得n ( y x ) = k 扛1 ) 且存在a = 玑驰，玑 cs ，t22 ，和z k z l ，使得对任意 的y o a ，瓤簪y ( y o ) ，并且l ( 可) l 一1 = iu 毫2 慨) i ，那么h e n d x 不能 形成一个幺半群 证明任取映射h 满足h ( k 机 ) = k 扛1 ) ，且h ( u t 。：2 ( 玑) ) = 1 7 兰州大学2 0 0 7 届硕士学位论文 联( 彩、 2 1 ) ) 对任意的2 s a u 掣1 ) ，存在如k 满足( 墨k ) 垡e 令 l ( z ) ，z k z k ) ， 他) ： 驰 忙孤 l 骗 扣孙一y t i ， 其他， 则，是一个同态进一步由引理4 2 可知，是半强的令g 是一个满 足g 渤) = 。l 。保持其余的点不变的保核收缩则口是半强自同态显然y 一 ( f g ) ( y 2 ) 0 9 ，并且( ，g ) - 1 ) = 啦，讥) 此时鸽9 = u ：= 2 n 慨) ，而l u l = 2 n ( y d i 2 ，如果l 慨) i 所以，( a ，) = f ( k z k ) = k z = n ( y 1 ) = v ( a ) n 乃 综合( 1 ) ，( 2 ) 由引理4 2 可知，是半强的 定理4 8设x 是一个连通分裂图，s 是一个反链，且对任意 的，可1 ，执s ，t 2 ，如果l ( 执) i i u ( y ) l ，那么i v ( 掣) l i u 名l ) i ，眈扰若存在z k ，( ，y 1 ) e ，( z i ) = y x ，则，h e n d x 当且 仅当 ( a ) 若【卅p ，= n ，则，( ( 口) ) = ( ，( o ) ) n 乃 ( b ) 当p ， 2 时， ( 1 ) 若( a ) k ，( 口】p ，s ，则，( ( o ) ) = ( ，( 口) ) n 乃，且对任意 1 9 兰州大学2 0 0 7 届硕士学位论文 的b h 甜，u ( b ) = ( o ) ( 2 ) 当，( o ) 只【n 】甜s ( i ) 若z l ( ，( 口) ) ，则，( 群( 。) ) = ( ，( o ) ) r ib ( i i ) 若z 1 聋( ，( 口) ) ，则，( ( n ) ) = ( ，( o ) ) n 乃，且对任意的b m p ， ( 6 ) = ( 口) 证明必要性：假设存在善k k 使得( 茁k ，讥) e ，( z k ) 一玑s ， 那么( k 瓢) ) k ，i ( ，0 k ) ) i = n 一1 我们知道，此时k 中只有一个 点与可l 不邻接，我们记其为z 1 若i 【口】p ，l = 1 ，则由引理4 1 得，( ( o ) ) = ( ，( o ) ) n 乃若i a l p ，i 之2 ，设【口】p ，= t o , 1 ，口| ) 因为，是半强的，据引 理4 1 我们有，( ( 口) uu l - l ( 啦) ) = ( ，( n ) ) n 矗下面我们分两种情况进 行讨论： ( 1 ) ，( o ) k ，【0 】p ，冬s ，因为f ( k z ) ) = k 。1 ) ，所以，( o ) = 1 此时对任意的啦【口】 ，巩) 车e 否则，( ，( 啦) ，i ( z k ) ) = ( 茁l ，讥) 隹e ， 与，是一个自同态矛盾又y ( u ( a ) uu 名1 池) ) = n ( z a ) n 乃显然， 等式左边集合的元素个数小于等于n 一1 ，而等式右边集合的元素个数大 于等于佗一1 因此i l ( u ( a ) uu 釜l ) ) l = i n ( z 1 ) n 乃j = 竹一1 又因 为l n ( v 1 ) i = n 一1 ，所以对任意的b 【0 】即u ( b ) = u ( a ) = k z ) ( 2 ) ，( 口) s ，m p ，s 因为，h e n d x ，则由引理4 1 ，( 群( 。) ) = ( ，( n ) ) n 乃成立。如果z 1 ( ，( o ) ) ，则对任意的b 【司即( 6 ，茹k ) 聋e 这样( 1 v ( a ) uu i l ( m ) ) = ( ，( n ) ) 又因为对任意的f ，讥，纨s ， t 2 ，l ( 可) i i u 垒l 慨) i ，所以对任意的b 【口】p ，( = ( 口) 充分性：设，e n d ) ( 满足定理中的条件假设存在k 使 得，( z ) 譬k ，( k 一 z ) ) k ，1 ( ，( z k ) ) i = n 一1 记，( z k ) = 弘 设口sni s 若口= 啦，则对任意b k d p ，且b z k ，x k 聋( b ) 因此n ( b ) u ( z k ) ，从而a s , = u ( z k ) 由( 2 ) 得，( a ，) = ，( ( z k ) ) = ( ，( ) ) n 乃= u ( a ) n0 若口鳜，则，- 1 ( a ) s 任取b - 1 ( o ) 根据( 2 ) ，对任意c y - 1 ( o ) ，u ( c ) = ( 6 ) ，因此= ( 6 ) 2 0 兰州大学2 0 0 7 届硕士学位论文 据( 2 ) 得，( 以) = n ( a ) n 乃设a knl 且f - 1 ( o ) s 则a = z k 任取b ，一1 ( 口) ，据( 1 ) ，对任意c f - 1 ( n ) ，( c ) = ( b ) ，因此a = ( 6 ) 于 是，( 以) = ，( ( 6 ) ) = ( ，( b ) ) n d = n ( a ) n 乃据引理4 2 我们得到，是 半强的。 定理4 9 设x 是一个连通分