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

張倩男，陳金陽

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

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

張倩男，陳金陽

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

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

完全圖；模n剩余類群；同構

1 問題背景

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

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

2 基本概念及術語

定義1 “*”運算：令H1=G1*G2，則

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

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

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

每個頂點的度都增大了，進而提高了圖的連通性．

定義2 “*”運算： 令H2=G1×G2，則

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

Ⅰ)x1=x2且y1～y2inG2；

Ⅱ)y1=y2且x1～x2inG1．

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

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

稱G1與G2同構，記作G1?G2．

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

定理1 “*”運算滿足下面兩條性質(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 “*”運算在同構意義下滿足以上兩條性質(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．

注：兩種運算都不滿足分配律．

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

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

由運算的定義知：

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

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

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

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

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

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

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

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

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

注：運算的實際意義：

1)當n1+n2

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

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

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

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

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

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

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

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

Ki→φ(Ki)

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

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

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

由運算的定義知：

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

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

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

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

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

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

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

重新定義在K[m]上的“×”運算：

注：運算的實際意義：

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

證明 因為：

1)由重新定義知，運算封閉;

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

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

又因為存在一個映射φ：K[m]→Zm

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

[1]Chen Jinyang, Zhu Wenhui, Jiang Binghua. Cyclic edge-connectivity of transformation graph G++-[J].蘭州大學學報(自然科學版),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]．北京：科學出版社，2008．

[7]李曉毅，黃風琴．循環(huán)群中剩余類加群的討論[J].沈陽師范大學學報(自然科學版) ,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

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

張倩男(1993— )，女，天津?qū)氎嫒耍T士研究生，主要研究方向為運籌學與控制論．