一直以来，半群上的同余与同余格是国内外学者密切关注的对象(如文献[1-10]等). 综述文献[6-7]较详尽地给出了20世纪关于半群的同余格的研究成果，并指出了若干相关问题. 文献[1]首次介绍了顶点间最多有1条边的图的图逆半群，并给出了这种图逆半群同余自由的充分条件. 文献[11]证明了：顶点指数最多为1的连通图最多有1个汇点，且若该图不是树，则在圈共轭的意义下只有1个非平凡圈. 文献[9]建立了从图逆半群上的所有同余构成的集合到图的同余三元组构成的集合的一一对应. 文献[3]证明了：图逆半群的同余格是上半模格，但不是下半模格. 文献[4]应用有向图的性质，证明了图逆半群上的0-受限同余所组成的集合关于包含关系形成一个分配格. 在这些基础之上，本文利用文献[3]中的方法证明了：顶点指数最多为1的连通图上的图逆半群的同余格不仅是上半模格，还是下半模格.

有向图Γ=(V，E，r，s)由V，E以及E到V的映射r，s构成. V中的元素为顶点，E中的元素为边. 对于边e，s(e)为e的起点，r(e)为e的终点. 用|X|表示集合X的基数，对任意顶点v，|s^-1(v)|称为v的指数. 以下Γ=(V，E，r，s) 总表示某个有向图，简记为Γ.

由V和E以及集合E^*={e^*：e∈E} 生成的满足以下各条的含零半群称为Γ上的图逆半群，记为Inv(Γ)：对任意u，v∈V，e，f∈E，

(G1) uv=δ_u，vu；

(G2) s(e)e=er(e)=e；

(G3) r(e)e^*=e^*s(e)=e^*；

(G4) f^*e=δ_f，er(e).

在Γ中，路是由边形成的序列α=e₁ e₂ … e_n，其中r(e_i)=s(e_i+1)，i=1，2，…，n-1. 此时s(α)=s(e₁)称为路α的起点，r(α)=s(e_n)称为路α的终点. 记{s(e_i)：i=1，2，…，n}为u(α)，约定顶点v为一条路径，且u(v)=Ø. 若s(α)=r(α)，且当i≠j时有s(e_i)≠s(e_j)，则称α为圈. 我们用Path(Γ) 表示Γ中所有路构成的集合. 对于V₁⊆V，用C(V₁) 表示所有满足u(c)⊆V₁的圈构成的集合.

设H为V的子集，若对任意e∈E，当s(e)∈H时总有r(e)∈H，则称H为V的遗传子集. 令H为遗传子集. 对任意v∈V，称|{e∈E：s(e)=v，r(e)∉H}|为v相对于H的指数. 设W是V的子集，且W中的元素相对于H的指数为1，显然H∩W=Ø. 设f是C(V)到${\mathbb{Z}_ +}$∪{∞}的映射，若对任意c∈C(H)，有f(c)=1，对任意c∉C(H)∪C(W)，有f(c)=∞，则称f为圈映射. 在文献[3]中，V的遗传子集H、相对于H的指数为1的顶点集的子集W，以及圈映射f构成Γ的一个同余三元组，记为(H，W，f). 用$\mathscr{CT}$(Γ) 表示Γ的所有同余三元组构成的集合.

对任意m₁，m₂∈${\mathbb{Z}_ +}$∪{∞}，我们用(m₁，m₂) 表示它们的最大公约数，[m₁，m₂]表示它们的最小公倍数，且设${\mathbb{Z}_ +}$∪{∞}中的任意元素m都整除∞，即(m，∞)=m，[m，∞]=∞.

根据文献[3]，作者证明了图逆半群Inv(Γ)的同余格同构于$\mathscr{CT}$(Γ)关于以下二元关系形成的格：对任意(H₁，W₁，f₁)，(H₂，W₂，f₂)∈$\mathscr{CT}$(Γ)，(H₁，W₁，f₁)≤(H₂，W₂，f₂) 当且仅当H₁⊆H₂，W₁\H₂⊆W₂，且对任意c∈C(V)，f₂(c)|f₁(c).

在格L中，我们用a∧b和a∨b分别表示a和b的上确界和下确界. 若a＞b，且在L中不存在元素x使得a＞x＞b，则称a覆盖b，记为a$\succ$b或b$\prec$a.

对L中任意元素a，b，c，若有(a∨b)∧c=(a∧c)∨(b∧c)，则称L为分配格；

对L中任意元素a，b，c，a≤c，若有(a∨b)∧c=a∨(b∧c)，则称L为模格；

