圖的兩類運(yùn)算性質(zhì)

張倩男，陳金陽

(湖北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖北 黃石 435002)

圖的兩類運(yùn)算性質(zhì)

張倩男，陳金陽

(湖北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖北 黃石 435002)

在圖論研究中，圖的運(yùn)算是構(gòu)造具有特殊性質(zhì)的圖的一種方法．文本對圖G的兩類運(yùn)算從結(jié)構(gòu)、運(yùn)算規(guī)律、性質(zhì)等方面進(jìn)行研究，進(jìn)而將其作用在完全圖Kn上，構(gòu)造出與剩余類加群同構(gòu)的有限群。

完全圖；模n剩余類群；同構(gòu)

1 問題背景

在圖論研究中，圖的運(yùn)算是構(gòu)造具有特殊性質(zhì)圖的一種方法，這種運(yùn)算作用在特殊圖上有可能構(gòu)成代數(shù)系統(tǒng)，乃至構(gòu)成群．在代數(shù)研究中，群論占有重要地位，用群理論構(gòu)造特殊性質(zhì)的圖也是圖論研究的一個重要方法，如Cayley圖，Bi-Cayley圖都是通過群構(gòu)造的，它們均具有較好的圖論性質(zhì)，如正則性，連通性，哈密爾頓性等．有關(guān)這方面理論研究參看文獻(xiàn)[1～3]．

本文首先研究了圖的兩種特殊運(yùn)算G1*G2和G1×G2的運(yùn)算性質(zhì)，進(jìn)而將其作用在完全圖Kn上，構(gòu)造出與剩余類加群同構(gòu)的有限群．

2 基本概念及術(shù)語

定義1 “*”運(yùn)算：令H1=G1*G2，則

1)V(H1)=V(G1)∪V(G2)；

注：“*”運(yùn)算可以提高圖的連通性，設(shè)|V(G1)|=n1，|V(G2)|=n2則：

?vi∈V(G1),dH1(vi)=dG1(vi)+n2?vj∈V(G2),dH1(vj)=dG2(vj)+n1

每個頂點(diǎn)的度都增大了，進(jìn)而提高了圖的連通性．

定義2 “*”運(yùn)算： 令H2=G1×G2，則

2) 任意兩點(diǎn)(x1,y1),(x2,y2)∈V(H2)在H2中鄰接當(dāng)且僅當(dāng)以下條件之一成立：

Ⅰ)x1=x2且y1～y2inG2；

Ⅱ)y1=y2且x1～x2inG1．

定義3 圖同構(gòu)： 對圖G1,G2，若存在一個雙射φ∶V(G1)→V(G2)， 使

xy∈E(G1) ?φ(x)φ(y)∈E(G2)

稱G1與G2同構(gòu)，記作G1?G2．

3 兩種運(yùn)算的一般性質(zhì)

定理1 “*”運(yùn)算滿足下面兩條性質(zhì)：

1) 結(jié)合律：(G1*G2)*G3=G1*(G2*G3)；

2) 交換律：G1*G2=G2*G1.

證明： 1)由定義知，

V((G1*G2)*G3)=V(G1*G2)∪V(G3)=(V(G1)∪V(G2))∪V(G3)=

V(G1)∪(V(G2)∪V(G3))=V(G1)∪V(G2*G3)=

V(G1*(G2*G3))

令G1*G2=H1，則E(H1)=E(G1*G2)=E(G1)∪E(G2)∪E12，故有：

所以E(G1*(G2*G3))=E(G1)∪E(G2)∪E(G3)∪E12∪E13∪E23．

令G2*G3=H2，則E(H2)=E(G2*G3)=E(G2)UE(G3)∪E23，所以

故結(jié)合律成立，即

(G1*G2)*G3=G1*(G2*G3)

2) 由定義知V(G1*G2)=V(G1)∪V(G2)=V(G2)∪V(G1)=V(G2*G1)

E(G1*G2)=E(G1)∪E(G2)∪E12E(G2*G1)=E(G2)∪E(G1)∪E21

而E12=E21，故E(G1*G2)=E(G2*G1)，G1*G2=G2*G1．

圖1 K3*K2=K5

圖2 K2×K2=C4

定理2 “*”運(yùn)算在同構(gòu)意義下滿足以上兩條性質(zhì)：

1) 結(jié)合律：(G1×G2)×G3=G1×(G2×G3);

2) 交換律：G1×G2=G2×G1．

所以在圖G中，存在一個映射φ，

使φ((x1,y1),zi)=(x1,(y1,z1)),φ((x2,y2),z2)=(x2,(y2,x2))．所以

(G1×G2)×G3?G1×(G2×G3),所以結(jié)合律成立，即(G1×G2)×G3=G1×(G2×G3)．

2) 和上面證結(jié)合律的方法類似，在圖G中，存在一個映射φ，

使φ(x1,y1)=(y1,x1)),φ(x2,y2)=(y2,x2).

? (y1,x1)～(y2,x2)inG2×G1.

所以G1×G2?G2×G1，所以交換律成立，即G1×G2=G2×G1．

注：兩種運(yùn)算都不滿足分配律．

令G1=G2=K1，G3=K2,則

4 “*”運(yùn)算作用在完全圖Kn上的性質(zhì)

由運(yùn)算的定義知：

