4連通圖的可去邊與4連通圖的構(gòu)造.pdf

1、廣西大學(xué)碩士學(xué)位論文4連通圖的可去邊與4連通圖的構(gòu)造姓名：尹建華申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：黃國(guó)勛19970617構(gòu)比3連通圖結(jié)構(gòu)復(fù)雜得多。本文引進(jìn)加點(diǎn)去邊和擴(kuò)點(diǎn)運(yùn)算，其定義見(jiàn)后。并得到；G是4連通圖當(dāng)且僅當(dāng)G是一個(gè)2循環(huán)圖或G是從一個(gè)2循環(huán)圖重復(fù)使用下四種運(yùn)算推得的圖：(1)加邊，(z)拆點(diǎn)，(3)加點(diǎn)去邊，(4)擴(kuò)點(diǎn)。設(shè)G是4連通圖，e—zy∈E(G)，S￡V(G—e)且15I=3，如果G—S—e恰有2個(gè)分支A和日，使

2、得I以I，lBl≥2。則稱(e，S)是G的分離對(duì)；(e，s；A，B)是G的一個(gè)分離分解。G／xy表示G收縮邊zy后得到的圖，若G／a：y仍4連通，則稱zy是可收縮邊，否則zy為不可收縮邊。G的可收縮邊的壘體記為Ec(G)，并記H(G)一E。(G)UE一(G)。2主要定理及其證明定理l設(shè)G是4連通圖1Gl≥7，則c=：；y∈E(G)是不可去邊的充分必要條件是存在s￡礦(G)，ISl=3，使得G～e—S恰有2個(gè)分支A和B，并且I^I≥2，l

3、占|≥2。證明必要性。設(shè)一是不可去邊，即Gee非4連通因1GI≥7，故IG@e1≥5所以存在S￡V(Gee)￡V(G)，』SJ=3使得(G@e)一s不連通，從而也必然使得G—e—S不連通。因?yàn)镚是4連通的，IsI=3，所以G—e—S恰有2個(gè)分支，設(shè)為A和B并可設(shè)工∈A，y∈B。如果I以l=1，即有A=z)，并且de(工)=3。這表明上毛V(G@e)，從而(Gee)一S是連通的，矛盾。因此只有jAI≥2。同理I丑I≥2，充分性。設(shè)存在S￡

4、V(G)，IS『=3使得G一￡一S恰有z個(gè)分支4和占，14I≥2『引≥2，且z∈A，y∈B。根據(jù)G@f—G@xy的定義知y(Gexy)Uz，y1=V(G)，所以Goe—S必有2個(gè)分支且7∈A，B7￡丑，且A’Uz)=A，B’Uy=B。因?yàn)镮AI≥2，lBI≥2，所以IA’I≥l，『B‘l≥1。這表明s是G@e的3點(diǎn)割，故e是不可去邊。定理z設(shè)G是4連通圖，IGl≥8，(e，S；^，丑)是G的一個(gè)分離分解，其中P=zyz∈A，y∈B。如果

5、lA『≥3，則對(duì)于任意的“∈S，f=z“是G的可擊邊。證明設(shè)廠=z“是不可去邊，則存在G的一個(gè)分離分解(，，T；C，D)，z∈C，“∈D；令x，=(Snc)U(5N丁)U(An丁)，X。；(ANr)U(SNT)U(5ND)，xa=(SnD)U(5N丁)U(Bn丁)，x=(BN)U(SnT)U(sNC)，在下面的證明過(guò)程中，將多次用到：e=xy是A與日之間唯一的邊，f—z“是C與D之間唯一邊。(1)『xI≥2。因?yàn)閤。Ub，“)把G分離為