向量空間上的仿射包含圖

王 麗，黃 迪

(河南理工大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 河南 焦作 454000)

0 引言

圖論和代數(shù)是近代數(shù)學(xué)的兩個重要分支，在物理、化學(xué)和計算機科學(xué)等領(lǐng)域有著重要的理論意義和應(yīng)用價值。兩者雖然研究內(nèi)容不同，卻有著緊密的聯(lián)系:圖論性質(zhì)可以用來研究代數(shù)結(jié)構(gòu)，代數(shù)的理論也常用來解決圖論問題。因此，許多學(xué)者將它們結(jié)合起來進行研究。1988年，文獻[1]首次提出交換環(huán)的零因子圖概念，建立了圖論與交換環(huán)理論的聯(lián)系。從此，圖與各種代數(shù)結(jié)構(gòu)結(jié)合起來進行研究引起了學(xué)者們的廣泛關(guān)注。例如，文獻[2-3]研究了有限群、冪零群、內(nèi)冪零群以及內(nèi)交換群上冪圖的相關(guān)性質(zhì)。文獻[4-5]分別對交換環(huán)和單演半群上的點積圖進行了研究。文獻[6]分類了有限群上的正則交圖，并給出了交圖自同構(gòu)群的結(jié)構(gòu)。文獻[7-8]研究了圖的自同態(tài)幺半群，建立起圖論和半群代數(shù)理論的聯(lián)系，并將半群理論用于圖論的研究。文獻[9-10]定義了向量空間上的非零組合圖，研究了圖的獨立數(shù)、哈密爾頓性及邊連通度等。文獻[11-12]研究了向量空間上子空間包含圖的歐拉性、點傳遞性、直徑等，隨后文獻[13]確定了子空間包含圖自同構(gòu)群的結(jié)構(gòu)。

目前，圖和代數(shù)結(jié)構(gòu)的結(jié)合研究大多與群、半群、環(huán)等代數(shù)結(jié)構(gòu)相關(guān)，有關(guān)仿射幾何的圖研究還比較少。因此，本文定義了仿射包含圖In(AV)，利用向量空間、仿射幾何及圖論的相關(guān)知識，討論了圖In(AV)的圍長、著色數(shù)和團數(shù)等基本性質(zhì)，并給出了仿射包含圖同構(gòu)與向量空間同構(gòu)之間的關(guān)系。

1 預(yù)備知識

本文所討論的圖都是簡單無向圖，關(guān)于圖論方面未提及的概念、符號等可參閱文獻[14]。圖中頂點vi的度數(shù)是與vi相關(guān)聯(lián)的邊的數(shù)目，記作d(vi)。沒有邊的圖稱為空圖。M=v0,e0,v1,…,ek-1,vk是一條從v0到vk的長度為k的途徑。如果對任意的i≠j，都有vi≠vj，則稱M是一條道路。如果圖G中任意兩個頂點之間都存在一條道路，則稱G為連通的。一條封閉的路稱為圈，為了方便，常用v1,v2,…,vk,v1表示一條長度為k的圈。G的圍長是G中最短圈的長度，記作g(G)。特別地，如果G不含任何圈，則g(G)=∞。如果對于G中的任意頂點v，總存在一個三角形(u,v,w)，其中u,v∈V(G)，則稱G可三角化。圖G的一個完全子圖稱為團，圖G中最大完全子圖所含的頂點個數(shù)是G的團數(shù)，記作ω(G)。著色數(shù)χ(G)是滿足圖G中相鄰頂點分配不同顏色所需顏色數(shù)的最小值。

給定一個q元域上的n維向量空間V，V中k維子空間的個數(shù)[15]為:

仿射幾何是由V中的向量和仿射子空間組成的，仿射子空間可由V中向量子空間經(jīng)過平移得到，因此若S是一個k維子空間，則對于任意β∈V，S+β:={α+β|α∈S}是一個k維仿射子空間。規(guī)定若S=?，且dim({β})=0，則S+β={β}。顯然，若β′∈(S+β)，則S+β′=S+β。關(guān)于仿射幾何未提及的內(nèi)容，可以參閱文獻[16]。文獻[11]定義了V的子空間包含圖In(V)，其點集是V中非平凡子空間的集合，任取W1,W2∈V(In(V))，若W1?W2或W2?W1，則(W1,W2)∈E(In(V))。受此啟發(fā)，本文定義了仿射包含圖。在下文中，除非特別提到，V都是q元域上的n維向量空間，S是V中的向量子空間。

