周麗霞

(無錫城市職業(yè)技術學院 會計系，江蘇 無錫 214000)

簡單圖的子圖及其性質(zhì)研究

周麗霞

(無錫城市職業(yè)技術學院 會計系，江蘇 無錫 214000)

給出圖論中關于子圖的定義,并得到子圖的一些性質(zhì)。通過定理闡述子圖與其導出子圖的同構(gòu)性、子圖與哈密爾頓圖的關系,并證明和舉例。

圖論;子圖;同構(gòu);哈密爾頓圖

本文給出了子圖的定義,并研究了子圖的一些性質(zhì)和它與其導出子圖的一些關系。本文所引用的定義及符號詳見文獻[1],文章所涉及的圖均為無端點圖。

在圖論中,自環(huán)是兩端連接著同一端點的邊。既不含平行邊又不含自環(huán)的圖稱為簡單圖[1]。給定1個簡單圖

G=(V,E),我們可以定義它的子圖H,即取G的邊集E作為H的頂點集,對H的邊集W作如下規(guī)定:若G中任一點v在G中只關聯(lián)邊x,y,則令無序?qū)?x,y)∈W,若v在G中關聯(lián)邊x1，…，xn(n>2,n為正整數(shù)),則在x1,…,xn中任選出2條邊xi,xj,令無序?qū)?xi,xj)∈W。若V′是V的1個非空子集,以V′為頂點集,以兩端點均在V′中的邊的全體為邊集所組成的子圖,稱為G的由V′導出的子圖,簡稱為G的導出子圖[2]。

依定義可知,G的頂點集和邊集與H的邊集和頂點集是一一對應的。

1 子圖的性質(zhì)

由子圖H的定義可知,圖G的子圖H不唯一(見圖1)且有以下性質(zhì)。

定理1圖G=(V,E)的子圖(指標號圖)H的個數(shù)為

(1)

圖1 圖G及其3個子圖

設G=(V，E)是沒有孤立點的圖，其邊數(shù)為m，由于每條邊都有兩種選擇，即包含于或不包含于某個子圖，如果子圖每條邊都包含就是圖G，如果每條邊都不包含，就是空圖，故必有簡單圖G中所有不同的生成子圖(包括G和空圖)的個數(shù)是2m。

事實上,當圖包含某邊時,也就意味著包含了與該邊關聯(lián)的2個頂點,故不同的子集個數(shù)為

一個圖是子圖,它要滿足什么樣的條件呢?

定理2一個圖Q=(U,W)是子圖當且僅當它滿足:

1) degu≤2,?u∈U;

若一條途徑有正的長且起點和終點相同,則稱之為途徑為閉的,閉途徑也稱為回路。若一條閉跡的起點和內(nèi)部頂點互不相同,則稱之為圈。下面利用圈的概念和性質(zhì)來證明定理2。

證明必要性。若Q是子圖,由定義可知,在子圖中相關聯(lián)的頂點、邊在其導出子圖中對應的邊、頂點也相關聯(lián)。對?u∈U,若u關聯(lián)3條或3條以上的邊,則u在其導出子圖中對應的邊就要關聯(lián)3個或3個以上的頂點，矛盾,故u最多關聯(lián)2條邊，即

degu≤2,

?u∈U,

又因為Q的頂點數(shù)與邊數(shù)對應其導出子圖的邊數(shù)和頂點數(shù),故有

其中

p=|U|,

q=|W|。

充分性。若Q滿足條件1),則它的每一個分支只可能是1個圈、1條道路或者孤立點?，F(xiàn)構(gòu)造如下圖:考察Q的線圖[3]L,它由一些圈、道路、孤立點組成。令L中的端點與它中間1個與此端點無線連的點聯(lián)線,令L中的孤立點與它中間的2個與此孤立點無線連的點聯(lián)線,由條件2)可知，此聯(lián)法是可行的。這樣,我們得到1個圖G′(見圖2)。

圖2 子圖及其構(gòu)造圖

對于Q中每一個孤立點,在G′中找出一對不相鄰的點,在它們中間加1條線,并令這條線與這個孤立點對應,由條件2)可知,這種做法是可行的。如此得到1個圖G。

從上面的構(gòu)造步驟中,我們不難從它的對應關系中反過來構(gòu)造1個與Q同構(gòu)的G的子圖,故Q是子圖。

由此,我們證明了定理2的充要性,并用圖2進行了直觀的驗證,1個圖Q=(U,W)是子圖所必備的條件。

2 子圖與其導出子圖的同構(gòu)性

兩個無向單純圖G1=(V1，E1)，G2=(V2，E2)，若這兩個圖的頂點間有一一對應關系，且在這種對應關系下保持“相鄰”的關系不變，則這兩個圖稱為是同構(gòu)的，兩個圖同構(gòu)時，將相對應的點取相同的順序，則這兩個圖的相鄰矩陣實際上是一樣的。同構(gòu)的圖研究的是頂點之間的聯(lián)系，在圖論中是一樣的圖。