对L中任意元素a，b，若a$\succ$a∧b，b$\succ$a∧b时总有a∨b$\succ$a，a∨b$\succ$b，则称L为上半模格；对L中任意元素a，b，若a∨b$\succ$a，a∨b$\succ$b时总有a$\succ$a∧b，b$\succ$a∧b，则称L为下半模格.

本文引用文献[3] 对$\mathscr{CT}$(Γ)中任意两个元素的上确界和下确界的刻画. 设

是Γ的任意两个同余三元组. 我们用V₀表示(W₁∪W₂)\(H₁∪H₂)中相对于H₁∪H₂的指数为0的顶点形成的集合，X表示集合(W₁∩W₂)\V₀，J表示(W₁∪W₂)\(H₁∪H₂)中存在以其为起点的满足条件u(α)⊆W₁∪W₂且以V₀中某顶点为终点的路径α的顶点形成的集合.

定理1  当图Γ为顶点指数最多为1的连通图时，同余格($\mathscr{CT}$(Γ)，≤)是下半模格.

证  当Γ为顶点指数最多为1的连通图时，由文献[11]的定理3.1知：Γ要么在不计循环置换的意义下只有1个圈，要么最多有1个汇点(V中任意顶点都有路径到该点的顶点即为汇点)；若H为V的非空遗传子集，则H包含Γ的圈或汇点. 我们用e_v表示从顶点v(v∈V)出发的边，由Γ的定义，e_v是唯一的. 则

由于W₁∩W₂中的顶点相对于H₁∪H₂的指数为1，故

对T₁=(H₁，W₁，f₁)∈$\mathscr{CT}$(Γ)，T₂=(H₂，W₂，f₂)∈$\mathscr{CT}$(Γ)，由文献[3]中引理2.7和引理2.8可得T_l=(H_l，W_l，f_l)，其中

对任意c∈C(V)，f_l(c)=[f₁(c)，f₂(c)]. T_u=(H_u，W_u，f_u)，其中

对任意c∈C(V)，f_u=(f₁(c)，f₂(c)). 要证明定理1，即证明若有T_u$\succ$T₁，T_u$\succ$T₂，则有T₁$\succ$T_l，T₂$\succ$T_l.

当H₁=H₂时，据文献[3]的推论2.9可知，结论成立.

当H₁≠H₂时，我们分H₁⊂H₂，H₂⊂H₁和H₁⊈H₂且H₂⊈H₁这3种情形讨论.

情形1  H₁⊂H₂.

此时

H₁可为空集，但H₂不能为空集，则H₂包含Γ的汇点或圈，从而W₂中无圈. 由圈映射的定义，对任意c∈C(V)，f₂(c) 取值为1，故

情形1.1  当J=Ø时，即H_u=H₂.

由T_u$\succ$T₁，T_u$\succ$T₂以及文献[3]的引理2.1和引理2.3知，W₁\H₂=W_u，W₂⊆W_u且|W_u\W₂|=1. 故有W₂⊂W_u⊆W₁，从而

因为

所以由文献[3]的引理2.3，结论成立. 下证T₂$\succ$T_l.

对任意T′=(H′，W′，f′)∈$\mathscr{CT}$(Γ)，若有

则

若H₂=H′，则W′⊆W₂，且由(1)式可得

所以W′=W₂，进而f′=f₂，与假设矛盾，所以H₂≠H′.

由(1)式可知

所以(W₁∩H₂)\H′中的顶点相对于H′的指数为1. 又由W_u=W₁\H₂知，W₁\H₂中顶点相对于H₂的指数为1，从而相对于H′的指数也为1 (V中任意顶点的指数最多为1)，故(H′，W₁\H′，f₂)∈$\mathscr{CT}$(Γ). 所以有

由T_u$\succ$T₁知H′=H₁.

但若H₁=H′，由T_u$\succ$T₁和文献[3]的引理2.1知，当c∈C[(W₁∩H₂)∪W₂]时，有

且在H₂\[H₁∪(W₁∩H₂)∪W₂]=H₂\(H₁∪W₁)中没有顶点相对于H₁的指数为1. 又由于

故由文献[3]的引理2.5得

即T′=T_l. 从而有T₂$\succ$T_l.

情形1.2  当J≠Ø时，即H_u=H₂∪J.

此时H₁⊂H_u，H₂⊂H_u. 由T_u$\succ$T₁和文献[3]的引理2.1知

