圈空間及其應(yīng)用*①

徐尚進(jìn)

(廣西大學(xué),廣西 南寧 530004)

本文所討論的問題屬代數(shù)圖論研究領(lǐng)域,所涉及的圖均為簡(jiǎn)單無(wú)向圖.

代數(shù)方法一直是圖論研究的重要手段.比如利用圖的全自同構(gòu)群可以研究圖的某種傳遞性,利用圖的鄰接矩陣則可以研究圖的譜,等等.用代數(shù)方法研究圖還包括研究其邊空間和圈空間,這部分內(nèi)容在不少圖論文獻(xiàn)[1,2,3,4]中都有介紹.然而所給的定義不都完全相同,并且對(duì)邊空間的描述也不夠嚴(yán)謹(jǐn).本文主要討論圖的邊空間特別是圈空間,通過完善邊空間的定義來(lái)得圈空間的精準(zhǔn)結(jié)構(gòu),最后將有關(guān)結(jié)論應(yīng)用于邊覆蓋圖.

1 預(yù)備知識(shí)

本節(jié)給出本文所需要的一些基本概念、性質(zhì)和結(jié)論.

1.1 簡(jiǎn)單無(wú)向圖

為了給出簡(jiǎn)單無(wú)向圖的嚴(yán)格定義,我們先引進(jìn)以下記號(hào).

定義1.1設(shè)V是非空集合.分別記V的所有有序?qū)Φ募蠟?/p>

V(2)∶={ (u,v)|u,v∈V,u≠v} ;

V的所有無(wú)序?qū)Φ募蠟?/p>

V{2}∶={ {u,v}|u,v∈V,u≠v} .

注:所謂無(wú)序?qū)u,v},意味著{u,v}={v,u}.

直接計(jì)算可知,當(dāng)V是有限集時(shí)有

|V(2)| = |V| ( |V|-1) ,|V{2}| = |V| ( |V| -1 ) /2.

接下來(lái)給出簡(jiǎn)單無(wú)向圖的定義.

定義1.2一個(gè)(有限)簡(jiǎn)單無(wú)向圖Γ是由其(非空)頂點(diǎn)集合V={v1,v2,…,vn}和一個(gè)邊的集合E?V{2}決定.邊集E中的無(wú)序?qū)v,u}稱為圖Γ的無(wú)向邊,頂點(diǎn)v和u稱為該邊的端點(diǎn).頂點(diǎn)的個(gè)數(shù)稱為圖Γ的階,記作|Γ|.

具有頂點(diǎn)集V和邊集E的圖Γ通常記作Γ=(V,E).反之,圖Γ的頂點(diǎn)集和邊集又分別記作V(Γ)和E(Γ).

每條無(wú)向邊{v,u}對(duì)應(yīng)著兩個(gè)序相反的有序?qū)?v,u)與(u,v),稱為Γ的弧.弧是有方向的,比如弧(v,u)的起點(diǎn)和終點(diǎn)分別是v和u.Γ的弧集記作Arc(Γ).

由于無(wú)向圖Γ的每條邊都對(duì)應(yīng)著一對(duì)方向相反的弧,因此有

性質(zhì)1.3|Arc(Γ) |=2|E(Γ)|.

圖1

值得一提的是,簡(jiǎn)單無(wú)向圖不能有自環(huán)(即端點(diǎn)同一的邊)或重邊(即兩條邊的端點(diǎn)對(duì)應(yīng)相同).例如圖1中,有一條端點(diǎn)同為頂點(diǎn)v2的邊,屬自環(huán);還有兩條都以頂點(diǎn)v3和v4為端點(diǎn)的邊,屬重邊.這些在簡(jiǎn)單圖中都不能有.

圍繞簡(jiǎn)單無(wú)向圖還有如下基本概念.

定義1.4設(shè)Γ=(V,E)是一個(gè)簡(jiǎn)單無(wú)向圖.

(1) 與v∈V相鄰的頂點(diǎn)個(gè)數(shù)稱為v的度,記作deg(v),與v相鄰的頂點(diǎn)集合稱為v的鄰域,記作N(v).

特別地,度數(shù)為0的頂點(diǎn)稱為孤立點(diǎn);度數(shù)等于同一個(gè)常數(shù)k的圖稱為正則圖,k稱為該正則圖的度數(shù),記作Val(Γ).