上面給出了子圖和其導出子圖的定義,根據(jù)圖的同構(gòu)[4]的定義得到定理3。

定理31個圖G與它的1個子圖同構(gòu)當且僅當它是一些圈的并。

證明充分性。由于連通圖同構(gòu)于它的線圖當且僅當它是1個圈,于是對于1個(不必連通的)圖要同構(gòu),G是2度正則的。由此可見,1個圖G與它的1個子圖同構(gòu),則它是一些圈的并。

必要性。若圖G與它的1個子圖同構(gòu),圖G中所有的點的度≥2,而它的子圖中所有點的度≤2,故必然是一些圈的并。

證畢。

下面通過反例說明兩個圖在它們的所有不同構(gòu)的子圖中存在一一對應的關系,且對應的子圖是同構(gòu)的,它們本身并不一定同構(gòu)。圖3中兩個圖G1,G2的所有的子圖(見圖4)的集合是相同的，但它們本身并不同構(gòu)。

通過反例,我們可以驗證圖和子圖同構(gòu)的前提條件。

圖3 不同構(gòu)的圖

圖4 G1,G2的子圖集

3 子圖與哈密爾頓圖的關系

經(jīng)過圖G中每個點僅有一次路(圈)稱為G的哈密爾頓路(圈)，存在哈密爾頓圈的圖稱為哈密爾頓圖，簡稱H圖，哈密爾頓路也簡稱為H路。下面就子圖和哈密爾頓圖的關系給出引理，進而得出定理4。

引理對每個子圖的每個圈[5],它的導出子圖G-v中必有1個長度相等的圈與之對應。

證明由定義可知，在H中相應的邊鄰接,則在G中對應的頂點也鄰接。故對H中圈上的每條邊,G中有1個頂點與之對應,邊鄰接對應頂點鄰接,則G中有1個長度相等的圈與它對應。

對于連通圖G,若G中存在經(jīng)過每條邊的閉跡(即Euler閉跡),則稱G為Euler圖。

定理41個圖G是哈密爾頓圖當且僅當它的子圖集{H}中有1個是歐拉圖。

證明充分性。若{H}中有1個是歐拉圖,則只有含所有邊的單圈情形,由引理1可知,G中有1個長度相等的圈與之對應,而子圖的邊集和其導出子圖的點集是一一對應的。故此圈含G中所有的頂點,則G是哈密爾頓圖。

必要性。若G是哈密爾頓圖,則它至少含有1個哈密爾頓圈[6]。我們來構(gòu)造1個圖P′,令G中哈密爾頓圈上的頂點集和邊集交換仍得到1個圈,令此圈上的所有邊組成P′的邊集,對G中除哈密爾頓圈上的邊外的每一條線,令P′中1個孤立點與之對應,這些孤立點加上新構(gòu)成的圈上的那些頂點組成P′的頂點集,則P′是G的1個子圖且為歐拉圖。

證畢。

與歐拉圖的情形相反，到目前為止，哈密爾頓圖仍然有很多尚未解決的問題，包括哈密爾頓圖的非平凡充要條件問題。關于H圖的研究仍是當前圖論中比較活躍的領域。希望將來，通過算法和編程的應用更好更快地解決圖論中的若干難題。

[1] 李慰萱.圖論[M].長沙:湖南科學技術出版社,1980:9-24.

[2] 哈拉里F.圖論[M].李慰萱,譯.上海:上?？茖W技術出版社,2008:75-98.

[3] 張先迪,李正良.圖論及其應用[M].北京:高等教育出版社,2005:1-20.

[4] 李修睦.圖論導引[M].武漢:華中工學院出版社,1982:203-244.

[5] 寧萬濤.圖中的度、邊和圈[D].蘭州：蘭州大學,2011:15-34.

[6] 張建高.一類路圖的哈密爾頓圈[J].重慶建筑工程學院學報,1991(3):1-6.

〔責任編輯：盧 蕊〕

Researchonsubgraphofsimplegraphanditsproperties

ZHOU Li-xia

(Accounting Department,Wuxi City College of Vocational Technology,Wuxi 214000,China)

This paper gives the definition of subgraph in graph theory,and obtains some properties of subgraph. This paper expounds the subgraph amd the isomorphism induced by the subgraph,and the relationship between subgraph and Hamilton graph. The proof and examples are shown.

graph theory; subgraph; isomorphism; Hamiltonian graph

2015-03-11

周麗霞(1976—),女,江蘇常熟人,講師,碩士,主要從事高職數(shù)學教學和統(tǒng)計研究。

O158

：C

：1008-8148(2015)03-0066-03