1. 引言
作为图的最重要的半群之一,图的自同态幺半群尤其受到研究人员和学者的重视,投入了大量的精力去研究。从 [1] - [16] 可知,对其研究的目的是建立半群代数理论和图论之间的联系,尤其是利用图的自同态幺半群的代数性质研究图的组合性质并对图进行分类。
我们知道,在半群理论中,正则元素的逆是非常重要的,尤其受到学者的重视。文献 [17] 探讨了图的正则自同态的逆。 [16] 给出了图的强自同态的各种各样的逆。 [1] 证明了路的补图是纯整的。因此路的补图上的自同态都存在弱逆。
在本篇文章中,我们将路的补图的自同态分为四类,详细刻画了各类自同态的弱逆,并且这些弱逆的个数也得到了。
本文只讨论有限的无向的没有环和重边的图。设G是一个图。图G的点集合(边集合)定义为。设
。如果
和
是相邻的,则写作
。对于图H,如果
并且
,那么H叫做图G的一个子图。进而,H称为G的一个诱导子图,如果对任意的
,
的充要条件是
。
设f是从
到
的映射。对于任意的
,如果由
可以得出
,那么f称为从G到H的自同态。我们把自同态f称为从G到H的同构,如果f是双射且
也是自同态。我们用
表示图G上的所有自同态组成的集合。设
,
,
。
我们定义
,
。图K称为完全图,如果任意的
,都有
。用
定义有且只有n个点的完全图。用
定义有且只有n个点的路。我们称
为图G的补图,如果
,并且对于任意的
,
的充要条件是
。
用
定义自同态f的自同态像。
上的由f诱导的等价关系
定义为:对于
,
的充要条件是
。设S是一个半群。对于
,如果存在元素
使得
,那么称a是正则的,元素x称为元素a的一个弱逆。如果半群S中的所有元素都是正则的,那么S称为是正则的。设
。用
表示f的所有弱逆组成的集合,即
。可知路的补图的
是非空的。
我们用数字
对补图
的点以逆时针的方式编号,见图1。可知,对于任意的
,
的充要条件是
。
Figure 1. Graph
and
图1. 图
和
对于本文没有列出的概念和术语,请读者参阅文献 [10] [13] [14]。下面的结论将在本文中使用。
设
。
引理1.1 ( [1])
。那么
1)
是非空的,并且形成
的一个区间。在这种情况下,在
中出现的偶数是
中连续的偶数。
2) 设i(j)是
中的最小值(最大值)。那么i和j是奇数。在这种情况下,在
上由
诱导的分划是
。
3) 设
(
)是
上的最小值(最大值)。那么
和
都是奇数。在这种情况下,
。
引理1.2 ( [1]) 1)
。
阶数为m的团的形式为
,其中
(
表示团为
,
表示团为
)。
2) 在
中的任何两个相邻点不可能同时都与K中的
个点相邻,K是
上的任意的阶数为m的团。
引理1.3 ( [1]) 设
。
1) 如果
是非空的,i(j)是
中的最小值(最大值)。那么i是奇数,j是偶数。如果是这种情况,在
上由
诱导的分划是
。
2) 设
(
)是
上的最小值(最大值)。那么
是奇数,
是偶数。进而,
。
3)如果
是空集,那么在
上由
诱导的分划是
,并且
是阶数为m的团。
2. 主要结论
对于
,当
时,根据引理1.1,当
时,此时
(
类似)。可知存在正整数
和
使得:
,
,
,
,然而
;
,
,
,
,但是
。则有以下结论:
定理2.1. 设
,并且
。那么
1)
的充要条件是
这里s分别取值
,t分别取值
。
2)
。
证明:充分性。经验证可得
,并且对于任意的
,都有
。
必要性。设
。可知g是补图
上的自同态,并且对于任意的
,都有
。由
的定义可知,对于任意的
,存在
使得
。由引理1.1,可知f在
上的限制是从
到
的同构。因此,对于任意的
,都有
。又,当
时,
。从而可得,对于任意的
,都有
。
如果
,那么由引理1.1,可得
。又,对于任意的
,都有
。所以,对于任意的
,都有
。因为
,可得
。
又由补图
的定义可知,
,从而
,并且x与
中的每一点都是相邻的。所以,由自同态的定义可以知道,
或者
。
讨论
。可知
,
。已知
,因此
。如果
,那么
,矛盾。所以,
。从而,
。如果
,那么由引理1.1可得,
,
,
。
如果
,即
。在这种情况下,可得
。
同理可知,
。如果
,可得
,
,
。如果
,可得
。因此,
……依次按上述方法讨论。当
时,可得
。如果
时,可得
,即
,矛盾。所以,
,进而
,
,
。
同理,我们可以证明
。如果
,那么
,
,
。如果
,则
。从而
。……依次下去,当
,则有
。如果
,则
。即
,矛盾。所以
,
,
,
。
综上,
的形式为
,
可知
共有
种,因此
。证毕。
定理2.2. 设
并且
。那么
1)
的充要条件是
s取值
;t取值
。或者
其中r取值
,
取值
。或者
这里
取值
;
取值
。
2)
。
证明:充分性。验证可知
,并且对于任意的
都有
。
必要性。设
。又
,所以对任意的
,存在
使得
,即
。又
,所以对于任意的
,都有
。
又
。设
,可得
。进而
。而
。因为
,可得
。又
。由补图
的定义可知,x与
中的每一点都是相邻的。因为
是
上的自同态,所以
与
中的每一点都是相邻的。因此,
或者
。
当
时,存在正整数
和
使得
,
是连续奇数,但是
和
不是连续奇数,
和
也不是连续奇数。
如果
时,可知
,
,
,
。存在正整数
使得
是连续奇数,但是
不是连续奇数。同理,当
时,……依次下去,当
时,
。
如果
,存在正整数
使得
是连
续奇数,但是
,不是连续奇数。同理,依次下去。……当
时,
。
综上所述,与定理1的证明类似,我们可以得出自同态f的弱拟g。并且
。
证毕。
设
,
,
,
。不妨设
(
类似)。设
。
则存在正整数
和
使得
,
,
,
;
,
,
,
。
定理2.3. 设
。则
1)
的充要条件是
s取值
,t取值
。
2)
。
证明:充分性。验证可知
,并且对于任意的
,
。
必要性。设
。则
,且对于任意的
,都有
。由定理1.3可知,对于
,
。又,对于
,
。由引理1.3可知,
。因此
。如果
,那么
或者
不是团,矛盾。所以,对于任意的
,
。
又
。对任意
可知
,所以
或者
。
当
,可知
。由补图
的定义可知,
,因此
。如果
,那么
,矛盾。所以,
,即
。
如果
,那么
,
,
。如果
,那么由引理1.3,可得
,从而
。同理,依次下去……如果
,那么
。如果
,可知
。即
,矛盾。所以,
。进而,
,
,
。
同理,可知
。如果
,那么
,
,
。如果
,那么
。进而
。同理,依次下去……如果
,那么
。如果
,那么
。即
,矛盾。所以,
。进而,
,
,
。即得结论(1)。
综上,可得
。因此,
,即结论(2)。证毕。
定义
。
定理 2.4. 设
,
是空集。那么
1)
的充要条件是
。或者
s分别取值
,t分别取值
。
,
,
。或者
这里r取值
,s取值
。
,
,
。或者
这里
,
,
,
。
2)
。
证明:充分性。验证可得
。
必要性。设
,则
。可知,对于任意的
,有
。而
(引理1.2)。如果
,可知
,那么
,x与
中的每一点都是相邻的。而2k与
中的每一点都是相邻的,
与
中的每一点都是相邻的。由自同态的定义,可知
或者
,
,
。从而可得,
或者
,
,
。
如果
是空集,由定理1.3,可得
,
,
,
,
,
。可知
是一个阶数为m团,
。因此,
,
,
,
,
。
如果
是非空的,且
,由引理1.3,可知
,
,
。则存在正整数
使得
,
,
,
,
是连续数字,但是
,
,
,
(不计次序)不是连续的;
,
,
,
,
是连续的,但是
,
,
,
(不计次序)不是连续的。设
。
如果
,可知
。则存在正整数
使得
,
,
,
,
是连续的,但是
,
,
,
(不计次序)不是连续。设
,
。如果
,同理,依次下去……如果
,可得
。
同理,如果
,那么
。则存在正整数
使得
,
,
,
,
是连续的,但是
,
,
,
(不计次序)不是连续的。设
,
。依次下去……,直至
。
综上,根据定理3,可得出结论(1) (2)。证毕。
致谢
本人非常感谢所有提供帮助的老师和同学。