所以W₂\W₁⊆J. 但在(H₂∪J)(H₁∪W₁)中顶点相对于H₁的指数为0，所以W₂\W₁中顶点相对于H₁的指数为0，从而相对于H₂的指数为0，由同余三元组的定义W₂\W₁=Ø，即有W₂⊆W₁. 类似地，由T_u$\succ$T₂和文献[3]的引理2.1知

所以有

因为(H₂∪J)\(H₂∪W₂)中顶点相对于H₂的指数为0，所以

因此W₂≠W₁，否则V₀=Ø，J=Ø，与假设矛盾. 所以

下证|V₀|=1. 若|V₀|＞1，对任意v₁∈V₀，令

由J₁的定义不难看出H₂∪J₁是遗传子集. 若W₂\J₁中存在顶点v相对于H₂∪J₁的指数为0，因为Γ是连通图，所以存在一条边以v为起点，终点在J₁中，因此有v∈J₁，矛盾. 故W₂\J₁中的顶点相对于H₂∪J₁的指数为1，因此(H₂∪J₁，W₂\J₁，f₂)∈$\mathscr{CT}$(Γ). 所以有

与T_u$\succ$T₂矛盾，所以

由于

据文献[3]的引理2.3，有

即有T₁$\succ$T_l. 下证T₂$\succ$T_l.

对任意T′=(H′，W′，f′)∈$\mathscr{CT}$(Γ)，若有

则有

若H′=H₂，则由(2)式可得

所以W′=W₂，进而f′=f₂，与假设矛盾. 所以H₂≠H′. 故

若以V₀中的唯一的顶点为起点的边的终点在H′中，则H′∪J是遗传子集. 由(2)式可得

因此W₁\H′中的顶点相对于H′的指数为1. 又因(W₁∩H₂)\H′⊆H₂，且H₂为遗传子集，所以(W₁∩H₂)H′中的顶点相对于H′∪J的指数为1. 因为

故W_u中的顶点相对于H′∪J的指数也为1. 从而得到

且有

这与T_u$\succ$T₁矛盾，所以以V₀中的唯一的顶点为起点的边的终点在H₂\H′中. 于是(H′，W₁\H′，f₁)∈$\mathscr{CT}$(Γ)，且有

再由T_u$\succ$T₁知H′⊆H₁.

由(2)式和文献[3]的引理2.5知[(W₁∩H₂)∪W₂]=W′，进而f′=f₂. T₂$\succ$T_l得证.

情形2  H₂⊂H₁.

与情形1的证明类似.

情形3  H₁⊈H₂且H₂⊈H₁.

此时H₁≠Ø，H₂≠Ø，故若Γ中有圈，则圈在H₁∩H₂中，所以W₁和W₂中均无圈. 从而可设f_u=f₁=f₂=f_l=f. 由T_u$\succ$T₁，T_u$\succ$T₂以及文献[3]的引理2.1可得

下证V₀=Ø. 否则，不妨设W₂(H₁∪W₁)≠Ø. 令

J₂={v∈J：存在α∈Path(Γ)，使得s(α)=v，u(α)⊆W₁∪W₂，r(α)∈W₂(H₁∪W₁)}

则J₂≠Ø. 由T_u$\succ$T₁和文献[3]的引理2.1知，W₂\(H₁∪W₁)中的顶点相对于H₁的指数为0，所以H₁∪J₂为遗传子集. 类似于情形1.2的证明，W₁\J₂中的顶点相对于H₁∪J₂的指数为1，所以(H₁∪J₂，W₁\J₂，f)∈$\mathscr{CT}$(Γ). 因此

这与T_u$\succ$T₁矛盾，故V₀=Ø.

由V₀=Ø及J的定义可得J=Ø，所以

下证T₁$\succ$T_l. 对任意T′=(H′，W′，f′)∈$\mathscr{CT}$(Γ)，若有

则有H₁∩H₂⊆H′⊆H₁. 若H′=H₁，由(3)式可得

所以W′=W₁. 进而f′=f，与假设矛盾，所以H′≠H₁. 故H₁∩H₂⊆H′⊂H₁，进而有

由(3)式可知(W₁∪W₂)\H′⊆W′，所以W₂H′⊆W′，这说明在W₂\H′中的顶点相对于H′的指数为1. 又因为H′∪H₂是遗传子集. 所以(H′∪H₂，W₂H′，f)∈$\mathscr{CT}$(Γ). 由

得H₂=H′∪H₂，即H′⊆H₂. 又由H′⊆H₁，所以H′⊆H₁∩H₂. 故H′=H₁∩H₂. 与情形1.1的证明类似，由文献[3]的引理2.5得

即T′=T_l，T₁$\succ$T_l得证. 同理可证T₂$\succ$T_l.