2 仿射包含圖的結(jié)構(gòu)及基本性質(zhì)

定義1令V是q元域F上的有限維向量空間，S是V的一個子空間且S≠V。定義仿射包含圖In(AV)如下:

V(In(AV))={S+β|?β∈V}；

E(In(AV))={(S1+α,S2+β)|S1+α?S2+β或S2+β?S1+α}。

例1令{α1,α2}是V的一組基，q=Z2，則2維向量空間上的仿射包含圖In(AV)如圖1所示。

圖1 2維向量空間上的仿射包含圖In(AV)

引理1任取S1,S2∈V(In(AV))，下列結(jié)論成立:

(Ⅰ) 若S1≠S2，則S1+α≠S2+β。

(Ⅱ)S1+α?S2+β的充要條件是S1?S2且α∈S2+β。

(Ⅲ) 若S1，S2是向量空間V的兩個不同的子空間，且0≤dim(S1)=dim(S2)≤n-1， 則(S1+α,S2+β)?E(In(AV))。

證明(Ⅰ) 若α∈S2+β，則S2+α=S2+β。由于S1≠S2，則S1+α≠S2+α，因此S1+α≠S2+β。若α?S2+β，而α∈S1+α，因此S1+α≠S2+β。證畢。

(Ⅱ)充分性顯然成立，下證必要性。若S1+α?S2+β，則α∈S2+β，因此S2+α=S2+β。顯然S1+α?S2+α。對任意的β∈S1，總有β+α∈S1+α。明顯地，β+α∈S2+α，因此β∈S2。由β的任意性可知S1?S2。證畢。

(Ⅲ)假設(shè)(S1+α,S2+β)∈E(In(AV))，則S1+α?S2+β或S2+β?S1+α。由證明(Ⅱ)可知：S1?S2或S2?S1。而dim(S1)=dim(S2)，因此S1=S2，與已知條件矛盾。證畢。

定理1In(AV)是一個n部圖。

證明因為V是一個n維向量空間，所以In(AV)的頂點集可以被劃分為n個互不相交的部分，即V(In(AV))=V0∪V1∪…∪Vn-1，其中，v∈Vi且dim(v)=i。由引理1的證明(Ⅲ)可得，對任意v,u∈Vi，i=0,…,n-1，總有(u,v)?E(In(AV))。因此，In(AV)是一個n部圖。證畢。

接下來，討論仿射包含圖In(AV)的頂點個數(shù)和每個頂點的度數(shù)。

引理2任取α∈V，頂點S和S+α的度數(shù)相等。

證明假設(shè)S′?S，S?S″，其中S′和S″是向量子空間。則存在仿射子空間S′+α和S″+α，滿足S′+α?S+α及S+α?S″+α。因此d(S)≤d(S+α)。

假設(shè)S′+β?S+α，S+α?S″+γ，其中S′+β和S″+γ是仿射子空間。由引理1中的(Ⅱ)可知，S′?S,S?S″。因此d(S+α)≤d(S)。綜上，d(S+α)=d(S)。證畢。

推論1若dim(V)=1，則In(AV)是一個有q個頂點的空圖。

引理3若dim(V)≥2，則In(AV)是連通圖。

證明任取S1+α,S2+β∈V(In(AV))，顯然總存在一條連接這兩點的路:S1+α,α,〈α〉,0,〈β〉,β,S2+β。 因此，In(AV)是連通的。證畢。

3 仿射包含圖的相關(guān)特征

引理4若dim(V)=2，則In(AV)無奇圈。

證明任取vi∈V(In(AV))，因為dim(V)=2，所以仿射子空間vi是0維或1維的。假設(shè)存在奇圈v1,v2,…,vk,v1，其中k是奇數(shù)。由引理1中的(Ⅲ)可得:

dim(v1)=dim(v3)=…=dim(vk-2)=dim(vk)，

這與(v1,vk)∈E(In(AV))矛盾，因此引理4成立。證畢。

定理4若dim(V)=n，則In(AV)的圍長為:

證明因為In(AV)是簡單圖，因此沒有重邊，則沒有長度為2的圈。若n=1，由推論1易知g(In(AV))=∞。