(2) 如果V′?V,E′?E∩V′[2],則稱?！?(V′,E′)為Γ的子圖.進(jìn)一步,如果V′=V,E′?E,則稱?！涫铅５闹巫訄D;如果V′?V,E′=E∩V′[2],則稱Γ′=(V′,E′)為V′的導(dǎo)出子圖,記作[V′].

(3) 如果Γ的一個(gè)由兩兩不同頂點(diǎn)組成的序列v0,v1,…,vk滿足{vi-1,vi}∈E(i=1,2,…,k),則這個(gè)頂點(diǎn)序列稱為Γ的一條路,詳稱k-路,記作[v0,v1,…,vk],其中k稱為這條路的長(zhǎng).而長(zhǎng)大于2且首尾相等的k-路[v0,v1,…,vk-1,vk=v0]稱為k-圈,簡(jiǎn)稱圈,記作Ck.

(4) 在頂點(diǎn)集合V中定義關(guān)系“～”：v～u當(dāng)且僅當(dāng)存在從v到u的路,易知“～”是等價(jià)關(guān)系.我們把每個(gè)等價(jià)類的導(dǎo)出子圖稱為Γ的一個(gè)連通分支.如果Γ只有一個(gè)連通分支,則稱Γ是連通圖.此時(shí),Γ中任意兩個(gè)頂點(diǎn)之間至少存在一條路.

性質(zhì)1.5設(shè)Γ是簡(jiǎn)單無(wú)向圖,則Γ的邊數(shù)

(1.1)

本文還涉及簡(jiǎn)單無(wú)向圖的自同構(gòu)群以及由它建立起來(lái)的傳遞性,有關(guān)概念詳見文獻(xiàn)[5].

1.2 樹

定義1.6[6]連通無(wú)圈的簡(jiǎn)單無(wú)向圖稱為樹.以樹為連通分支的圖稱為林.

性質(zhì)1.7[6]設(shè)Γ是簡(jiǎn)單無(wú)向圖，則下列各項(xiàng)等價(jià):

(1)Γ是樹;

(2)Γ的任意2點(diǎn)之間有且僅有一條路;

(3)Γ連通且|Γ|=|E(Γ)|+1;

(4)Γ無(wú)圈且|Γ|=|E(Γ)|+1.

證明(1)?(2)由Γ連通,則Γ的任意2點(diǎn)v,u之間至少存在一條路,設(shè)為[v0=v,v1,v2,…,vk-1,vk=u].假設(shè)v,u之間存在另一條路[u0=v,u1,u2,…,ul-1,ul=u]，則先取i是使vi≠ui的最小正整數(shù).易知i

(2)?(3)Γ顯然連通.為證明|Γ|=|E(Γ)|+1,可對(duì)|Γ|用歸納法.事實(shí)上,當(dāng)|Γ|=1時(shí),由E(Γ)=?,得1=|Γ|=|E(Γ)|+1.結(jié)論成立.假設(shè)結(jié)論對(duì)于頂點(diǎn)數(shù)小于|Γ|的圖成立.由于Γ的某2點(diǎn)之間僅有一條路,故Γ在刪去該路的一條邊后被分割為兩個(gè)連通分支Γ1和Γ2.這時(shí),|Γ1|+|Γ2|=|Γ|,|E(Γ1)|+|E(Γ2)|=|E(Γ)|-1.再由歸納假設(shè),|Γi|=|E(Γi)|+1,i=1,2.從而|Γ|=|Γ1|+|Γ2|=|E(Γ1)|+|E(Γ2)|+2=|E(Γ)|+1.

