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

周麗霞

(無(wú)錫城市職業(yè)技術(shù)學(xué)院 會(huì)計(jì)系，江蘇 無(wú)錫 214000)

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

周麗霞

(無(wú)錫城市職業(yè)技術(shù)學(xué)院 會(huì)計(jì)系，江蘇 無(wú)錫 214000)

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

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

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

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

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

依定義可知,G的頂點(diǎn)集和邊集與H的邊集和頂點(diǎn)集是一一對(duì)應(yīng)的。

1 子圖的性質(zhì)

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

定理1圖G=(V,E)的子圖(指標(biāo)號(hào)圖)H的個(gè)數(shù)為

(1)

圖1 圖G及其3個(gè)子圖

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

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

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

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

1) degu≤2,?u∈U;

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

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

degu≤2,

?u∈U,

又因?yàn)镼的頂點(diǎn)數(shù)與邊數(shù)對(duì)應(yīng)其導(dǎo)出子圖的邊數(shù)和頂點(diǎn)數(shù),故有

其中

p=|U|,

q=|W|。

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

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

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

從上面的構(gòu)造步驟中,我們不難從它的對(duì)應(yīng)關(guān)系中反過來(lái)構(gòu)造1個(gè)與Q同構(gòu)的G的子圖,故Q是子圖。

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

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

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

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

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

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

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

證畢。

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

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

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

圖4 G1,G2的子圖集

3 子圖與哈密爾頓圖的關(guān)系

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

引理對(duì)每個(gè)子圖的每個(gè)圈[5],它的導(dǎo)出子圖G-v中必有1個(gè)長(zhǎng)度相等的圈與之對(duì)應(yīng)。

證明由定義可知，在H中相應(yīng)的邊鄰接,則在G中對(duì)應(yīng)的頂點(diǎn)也鄰接。故對(duì)H中圈上的每條邊,G中有1個(gè)頂點(diǎn)與之對(duì)應(yīng),邊鄰接對(duì)應(yīng)頂點(diǎn)鄰接,則G中有1個(gè)長(zhǎng)度相等的圈與它對(duì)應(yīng)。

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

定理41個(gè)圖G是哈密爾頓圖當(dāng)且僅當(dāng)它的子圖集{H}中有1個(gè)是歐拉圖。

證明充分性。若{H}中有1個(gè)是歐拉圖,則只有含所有邊的單圈情形,由引理1可知,G中有1個(gè)長(zhǎng)度相等的圈與之對(duì)應(yīng),而子圖的邊集和其導(dǎo)出子圖的點(diǎn)集是一一對(duì)應(yīng)的。故此圈含G中所有的頂點(diǎn),則G是哈密爾頓圖。

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

證畢。

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

[1] 李慰萱.圖論[M].長(zhǎng)沙:湖南科學(xué)技術(shù)出版社,1980:9-24.

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

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

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

[5] 寧萬(wàn)濤.圖中的度、邊和圈[D].蘭州：蘭州大學(xué),2011:15-34.

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

〔責(zé)任編輯：盧 蕊〕

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ù)學(xué)教學(xué)和統(tǒng)計(jì)研究。

O158

：C

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