若n=2，由引理4可知In(AV)沒有奇圈。下證In(AV)中不含長度為4的圈。假設(shè)存在一個長度為4的圈:v1,v2,v3,v4,v1，不失一般性，令dim(v1)=dim(v3)=1且dim(v2)=dim(v4)=0。假設(shè)v1=〈α〉+γ，v3=〈β〉+γ′。若α和β線性相關(guān)，則|v1∩v3|=0。若α和β線性無關(guān)，則|v1∩v3|=1。因此至多存在一個頂點同時與v1和v3相鄰，但v2和v4都與v3相鄰，矛盾。因此，不存在長度為4的圈。然而，〈α〉+γ,γ,〈γ〉,0,〈α+γ〉,α+γ,〈α〉+γ是一個長度為6的圈，因此圍長為6。

假定α和β是V中的兩個向量，若n≥3，γ=k1α+k2β，k1,k2∈F，顯然〈α〉+γ,〈α,β〉+γ,γ,〈α〉+γ是一個三角形，因此圍長為3。證畢。

定理5若dim(V)≥3，則In(AV)可三角化。

證明令S是V的一個子空間，{α1,α2,…,αn}是V的一組基，γ是V中的向量。

若dim(S+γ)<2，令S=α1或〈α1〉，顯然α1+γ,〈α1〉+γ,〈α1,α2〉+γ,α1+γ是一個三角形。

若dim(S+γ)≥2，令S=〈α1,α2,…,αk〉，k≥2，顯然存在V中的兩個子空間S′=〈α1,α2,…,αk-1〉，S″=〈α1,α2,…,αk-2〉，使得S+γ,S′+γ,S″+γ,S+γ是一個三角形。證畢。

定理6V是一個n維向量空間，當(dāng)且僅當(dāng)ω(In(AV))=n。

證明因為In(AV)是一個n部圖，則其頂點集V(In(AV))可被表示為n個獨立集的并。此外，其最大團不能包含多于每個獨立集合的一個頂點，因此ω(In(AV))≤n。令{α1,α2,…,αn}為n維向量空間V的一組基，Si=〈α1,α2,…,αi〉，i=1,2,…,n-1。顯然，{α,S1+α,…,Sn-1+α}是一個大小為n的團，其中α∈V。因此，ω(In(AV))=n。反過來，若ω(In(AV))=n，令dim(V)=m，由上述證明過程易知ω(In(AV))=m，因此m=n。證畢。

推論2令V是一個n維向量空間，且n≥5，則In(AV)不可平面。

證明由定理6可知，ω(In(AV))≥5，即In(AV)包含一個完全圖K5作為子圖，因此不可平面。證畢。

定理7若V是一個n維向量空間，則χ(In(AV))=n。

證明根據(jù)文獻[17]的標(biāo)記5.1.2，In(AV)是n可著色的，即χ(In(AV))≤n。任取V中的向量γ，m維非平凡子空間S，不失一般性，令S=〈α1,α2,…,αm〉。將{α1,α2,…,αm}擴充為V的一組基{α1,α2,…,αn}。顯然，γ,〈α1〉+γ,〈α1,α2〉+γ,…,〈α1,α2,…,αm〉+γ,…,〈α1,α2,…,αm,…,αn-1〉+γ構(gòu)成一個n個點的完全圖，即對于任意的S+γ∈V(In(AV))，都有S+γ∈V(Kn)。因此χ(In(AV))=n。證畢。

定理8令V1和V2是域F上的兩個有限維向量空間，則In(AV1)和In(AV2)同構(gòu)的充要條件是V1和V2同構(gòu)。

證明充分性: 假設(shè)V1和V2作為向量空間是同構(gòu)的，令{α1,α2,…,αn}和{β1,β2,…,βn}分別為V1和V2的一組基。令τ是V1到V2的一個同構(gòu)映射，并且滿足:

τ(a1α1+a2α2+…+anαn)=a1τ(α1)+a2τ(α2)+…+anτ(αn)，其中a1,a2,…,an∈F。

τ(τ-1(S)+τ-1(α))=S+α，

(S+β,S′+α)∈E(In(AV1))?
S+β?S′+α或S′+α?S+β?
τ(S+β)?τ(S′+α)或τ(S′+α)?τ(S+β)?
(τ(S+β),τ(S′+α))∈E(In(AV2))。

因此，In(AV1)和In(AV2)同構(gòu)。

必要性: 令dim(V1)=n1，dim(V2)=n2。由定理6可得:ω(In(AV1))=n1，ω(In(AV2))=n2。因為In(AV1)和In(AV2)同構(gòu)，所以n1=n2，因此V1與V2同構(gòu)。證畢。