自同態(tài)生物力量的元循環(huán)圖

自同態(tài)生物力量的元循環(huán)圖

最終半正圖是原始半組圖的圖。同一圖的等效截面。這是一個(gè)完整的自然生態(tài)圖像的子圖。它們都是收縮圖的收縮核。這與自然生態(tài)圖像的原始圖像具有相同的結(jié)構(gòu)。在和中，通過圖積算法獲得了更廣泛的最終結(jié)果。李于民還提供了一個(gè)家庭的自然生態(tài)橫截面，即黃色cn（n.3）cn（n.3）。事實(shí)上，左圖（n.3）cs，左圖（n.3）是末端的正式循環(huán)圖。在這項(xiàng)工作中，我們研究了小型末端的后半部分。本文只討論有限簡單圖.記X=(V(X),E(X))為具有頂點(diǎn)集V(X),邊集E(X)的圖.若頂點(diǎn)x1與x2在X中相鄰,則記為{x1,x2}∈E(X).稱映射f∶V(X)→V(Y)為圖X到圖Y的同態(tài),如果f保持頂點(diǎn)的相鄰關(guān)系,即對任意x1,x2∈V(X),{x1,x2}∈E(X)蘊(yùn)含{f(x1),f(x2)}∈E(Y).若f是雙射,并且f-1也是從Y到X的同態(tài),則稱f是X到Y(jié)的同構(gòu).當(dāng)X=Y時(shí),上面定義的映射分別稱為自同態(tài)與自同構(gòu).X的所有自同態(tài)的集合記為EndX,它在通常的映射合成下構(gòu)成一個(gè)幺半群,稱為圖X的自同態(tài)幺半群.類似地定義圖X的自同構(gòu)群AutX.顯然AutX?EndX.若AutX=EndX,則稱X為E-A不可收縮圖.設(shè)f∈EndX,分別記ran(f),R(f)為f的像集及由此像集ran(f)導(dǎo)出的X的子圖.稱R(f)為圖X在f下的自同態(tài)像子圖.f|V′表示映射f在V的子集V′上的限制.若對所有v∈ran(f),f(v)=v,則稱自同態(tài)f為收縮映射,稱相應(yīng)的自同態(tài)像子圖R(f)為X的收縮核.設(shè)S是一個(gè)幺半群,a∈S,稱a為S的正則元如果存在b∈S使得aba=a.若S中所有元素都是正則元,則稱S是正則幺半群.若圖X的自同態(tài)幺半群EndX是正則幺半群,則稱圖X是End-正則圖,其它概念和術(shù)語可參見文獻(xiàn).引理1設(shè)X是圖,f∈EndX,則下列條件等價(jià):(i)f是正則元;(ii)R(f)是X的收縮核,并且存在X的收縮核A,使得f|V(A)是從A到R(f)的同構(gòu);(iii)R(f)是X的收縮核,并且存在X的導(dǎo)出子圖A,使得f|V(A)是從A到R(f)的同構(gòu).引理2設(shè)X是二分圖,則X是End-正則圖當(dāng)且僅當(dāng)X是下列圖之一:(i)完全二分圖Kn,m(n,m≥1);(ii)雙星圖T(r,s)(r,s≥1);(iii)6長圈C6;(iv)4長路P4或8長圈C8;(v)不連通圖nK1,(n-1)K1∪K2或nK2(n≥2).若圖有n個(gè)連通分支,并且每個(gè)連通分支都同構(gòu)于X,則記此圖為nX.若對任意f,g∈EndX,有ran(f)?ran(g)或者ran(g)?ran(f),則稱X為階梯圖.顯然,E-A不可收縮圖是階梯圖,偶圈不是階梯圖.引理3nX是End-正則圖當(dāng)且僅當(dāng)X是End-正則的階梯圖.記循環(huán)圖G為Cn〈j1,j2,…,jr〉,其中1≤j1<j2<?≤jr=[n/2]([n]1≤j1<j2<?≤jr=[n/2]([n]表示不大于n的最大正整數(shù)),頂點(diǎn)集為V(G)={0,1,…,n-1},邊集為E(G)={{i,j}||j-i|≡jk(modn),k=1,2,…,r}.循環(huán)圖G=Cn〈j1,j2,…,jr〉有m=gcd(n,j1,j2,…,jr)個(gè)連通分支,每個(gè)連通分支的度數(shù)都與G的度數(shù)相同并且都同構(gòu)于Cn/m〈j1/m,j2/m,…,jr/m〉.若G=Cn〈j1,j2,…,jr〉(jr≠n/2)是偶數(shù)度循環(huán)圖,則G是由一些回路構(gòu)成的,這些回路分成r組,每組是由Cn〈ji〉(i=1,2,…,r)構(gòu)成的mi=gcd(n,ji)條長為nminmi的邊不相交的回路組成.若G=Cn〈j1,j2,…,jr〉(jr=n/2)是奇數(shù)度循環(huán)圖,則G由兩部分構(gòu)成:一部分由r-1組回路構(gòu)成,每組回路是由Cn〈ji〉(i=1,2,…,r-1)構(gòu)成的mi=gcd(n,ji)條長為nminmi的邊不相交的回路組成;另一部分由n/2條邊{0,n/2},{1,1+n/2},{2,2+n/2},?,{n/2-1,n-1}{0,n/2},{1,1+n/2},{2,2+n/2},?,{n/2?1,n?1}構(gòu)成.根據(jù)循環(huán)圖的結(jié)構(gòu),1度循環(huán)圖即為Cn(j)(j=n/2).而Cn(j)?jK2,由引理2,即得下面定理.定理4Cn(j)(j=n/2)是End-正則圖.關(guān)于2度循環(huán)圖,有下面結(jié)果.定理5設(shè)X=Cn(j)(j≠n/2),m=gcd(n,j),則X是End-正則圖當(dāng)且僅當(dāng)n/m為奇數(shù)或者n=4,6,8而且m=1.證把m分成兩種情形進(jìn)行討論:情形1當(dāng)m=1時(shí),X只有一個(gè)連通分支并且每個(gè)頂點(diǎn)的度數(shù)為2,所以X是圈Cn.(i)若n為奇數(shù),因?yàn)閷θ我鈌∈EndX,f只能把極小奇圈Cn映到極小奇圈Cn,所以f是滿射,必為自同構(gòu).此時(shí),EndX=AutX,f是正則元,因此X=Cn是End-正則圖.(ii)若n為偶數(shù)時(shí),偶圈Cn是二分圖.由引理2得X=Cn是End-正則圖當(dāng)且僅當(dāng)n等于4,6或8.由(i),(ii),當(dāng)m=1時(shí),Cn(j)(j≠n/2)是End-正則圖當(dāng)且僅當(dāng)n為奇數(shù)或?yàn)?,6,8.情形2當(dāng)m>1時(shí),由循環(huán)圖的結(jié)構(gòu)可知X由m個(gè)連通分支組成,每個(gè)連通分支為Cn/m.(i)′若n/m為奇數(shù),與情形1中(i)的證明類似,可知EndCn/m=AutCn/m.因此Cn/m是End-正則的階梯圖.又由引理3得X=mCn/m是End-正則圖.(ii)′若n/m為偶數(shù),與情形1中(ii)的證明類似,可知Cn/m是End-正則圖當(dāng)且僅當(dāng)n/m等于4,6或8.但當(dāng)n/m等于4,6或8時(shí),Cn/m是偶圈,不是階梯圈.由引理3得X=mCn/m不是End-正則圖.由(i)′,(ii)′,可知當(dāng)m>1時(shí),Cn(j)(j≠n/2)是End-正則圖當(dāng)且僅當(dāng)n/m為奇數(shù).綜合情形1,情形2,可知X=Cn(j)(j≠n/2)是End-正則圖當(dāng)且僅當(dāng)n/m為奇數(shù)或者n=4,6,8而且m=1.因?yàn)間cd(n,j,n/2)=gcd(j,gcd(n,n/2))=gcd(j,n/2),所以由循環(huán)圖的結(jié)構(gòu)可知3度循環(huán)圖Cn〈j,n/2〉由m=gcd(j,n/2)個(gè)有n/m個(gè)頂點(diǎn)的互相同構(gòu)的連通分支構(gòu)成,而且每個(gè)連通分支都是3度連通循環(huán)圖.又因?yàn)間cd(j,n/2)=m,所以gcd(n,j)=m或2m.先討論3度連通循環(huán)圖.引理6設(shè)Cn〈i,n/2〉與Cn〈j,n/2〉都是3度連通循環(huán)圖.若gcd(n,i)=gcd(n,j)=1,則Cn〈i,n/2〉與Cn〈j,n/2〉都與Cn〈1,n/2〉同構(gòu);若gcd(n,i)=gcd(n,j)=2,則Cn〈i,n/2〉與Cn〈j,n/2〉都與Cn〈2,n/2〉同構(gòu).由引理6可知所有3度連通循環(huán)圖Cn〈i,n/2〉只分為兩類:Cn〈1,n/2〉與Cn〈2,n/2〉.命題7設(shè)Cn〈1,n/2〉是連通圖,則它是End-正則圖當(dāng)且僅當(dāng)n≡0(mod4)或者n=6.證因?yàn)閚為偶數(shù),所以n/2或者為偶數(shù),或者為奇數(shù).可把Cn〈1,n/2〉分為兩類:C4k〈1,2k〉與C4k+2〈1,2k+1〉.(i)如果n/2為偶數(shù),那么設(shè)n/2=2k(k≥1).對任意f∈EndC4k〈1,2k〉,f是單射.事實(shí)上,因?yàn)镃4k〈1,2k〉中任意兩個(gè)頂點(diǎn)都在一個(gè)極小2k+1長奇圈上.如果f不是單射,那么f把此奇圈映到一個(gè)比它更小的奇圈,矛盾.所以,EndC4k〈1,2k〉=AutC4k〈1,2k〉,進(jìn)一步得C4k〈1,2k〉是End-正則圖.(ii)如果n/2為奇數(shù),那么設(shè)n/2=2k+1(k≥0).將C4k+2〈1,2k+1〉中頂點(diǎn)標(biāo)號按奇偶分劃,易見它為二分圖.由引理2,可知C4k+2〈1,2k+1〉是End-正則圖當(dāng)且僅當(dāng)它是C6〈1,3〉,即圖K3,3.綜合(i),(ii),可知當(dāng)n≡0(mod4)或者n=6時(shí),Cn〈1,n/2〉是End-正則圖.充分性得證.又由(ii)可知當(dāng)n≠0(mod4)時(shí),n/2為奇數(shù),如果n≠6,那么Cn〈1,n/2〉不是End-正則圖.必要性得證.記G□H為圖G與H的卡氏積,它的頂點(diǎn)集V(G□H)=V(G)×V(H),邊集為E(G□H)={{(u,x),(v,y)}∶u=v且{x,y)∈E(H)或者{u,v}∈E(G)且x=y}.引理8若循環(huán)圖Cn〈j1,j2,jr,n/2〉是連通的,且gcd(n,j1,j2,…,jr)=2,則Cn?j1,j2,?,jr,n/2??Cn/2?j12,j22,?,jr2?□Κ2命題9若Cn〈2,n/2〉是連通圖,則它是End-正則圖,且不是階梯圖.證先證明n/2為奇數(shù).否則,如果n/2為偶數(shù),那么gcd(2,n/2)=2≠1.即Cn〈2,n/2〉有2個(gè)連通分支,矛盾.所以n/2為奇數(shù).由引理8可知Cn〈2,n/2〉?Cn/2□K2,因此Cn/2是Cn〈2,n/2〉的極小奇圈.設(shè)Cn/2的頂點(diǎn)為0,1,…,n/2-1,K2的頂點(diǎn)為0,1.按卡氏積的定義對Cn〈2,n/2〉進(jìn)行標(biāo)號.可以構(gòu)造映射α如下:α((i,1))=(i,1),α((i,0))=(i+1,1)(i∈{0,1,…,n/2}且運(yùn)算取模n/2).設(shè)G=R(α),G′=(Cn/2□K2)-G.則G為由邊{(0,1),(1,1)},{(1,1),(2,1)},…,{(n/2-1,1),(0,1)}組成的圈Cn/2,它是Cn〈2,n/2〉的收縮核.而G′為由邊{(0,0),(1,0)},{(1,0),(2,0)},…,{(n/2-1,0),(0,0)}組成的圈Cn/2.同理可構(gòu)造映射β使R(β)=G′.而G與G′之間沒有包含關(guān)系,故Cn〈2,n/2〉不是階梯圖.因?yàn)閷θ我鈌∈EndCn〈2,n/2〉,f只能把極小奇圈Cn/2映到極小奇圈Cn/2,所以R(f)=Cn〈2,n/2〉?Cn/2□K2或者R(f)=Cn/2.(i)如果R(f)=Cn〈2,n/2〉,那么f是滿射,所以是自同構(gòu).因此f是正則元.(ii)如果R(f)=Cn/2,則R(f)是Cn〈2,n/2〉的收縮核,并且存在Cn〈2,n/2〉的收縮核A=(Cn/2□K2)-R(f),使得f|A是A到R(f)上的同構(gòu).根據(jù)引理2得f是正則元.綜上所述,Cn〈2,n/2〉是End-正則圖.命題10設(shè)Cn〈j,n/2〉是不連通圖,m=gcd(j,n/2)>1,則Cn〈j,n/2〉是End-正則圖當(dāng)且僅當(dāng)gcd(n,j)=m并且n/2m為偶數(shù).證如果m=gcd(j,n/2),那gcd(n,j)=m或2m.如果gcd(n,j)=m,那么gcd(n/m,j/m)=1.由引理6得每個(gè)連通分支同構(gòu)于Cn/m〈1,n/2m〉.又由命題7得Cn/m〈1,n/2m〉是End-正則圖當(dāng)且僅當(dāng)n/m≡0(mod4)或n/m=6.當(dāng)n/m≡0(mod4),即n/2m為偶數(shù)時(shí),由命題7(i)的證明過程,可知EndCn/m〈1,n/2m〉=AutCn/m(1,n/2m).又由引理3得mCn/m〈1,n/2m〉是End-正則圖.當(dāng)n/m=6時(shí),C〈1,3〉不是階梯圖,根據(jù)引理3可知mCn/m〈1,n/2m〉不是End-正則圖.如果gcd(n,j)=2m,那么gcd(n/m,j/m)=2.由引理6得每個(gè)連通分支同構(gòu)于Cn/m〈2,n/2m〉.由命題6得Cn/m〈2,n/2m〉不是階梯圖