圖論試題浙師大

《圖論試題浙師大》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、思考練習(xí)第一章1對任意圖，證明。證：，故。2在一次聚會有個人參加，其中任意6個人中必有3個人互相認(rèn)識或有3個人互不認(rèn)識。舉例說明，將6個人改成5個人，結(jié)論不一定成立。證：構(gòu)圖如下：圖的頂點(diǎn)代表這6個人，兩個頂點(diǎn)相鄰當(dāng)且僅當(dāng)對應(yīng)的兩個人互相認(rèn)識。則對于圖中任意一個點(diǎn)或。不妨設(shè)及它的3個鄰點(diǎn)為。若中有任意兩個點(diǎn)，不妨設(shè)為，相鄰，則對應(yīng)的3個人互相認(rèn)識；否則，中任意兩個點(diǎn)不鄰，即它們對應(yīng)的3個人互不認(rèn)識。若這5個人構(gòu)成的圖是5圈時，就沒有3個人互相認(rèn)識或有3個人互不認(rèn)識。3給定圖畫出下列幾個子圖:(a)；(b);(c)解：(a)(b)(c)第二章1設(shè)是一個簡單圖，。證明：中存在

2、長度至少是的路。證：選取的一條最長路，則的所有鄰點(diǎn)都在中，所以，即中存在長度至少是的路。2證明：階簡單圖中每一對不相鄰的頂點(diǎn)度數(shù)之和至少是，則是連通圖。證：假設(shè)不連通，令、是的連通分支，對，有，與題設(shè)矛盾。故連通。3設(shè)是連通圖的一個回路，，證明仍連通。證：，中存在路，1、若，則是中的路；2、若，則是中的途徑，從而中存在路。故連通。4圖的一條邊稱為是割邊，若。證明的一條邊是割邊當(dāng)且僅當(dāng)不含在的任何回路上。證：不妨設(shè)連通，否則只要考慮中含的連通分支即可。必要性：假設(shè)在的某一回路上，則由習(xí)題2.13有連通，，與是割邊矛盾。故不在回路中。充分性：假設(shè)不是割邊，則仍連通，存在路，則

3、就是含的一個回路，與不在回路中矛盾。故是割邊。5證明：若是連通圖，則。證：若是連通圖，則。第三章1證明：簡單圖是樹當(dāng)且僅當(dāng)中存在一個頂點(diǎn)到中其余每個頂點(diǎn)有且只有一條路。證：必要性：由定理3.1.1立即可得。充分性：首先可見連通。否則，設(shè)有兩個連通分支、，且，則到中的頂點(diǎn)沒有路，與題設(shè)矛盾。其次，中無回路。否則，若有回路。由于連通，到上的點(diǎn)有路，且設(shè)與的第一個交點(diǎn)為，則到上除外其余點(diǎn)都至少有兩條路，又與題設(shè)矛盾。故是樹。2設(shè)圖有個連通分支，。證明含有回路。證：假設(shè)中不含回路。設(shè)的個連通分支為，則每個連通無回路，是樹。從而，與題設(shè)矛盾，故無回路。3是連通簡單圖的一條邊。證明在

4、的每個生成樹中當(dāng)且僅當(dāng)是的割邊。證：必要性：假設(shè)不是的割邊，即連通，有生成樹，與在的每個生成樹矛盾。故不是的割邊。充分性：假設(shè)存在一棵生成樹，使得不在中，從而連通，與是的割邊矛盾。故在的每個生成樹中。4設(shè)是至少有3個頂點(diǎn)的連通圖，證明中存在兩個頂點(diǎn)，使得仍是連通圖。證：是至少有3個頂點(diǎn)的連通圖，有生成樹，設(shè)是的懸掛點(diǎn)，則連通，是的生成子圖，從而連通。5Kruskal算法能否用來：1、在賦權(quán)連通圖中求最大權(quán)的生成樹？2、在非連通圖中求最小權(quán)的生成森林？如果可以，寫出算法。解：1、算法：1)在中選取邊，使盡可能的大；2)若已經(jīng)選定邊，則在中選取邊，使?jié)M足以下兩條：I.不含回路

5、；II.在滿足Ⅰ的前提下，使盡可能的大。3)當(dāng)2)不能繼續(xù)執(zhí)行時，停止。2、算法：1)在中選取邊，使盡可能的小；2)若已經(jīng)選定邊，則在中選取邊，使?jié)M足以下兩條：I.不含回路；II.在滿足Ⅰ的前提下，使盡可能的小。當(dāng)2)不能繼續(xù)執(zhí)行時，停止。第四章1設(shè)簡單圖是一個Euler圖。證明：中每個頂點(diǎn)，均有。證：設(shè)的每個連通分支為，則每個中至少有兩個點(diǎn)與鄰。否則的話，由于是Euler圖，中每個頂點(diǎn)的度數(shù)為偶數(shù)。若中只有一個點(diǎn)與鄰，設(shè)為，則中除了外其余點(diǎn)度數(shù)都是偶數(shù)，與推論1.3.2矛盾。故每個中至少有兩個點(diǎn)與鄰。從而。2設(shè)是連通圖，證明：是Euler圖當(dāng)且僅當(dāng)存在邊不交的回路，使：

6、。證：充分性：若中存在邊不交的回路，使：。則對中任意一個頂點(diǎn)，假設(shè)在個回路中，由回路的邊不相交性，有，是偶數(shù)。又連通，由定理4.1.1，有是Euler圖。必要性：對邊數(shù)用歸納法。當(dāng)邊數(shù)為1的時候，只能是一個頂點(diǎn)其邊為環(huán)的圖，顯然滿足條件。歸納假設(shè)邊數(shù)時成立，現(xiàn)在證明邊數(shù)等于時定理的必要性也成立。由于是Euler圖，無奇點(diǎn)且連通，故中每個頂點(diǎn)度至少是2。由定理2.1.1知中存在回路。現(xiàn)將中屬于的邊全刪去，再除去孤立點(diǎn)得圖。顯然的每個頂點(diǎn)度仍然是偶數(shù)，則的每個連通分支都是無奇點(diǎn)的連通圖，是Euler圖，且邊數(shù)，由歸納假設(shè)，中存在邊不交的回路，使：。則中存在邊不交的回路，使：。

7、3找一個有10個頂點(diǎn)的簡單圖，使的每一對不相鄰頂點(diǎn)，均有，而不是H—圖。解：令即可4設(shè)是連通圖中某一回路，若刪去中任意一條邊就得到的一條最長路。證明回路就是的H—回路。證：設(shè)的長度為。反證法，假設(shè)不是連通圖的H—回路，即連通，存在路，設(shè)與最后一個交點(diǎn)為。在中去掉與關(guān)聯(lián)的一條邊，再加上路，就可以得到一條長度至少是的路，與刪去中任意一條邊就得到的一條最長路矛盾。故，則含個點(diǎn)，是H—回路。5證明：若圍圓桌至少坐5個人，那么一定可以調(diào)整他們的座位，使得每個人的兩側(cè)都挨著兩個新鄰居。證：構(gòu)作圖：以人為頂點(diǎn)，兩個頂點(diǎn)相鄰當(dāng)且僅當(dāng)他們本來不