圈空間及其應用*①

徐尚進

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

本文所討論的問題屬代數圖論研究領域,所涉及的圖均為簡單無向圖.

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

1 預備知識

本節給出本文所需要的一些基本概念、性質和結論.

1.1 簡單無向圖

為了給出簡單無向圖的嚴格定義,我們先引進以下記號.

定義1.1設V是非空集合.分別記V的所有有序對的集合為

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

V的所有無序對的集合為

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

注:所謂無序對{u,v},意味著{u,v}={v,u}.

直接計算可知,當V是有限集時有

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

接下來給出簡單無向圖的定義.

定義1.2一個(有限)簡單無向圖Γ是由其(非空)頂點集合V={v1,v2,…,vn}和一個邊的集合E?V{2}決定.邊集E中的無序對{v,u}稱為圖Γ的無向邊,頂點v和u稱為該邊的端點.頂點的個數稱為圖Γ的階,記作|Γ|.

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

每條無向邊{v,u}對應著兩個序相反的有序對(v,u)與(u,v),稱為Γ的弧.弧是有方向的,比如弧(v,u)的起點和終點分別是v和u.Γ的弧集記作Arc(Γ).

由于無向圖Γ的每條邊都對應著一對方向相反的弧,因此有

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

圖1

值得一提的是,簡單無向圖不能有自環(即端點同一的邊)或重邊(即兩條邊的端點對應相同).例如圖1中,有一條端點同為頂點v2的邊,屬自環;還有兩條都以頂點v3和v4為端點的邊,屬重邊.這些在簡單圖中都不能有.

圍繞簡單無向圖還有如下基本概念.

定義1.4設Γ=(V,E)是一個簡單無向圖.

(1) 與v∈V相鄰的頂點個數稱為v的度,記作deg(v),與v相鄰的頂點集合稱為v的鄰域,記作N(v).

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

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

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

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

性質1.5設Γ是簡單無向圖,則Γ的邊數

(1.1)

本文還涉及簡單無向圖的自同構群以及由它建立起來的傳遞性,有關概念詳見文獻[5].

1.2 樹

定義1.6[6]連通無圈的簡單無向圖稱為樹.以樹為連通分支的圖稱為林.

性質1.7[6]設Γ是簡單無向圖，則下列各項等價:

(1)Γ是樹;

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

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

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

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

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

(3)?(4)只需證Γ無圈.假設Γ含有一個k-圈?！?則圈?！渖瞎灿衚個頂點和k條邊.再由|Γ|=|E(Γ)|+1>k,可知?！渲膺€有|Γ|-k個頂點.往證|Γ|-k≤|E(Γ)|-k.為此,定義V(Γ)V(?！?到E(Γ)E(?！?內的一個對應:?v∈V(Γ)V(?！?.由于Γ連通,故存在v到?！涞淖疃搪穂v,v′,…,v″],其中v″∈V(?！?.這時{v,v′} ?E(?！?,于是可令v對應{v,v′}∈E(Γ)E(?！?.顯然這樣的對應是單射,因此|Γ|-k≤|E(Γ)E(?！?|=|E(Γ)|-k,導致|Γ|≤|E(Γ)|,與(3)矛盾.從而(4)成立.

(4)?(1)只需證Γ連通.假設Γ不連通，則可增加k>0條邊使之連通且無圈,這個新圖記作?！?這時V(Γ)=V(?！?,|E(?！鋦=|E(Γ)|+k.往證|E(?！?|≤|?！鋦-1.為此,先取定v∈V(?！?,然后定義E(?！?到V(?！?{v}內的一個對應:?{v′,v″}∈E(?！?,由于?！?連通且無圈,因此d(v′,v)≠d(v″,v).當d(v′,v)>d(v″,v)時,規定{v′,v″}對應于v′.這時v′≠v,且?！涞牟煌吽鶎捻旤c也不同,說明該對應是E(?！?到V(?！?{v}內的單射,因此|E(Γ)|+k=|E(?！?| ≤|?！鋦-1=|Γ|-1,推出|E(Γ)|+1≤|Γ|-k<|Γ|,與(4)矛盾.從而只能有Γ連通.□

推論1.8設Γ是樹，則Γ至少存在2個1度頂點.

1.3 邊空間

給定一個簡單無向圖Γ=(V,E).為方便研究,其邊集相同的子圖視為等同(即不計較子圖的孤立點),無邊的子圖(即空圖)記作?.若Γ的邊集E={e1,e2,…,em},則Γ的子圖?！淇蓪?元域GF(2)上m維向量空間V(m,2)的一個向量(x1,x2,…,xm),其中

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

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

圖2

又設V(m,2)的向量(x1,x2,…,xm)和(y1,y2,…,ym)分別對應Γ的子圖?！浜挺！?，則向量(x1+y1,x2+y2,…,xm+ym)對應的子圖稱為?！渑c?！宓沫h和,記作?！??！?這時,Γ的子圖全體關于環和運算?以及如下定義的數乘運算·：

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

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

性質1.10設?！??！濉蔈(Γ),則

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

(2)?！??！???！??！??.

證明(1) 設子圖?！浜挺！宸謩e對應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 圈空間

圈在圖的研究中扮演重要角色.它與樹的關系既對立(見定義1.7)但又有所關聯.先看一個關于圈數的基本結論.

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

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

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

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

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

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

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

圖3

性質1.14設Γ是連通無向圖,則

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

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

(3) 每棵支撐樹的基本圈個數等于|E(Γ)|-|Γ|+1,因此也與支撐樹的選擇無關.

證明(1) 顯然.

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

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

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

性質1.16C1,C2,…,Cr是線性無關的,因此dimC(Γ)=r,|C(Γ)|=2r.

1.5 覆蓋圖

設Γ是一個簡單無向圖,K是一個群.如果存在Arc(Γ)到K的一個映射φ滿足

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

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

覆蓋圖明顯具有以下性質.

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

圖4

圖5

2 有關引理

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

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

圖6

(2) 對k用歸納法.當k=0時,?！??,結論成立.

圖7

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

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

3 主要結論

由于簡單無向圖Γ的邊空間E(Γ)關于子圖的“環和”運算是方次數為2的加群,因此可取K∶=E(Γ)來構造非平凡的K-鏈.

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

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

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

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

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

再定義半直積GK在邊覆蓋圖頂點集上的作用

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

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

定理3.3沿用定義3.1的記號.

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

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

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

是頂點(v,?！?到(u,?！??！?的一條路.

? 同理可證(略).

(3) 分兩種情況.

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

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

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

注:文獻[7,p152,Theorem 19.5]也就類似的結論給出了證明,但不夠嚴謹.