(3)?(4)只需證Γ無(wú)圈.假設(shè)Γ含有一個(gè)k-圈?！?則圈Γ′上共有k個(gè)頂點(diǎn)和k條邊.再由|Γ|=|E(Γ)|+1>k,可知?！渲膺€有|Γ|-k個(gè)頂點(diǎn).往證|Γ|-k≤|E(Γ)|-k.為此,定義V(Γ)V(?！?到E(Γ)E(?！?內(nèi)的一個(gè)對(duì)應(yīng):?v∈V(Γ)V(?！?.由于Γ連通,故存在v到Γ′的最短路[v,v′,…,v″],其中v″∈V(?！?.這時(shí){v,v′} ?E(?！?,于是可令v對(duì)應(yīng){v,v′}∈E(Γ)E(?！?.顯然這樣的對(duì)應(yīng)是單射,因此|Γ|-k≤|E(Γ)E(?！?|=|E(Γ)|-k,導(dǎo)致|Γ|≤|E(Γ)|,與(3)矛盾.從而(4)成立.

(4)?(1)只需證Γ連通.假設(shè)Γ不連通，則可增加k>0條邊使之連通且無(wú)圈,這個(gè)新圖記作?！?這時(shí)V(Γ)=V(Γ′),|E(?！鋦=|E(Γ)|+k.往證|E(?！?|≤|Γ′|-1.為此,先取定v∈V(?！?,然后定義E(?！?到V(Γ′){v}內(nèi)的一個(gè)對(duì)應(yīng):?{v′,v″}∈E(?！?,由于?！?連通且無(wú)圈,因此d(v′,v)≠d(v″,v).當(dāng)d(v′,v)>d(v″,v)時(shí),規(guī)定{v′,v″}對(duì)應(yīng)于v′.這時(shí)v′≠v,且?！涞牟煌吽鶎?duì)應(yīng)的頂點(diǎn)也不同,說(shuō)明該對(duì)應(yīng)是E(?！?到V(?！?{v}內(nèi)的單射,因此|E(Γ)|+k=|E(?！?| ≤|Γ′|-1=|Γ|-1,推出|E(Γ)|+1≤|Γ|-k<|Γ|,與(4)矛盾.從而只能有Γ連通.□

推論1.8設(shè)Γ是樹，則Γ至少存在2個(gè)1度頂點(diǎn).

1.3 邊空間

給定一個(gè)簡(jiǎn)單無(wú)向圖Γ=(V,E).為方便研究,其邊集相同的子圖視為等同(即不計(jì)較子圖的孤立點(diǎn)),無(wú)邊的子圖(即空?qǐng)D)記作?.若Γ的邊集E={e1,e2,…,em},則Γ的子圖?！淇蓪?duì)應(yīng)于2元域GF(2)上m維向量空間V(m,2)的一個(gè)向量(x1,x2,…,xm),其中

反之,V(m,2)的任意一個(gè)m維向量(x1,x2,…,xm)也可對(duì)應(yīng)于Γ的一個(gè)子圖?！?,其中E(Γ′)={ei|xi=1}?E.由此,Γ的子圖共有|V(m,2)|=2m個(gè).

例1.94階完全圖K4具有頂點(diǎn)集V(K4)={v1,v2,v3,v4}和邊集E(K4)={e1,e2,…,e6}(見圖2).

圖2

又設(shè)V(m,2)的向量(x1,x2,…,xm)和(y1,y2,…,ym)分別對(duì)應(yīng)Γ的子圖?！浜挺！?，則向量(x1+y1,x2+y2,…,xm+ym)對(duì)應(yīng)的子圖稱為?！渑cΓ″的環(huán)和,記作?！??！?這時(shí),Γ的子圖全體關(guān)于環(huán)和運(yùn)算?以及如下定義的數(shù)乘運(yùn)算·：

0·Γ′ = ?,1·?！?=?！?，

構(gòu)成2元域GF(2)上的m維線性空間,稱為圖Γ的邊空間,記作E(Γ).

性質(zhì)1.10設(shè)?！?Γ″∈E(Γ),則

(1)E(?！??！?=E(?！?∪E(?！?E(?！?∩E(Γ″),

(2)?！?Γ″???！??！??.

證明(1) 設(shè)子圖?！浜挺！宸謩e對(duì)應(yīng)V(m,2)的向量(x1,x2,…,xm)和(y1,y2,…,ym).由

即得

e∈E(?！??！? ??e∈E(?！?E(Γ″)∪E(?！?E(Γ′)??

e∈E(?！?∪E(?！?E(Γ′)∩E(?！?.

(2) 由(1)推出,Γ′=?！??E(?！?=E(?！???E(?！??！?=????！?Γ″=?.即證得(2).□

1.4 圈空間

圈在圖的研究中扮演重要角色.它與樹的關(guān)系既對(duì)立(見定義1.7)但又有所關(guān)聯(lián).先看一個(gè)關(guān)于圈數(shù)的基本結(jié)論.

引理1.11設(shè)Γ是連通無(wú)向圖,則Γ至少有|E(Γ)|-|Γ|+1個(gè)圈.

證明對(duì)|E(Γ)|用歸納法.

當(dāng)|E(Γ) |≤ 2時(shí),圖Γ無(wú)圈.再由性質(zhì)1.7,即得|E(Γ)|-|Γ|+1=0,結(jié)論成立.當(dāng)|E(Γ)|>2時(shí),如果Γ無(wú)圈,則同上理結(jié)論也已成立.如果Γ有圈,則將刪去該圈一條邊后的子圖記作?！?顯然Γ的圈要比?！涞娜χ辽俣喑?個(gè).另一方面,由于Γ′仍然連通,并且|?！鋦=|Γ|,|E(?！?|=|E(Γ)|-1，因此由歸納假設(shè),?！渲辽儆衸E(Γ′)|-|?！鋦+1=|E(Γ)|-|Γ|個(gè)圈.從而Γ至少有|E(Γ)|-|Γ|+1個(gè)圈.□

推論1.12設(shè)Γ是連通無(wú)向圖.若|E(Γ)|=|Γ|,則Γ有且僅有1個(gè)圈.

證明根據(jù)定理1.11,圖Γ至少有|E(Γ)|-|Γ|+1=1個(gè)圈.假設(shè)Γ有2個(gè)不相等的圈C和C′.不妨設(shè)C′有一條邊不在C上,并記Γ′為Γ刪去該邊后的子圖，則?！溆腥并依然連通.但|?！鋦=|Γ|=|E(Γ)|=|E(?！?|+1,導(dǎo)致?！涫菢?性質(zhì)1.7),與前述矛盾.說(shuō)明Γ只有1個(gè)圈.□

定義1.13連通無(wú)向圖Γ的一個(gè)支撐子圖Ψ如果是樹則稱為支撐樹.這時(shí),Ψ的邊稱為Ψ的樹枝,而E(Γ)E(Ψ)中的邊稱為Ψ的連枝.支撐樹Ψ添加一條連枝后有且僅有一個(gè)圈(由推論1.12),稱為Ψ的基本圈.基本圈作為子圖自然都含于Γ的邊空間E(Γ).

以下是4階完全圖K4和它的一棵支撐樹Ψ及其基本圈.Ψ的樹枝集為{e1,e2,e3},連枝集為{e4,e5,e6}.

圖3

性質(zhì)1.14設(shè)Γ是連通無(wú)向圖,則

(1)Γ的支撐樹通常不唯一,除非Γ本身是樹;

(2) 每棵支撐樹的連枝條數(shù)等于|E(Γ) |-|Γ|+1,因此與支撐樹的選擇無(wú)關(guān);

(3) 每棵支撐樹的基本圈個(gè)數(shù)等于|E(Γ)|-|Γ|+1,因此也與支撐樹的選擇無(wú)關(guān).

證明(1) 顯然.

(2) 任取Γ的一棵支撐樹Ψ.先由性質(zhì)1.7,得|Ψ|=|E(Ψ)|+1.再由V(Ψ)=V(Γ),即得Ψ的連枝條數(shù)|E(Γ)E(Ψ)|=|E(Γ)|-|E(Ψ)|=|E(Γ)|-|Ψ|+1=|E(Γ)|-|Γ|+1.

(3) 由基本圈的定義及(2)立得.

定義1.15設(shè)Γ是連通無(wú)向圖,C1,C2,…,Cr∈E(Γ)是Γ的某棵支撐樹的基本圈全體,即r=|E(Γ)|-|Γ|+1,則E(Γ)的子空間〈C1,C2,…,Cr〉稱為Γ的圈空間,記作C(Γ).

性質(zhì)1.16C1,C2,…,Cr是線性無(wú)關(guān)的,因此dimC(Γ)=r,|C(Γ)|=2r.

1.5 覆蓋圖

設(shè)Γ是一個(gè)簡(jiǎn)單無(wú)向圖,K是一個(gè)群.如果存在Arc(Γ)到K的一個(gè)映射φ滿足

φ(v,u)=[φ(u,v)]-1,(v,u)∈Arc(Γ),

則稱φ是圖Γ的一個(gè)K-鏈.若映射φ平凡,即對(duì)所有(v,u)∈Arc(Γ),有φ(v,u)≡1,則φ顯然是圖Γ的一個(gè)K-鏈,稱為平凡K- 鏈.

覆蓋圖明顯具有以下性質(zhì).

例1.20[7]設(shè)Γ是簡(jiǎn)單無(wú)向圖.取K∶=2={0,1},并對(duì)Γ的每條弧(v,u)∈Arc(Γ),定義φ(v,u)≡1(對(duì)合).則映射φ是Γ上的一個(gè)2-鏈,并且覆蓋圖2是具有二部劃分(V(Γ),0)與(V(Γ),1)的二部圖,稱為Γ的雙覆蓋圖.比如,當(dāng)Γ=C4時(shí),覆蓋圖(不再連通,見圖4).又比如,當(dāng)Γ=K4時(shí),覆蓋圖2同構(gòu)于立方體圖Q3(見圖5).

圖4

圖5

2 有關(guān)引理

引理2.1(1) 若C和C′是E(Γ)的圈,則C?C′或者是空?qǐng)D,或者是若干個(gè)邊不交的圈之并.

證明(1) 只需考慮圈C與C′不等,并且它們的邊集有交的情況.這時(shí),邊的交集只能是若干條不相連的路.當(dāng)C與C′取“環(huán)和”運(yùn)算之后,這些路被去掉(見圖6),而C與C′各自剩下的若干條不相連的路之間一一對(duì)應(yīng),即可組成一些邊不交的圈.

圖6

(2) 對(duì)k用歸納法.當(dāng)k=0時(shí),?！??,結(jié)論成立.

圖7

引理2.2(1) C (Γ)中非空子圖是若干個(gè)邊不交的圈之并;

(2) 如果Γ的子圖Γ′∈ E(Γ)是若干個(gè)邊不交的圈之并,則?！洹?C (Γ).

3 主要結(jié)論

由于簡(jiǎn)單無(wú)向圖Γ的邊空間E(Γ)關(guān)于子圖的“環(huán)和”運(yùn)算是方次數(shù)為2的加群,因此可取K∶=E(Γ)來(lái)構(gòu)造非平凡的K-鏈.

定義3.1[7]設(shè)Γ是連通無(wú)向圖,取K∶=E(Γ),并且很自然地定義Arc(Γ)到K內(nèi)的映射

性質(zhì)3.2[7]沿用上述記號(hào),并令G∶=Aut(Γ)，則G與K的(外)半直積GK是邊覆蓋圖的自同構(gòu)(子)群.特別地,如果Γ是點(diǎn)傳遞圖,則亦然.

證明先定義σ∈G在K=E(Γ)上的作用

這時(shí),??！?Γ″∈E(Γ),(?！??！?σ=?！洇??！濡?即GAut(K).根據(jù)群論知識(shí),存在G與K的半直積GK∶={(σ,?！?|σ∈G,?！蔏},其乘法關(guān)系如下:

(σ′,Γ′)(σ″,?！?=(σ′σ″,?！洇摇??！?.

再定義半直積GK在邊覆蓋圖頂點(diǎn)集上的作用

(v,k)(σ,?！?∶=(vσ,kσ?Γ′),(σ,?！?∈GK.

推出(σ,?！?∈GK保邊,因此是邊覆蓋圖的一個(gè)自同構(gòu).即G

定理3.3沿用定義3.1的記號(hào).

[(v,?)=(v0,Γ0),(v1,Γ1),(v2,Γ2),…,(vl,Γl)=(u,Γ′)] ,

其中(vj-1,vj)∈Arc(Γ),Γj=Γj-1?{vj-1,vj},j=1,2,…,l.這時(shí)?！?Γj=?！?Γj-1?{vj-1,vj},j=1,2,…,l.從而

[(v,?！?=(v0,Γ″?Γ0),(v1,Γ″?Γ1),(v2,?！?Γ2),…,(vl，?！?Γl)=(u,?！?Γ″)]

是頂點(diǎn)(v,?！?到(u,?！??！?的一條路.

? 同理可證(略).

(3) 分兩種情況.

(i)v∈V(C).由(2)立得.

(ii)v?V(C).此時(shí)存在頂點(diǎn)v到圈C的一條路L：[v0=v,v1,…,vl],其中vl∈V(C).

[(v,?)=(v0,Γ0),(v1,Γ1),(v2,Γ2),…,(vl,Γl)=(v,Γ′)],

注:文獻(xiàn)[7,p152,Theorem 19.5]也就類似的結(jié)論給出了證明,但不夠嚴(yán)謹(jǐn).