性質(zhì)1K0*Kn=Kn．(其中K0=?表示空圖)

性質(zhì)2Kn1*Kn2=Kn1+n2.

定理3 (K,*)構(gòu)成代數(shù)系統(tǒng)．

證明 由性質(zhì)2知，對?Kn1,Kn2∈K,有Kn1*Kn2=Kn1+n2∈K，所以運(yùn)算封閉構(gòu)成代數(shù)系統(tǒng)．

定理4 (K,*)構(gòu)成交換半群．

證明 由定理1知，“*”運(yùn)算滿足結(jié)合律和交換律，所以構(gòu)成交換半群．

定理5 (K,*)構(gòu)成交換幺半群．

證明 由性質(zhì)1知，K0*Kn=Kn，所以K0是單位元，所以構(gòu)成交換幺半群．

但是在(K,*)中，任一元素(除K0外)無逆元，所以(K,*)構(gòu)不成群，下面我們設(shè)

注：運(yùn)算的實(shí)際意義：

1)當(dāng)n1+n2

2)當(dāng)n1+n2≥n時，Kn1*Kn2=Kn1+n2-Kn∈K[n]，即Kn在Kn1+n2中的補(bǔ)圖．

定理6 (K[n],*)構(gòu)成交換群且與(Zn,+)同構(gòu)．

證明 1)由重新定義知，運(yùn)算封閉．

2)由定理1知，結(jié)合律和交換律成立．

3)由性質(zhì)1知，對?Ki∈Kn，有K0*Ki=Ki，所以K0為單位元．

4)對?Km∈K[n]有逆元，(Km)-1=Kn-m．

所以(Kn,*)構(gòu)成一個交換群．

存在一個映射φ：K[n]→Zm

Ki→φ(Ki)

使得φ(Ki*Kj)=φ(Ki)+φ(Kj)=(i+j)mod(n)．

故：(K[n],*)與(Zn,+)同構(gòu)．

5 “×”運(yùn)算作用在完全圖Kn上的性質(zhì)

由運(yùn)算的定義知：

性質(zhì)3K0×Kn=?.(其中K0=?表示空圖)

性質(zhì)4K1×Kn=Kn．

但是“×”運(yùn)算作用在完全圖Kn上的運(yùn)算不封閉，如K2×K2=C4，我們記

定理7 (K,×)構(gòu)成具有單位元的交換半群．

證明 由性質(zhì)4知，K1×Kn=Kn，所以K1為單位元；

由定理2知“×”運(yùn)算滿足結(jié)合律和交換律；所以(K,×)構(gòu)成具有單位元的交換半群．

但是在(K,×)中，任一元素(除K1外)無逆元，所以(K,×)構(gòu)不成群，下面我們設(shè)

重新定義在K[m]上的“×”運(yùn)算：

注：運(yùn)算的實(shí)際意義：

定理8 (K[m],×)構(gòu)成交換群且與(Zm,+)同構(gòu)．

證明 因?yàn)椋?/p>

1)由重新定義知，運(yùn)算封閉;

2)由定理2知，結(jié)合律和交換律成立;

所以(K[m],×)構(gòu)成交換群．

又因?yàn)榇嬖谝粋€映射φ：K[m]→Zm

使得(K[m],×)與(Zm,+)同構(gòu)．

[1]Chen Jinyang, Zhu Wenhui, Jiang Binghua. Cyclic edge-connectivity of transformation graph G++-[J].蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,52(3)：393～395.

[2]Chen Jinyang,Super connectivity and Super Edge connectivity of Transformation Graphs[J]. Ars Combinatoria,2012，(105):103～115.

[3]Chen Jinyang,Meng Jixiang, Huang Lihong. Super edge connectivity of mixed Cayley graph[J]. Discrete Mathematic,2009, (309): 264～270.

[4]Bondy J A,Murty U S R. Graph Theory and Applications[M]．New York：Macmillan,Elseiver,1976.

[5]Reinhard Diestel．Graph Theory[M]．New York：Springer-Verlag,1997．

[6]樊 惲，劉宏偉．抽象代數(shù)[M]．北京：科學(xué)出版社，2008．

[7]李曉毅，黃風(fēng)琴．循環(huán)群中剩余類加群的討論[J].沈陽師范大學(xué)學(xué)報(bào)(自然科學(xué)版) ,2003，21(3)：169～171．

Abstract: In the study of graph theory, the operation of graphs is a method of constructing graphs with special properties. This thesis discusses and studies two kinds of operations of graph G in the respect of structure, operation rules and properties, and make it work on complete graphs, so constructing a finite group wnich is isomorphic to the additive groups of surplus.

Keywords: complete graph; residue class group of module n; isomorphism

Operationalpropertiesoftwokindsofgraphs

ZHANG Qian-Nan CHEN Jin-Yang

( College of Mathematics and Statistics, Hubei Normal University, Huangshi 435002, China)

O157．5

A

2096-3149(2017)03- 0053-05

10.3969/j.issn.2096-3149.2017.03.010

2017—04—20

國家自然科學(xué)基金項(xiàng)目(71701076)，湖北省教育廳青年項(xiàng)目(Q20162504)

張倩男(1993— )，女，天津?qū)氎嫒?，碩士研究生，主要研究方向?yàn)檫\(yùn)籌學(xué)與控制論．