哈工大集合論習(xí)題課-第五章-圖的基本概念習(xí)題課(學(xué)生)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第五章 圖的基本概念習(xí) 題 課 11. 畫出具有 6、8、10、2n個(gè)頂點(diǎn)的三次圖；是否有7個(gè)頂點(diǎn)的三次圖？2. 無向圖有21條邊，12個(gè)3度數(shù)頂點(diǎn)，其余頂點(diǎn)的度數(shù)均為2，求的頂點(diǎn)數(shù)。解：設(shè)圖的頂點(diǎn)為，根據(jù)握手定理：，有，得。3. 下列各無向圖中有幾個(gè)頂點(diǎn)？（1）16條邊，每個(gè)頂點(diǎn)的度為2；（2）21條邊，3個(gè)4度頂點(diǎn)，其余的都為3度數(shù)頂點(diǎn)；（3）24條邊，各頂點(diǎn)的度數(shù)相同。解： 設(shè)圖的頂點(diǎn)為，根據(jù)握手定理：（1），即；所以，即有16個(gè)頂點(diǎn)。（2），即，所以。（3）各點(diǎn)的度數(shù)為，則，即，于是 若，； 若，； 若，； 若，； 若，； 若，； 若，； 若，； 若，； 若，

2、。4設(shè)圖中9個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度不是5就是6。證明中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn)。證：由握手定理的推論可知，中5度頂點(diǎn)數(shù)只能是0，2，6，8五種情況，此時(shí)6度頂點(diǎn)數(shù)分別為9，7，5，3，1個(gè)。以上五種情況都滿足至少5個(gè)6度頂點(diǎn)或至少6個(gè)5度頂點(diǎn)的情況。5有個(gè)藥箱，若每?jī)蓚€(gè)藥箱里有一種相同的藥，而每種藥恰好放在兩個(gè)藥箱中，問藥箱里共有多少種藥？就是求一個(gè)完全圖的邊數(shù)6.設(shè)是有個(gè)頂點(diǎn)，條邊的無向圖，各頂點(diǎn)的度數(shù)均為3。則（1）若，證明同構(gòu)意義下唯一，并求；（2）若，證明在同構(gòu)的意義下不唯一。分析：在圖論中，對(duì)于簡(jiǎn)單無向圖和簡(jiǎn)單有向圖，若涉及到邊與頂點(diǎn)的問題，握手定理是十分有用的。解：（1

3、）由于各頂點(diǎn)的度數(shù)均為3，現(xiàn)在有個(gè)頂點(diǎn)，條邊，所以由握手定理知：，即，故；又，故，則。即，此時(shí)所得的無向圖如圖1所示，該圖是4個(gè)頂點(diǎn)的簡(jiǎn)單無向圖中邊最多的圖，即為無向完全圖。對(duì)于4個(gè)頂點(diǎn)的完全圖，在同構(gòu)意義下，4個(gè)頂點(diǎn)的完全圖是唯一的。（2）若，由握手定理：，即。故，此時(shí)有，且每個(gè)頂點(diǎn)的度數(shù)為3；此時(shí)對(duì)于簡(jiǎn)單無向圖，6個(gè)頂點(diǎn)，9條邊及每個(gè)度數(shù)為3的有如圖2所示兩個(gè)非同構(gòu)的圖；與是非同構(gòu)的圖，所以，度數(shù)為3的無向圖在同構(gòu)的意義下是不唯一的。 （a） (b)圖1 圖27.已知階簡(jiǎn)單圖中有條邊，各頂點(diǎn)的度數(shù)均為3，又，試畫出滿足條件的所有不同構(gòu)的。解：由握手定理：，又，即。故，即，。此時(shí)有，且每個(gè)頂

4、點(diǎn)的度數(shù)都為3，則不同構(gòu)的無向圖有兩個(gè)，如圖3所示。 圖389個(gè)學(xué)生，每個(gè)學(xué)生向其他學(xué)生中的3個(gè)學(xué)生各送一張賀年卡。確定能否使每個(gè)學(xué)生收到的卡均來自其送過卡的相同人？為什么？解：否，因?yàn)椴淮嬖?（奇數(shù)）個(gè)頂點(diǎn)的3正則圖習(xí)題課2例3設(shè)為正整數(shù)，則（1）為何值時(shí)，無向完全圖是歐拉圖？為何值時(shí)為半歐拉圖？（2）為何值時(shí)為歐拉圖？ （3）為何值時(shí)為哈密整圖？（3）為何值時(shí)，輪圖為歐拉圖？證：（1）一般情況下，不考慮無向圖。因此因?yàn)楦黜旤c(diǎn)的度均為，若使為歐拉圖，必為偶數(shù)，因而必為奇數(shù)。即為奇數(shù)時(shí)，完全圖是歐拉圖。若或?yàn)槠鏀?shù)時(shí)，是半歐拉圖。（2）當(dāng)均為偶數(shù)時(shí)，為歐拉圖。（3）當(dāng)時(shí)，為哈密整圖。（4）設(shè)為輪

5、圖，在中，有個(gè)頂點(diǎn)的度為3，因而對(duì)于任意取值，輪圖都不是歐拉圖。例1 判斷圖5所示的圖是否為哈密頓圖，若是寫出哈密頓回路，否則證明其不是哈密頓圖。 (a) (b) 圖3 圖4 例2 給出一個(gè)10個(gè)頂點(diǎn)的非哈密頓圖的例子，使得每一對(duì)不鄰接的頂點(diǎn)和，均有。例3 試求中不同的哈密頓回路的個(gè)數(shù)。例4 (1) 證明具有奇數(shù)頂點(diǎn)的偶圖不是哈密頓圖；用此結(jié)論證明圖8所示的圖不是哈密頓圖。(2) 完全偶圖為哈密頓圖的充分必要條件是什么？證：(1) 設(shè)是一個(gè)具有奇數(shù)頂點(diǎn)的偶圖，則的頂點(diǎn)集有一個(gè)二劃分，即且有。 不妨設(shè)，則有。由哈密頓圖的必要條件可知：不是哈密頓圖。 題中所給的圖中無奇數(shù)長(zhǎng)的回路，因而此圖是偶圖。

6、而且此圖中有13個(gè)頂點(diǎn)，因此它不是哈密頓圖。(2) 若，有(1)可知不是哈密頓圖；若，同理有不是哈密頓圖。故是哈密頓圖時(shí)只有，即。若，則，由定理知：是哈密頓圖。例5 菱形12面體的表面上有無哈密頓回路？例6設(shè)是連通圖且頂點(diǎn)數(shù)為，最小度數(shù)為，則中有一長(zhǎng)至少為的路。分析: 采用最長(zhǎng)路法，設(shè)連通圖的最長(zhǎng)路為且。再看這條路的端點(diǎn)，端點(diǎn)只能與上的頂點(diǎn)相鄰，這樣就可以構(gòu)成一個(gè)回路，對(duì)于回路外的頂點(diǎn)，因?yàn)槿耘c此回路上的某些頂點(diǎn)相鄰，所以可以把這個(gè)頂點(diǎn)連到回路上，然后再打開回路，顯然這時(shí)有一條路比假設(shè)時(shí)的路更長(zhǎng)了，所以假設(shè)不成立。證：假設(shè)中的最長(zhǎng)路為：，其長(zhǎng)度為。因?yàn)椋?，所以存在，使 與在中相鄰，得一長(zhǎng)為的

7、回路：。又因?yàn)檫B通，且的頂點(diǎn)數(shù)，故存在與回路上相鄰，則把回路在處斷開，并把連入回路中，得到一條長(zhǎng)為的路，矛盾。所以中有一長(zhǎng)至少為的路。例7 證明：彼德森()圖不是哈密頓圖。 例8 某工廠生產(chǎn)由6種不同顏色的紗織成的雙色布。雙色布中，每一種顏色至少和其他3種顏色搭配。證明：可以挑出3種不同的雙色布，它們含有所有6種顏色。證：用6個(gè)不同的點(diǎn)分別表示6種不同顏色的紗，兩個(gè)點(diǎn)間聯(lián)一條線當(dāng)且僅當(dāng)用這兩點(diǎn)所表示的兩種不同顏色的紗織成一種雙色布。于是，我們得到一個(gè)有6個(gè)點(diǎn)的圖G。由于每種顏色的紗至少和3種其他顏色的紗搭配，所以G的每個(gè)頂點(diǎn)的度至少是3。于是，由定理1，G有哈密頓回路。回路上有6條邊，對(duì)應(yīng)了6

8、種不同的雙色布。間隔取出3條邊，它們包含了全部6種顏色。與例8等價(jià)的例題：例9 今要將6個(gè)人分成3組（每組2個(gè)人）去完成3項(xiàng)任務(wù)，已知每個(gè)人至少與其余5個(gè)人中的3個(gè)人能相互合作，問：(1)能否使得每組2個(gè)人都能相互合作？(2)你能給出集中方案？（兩種）例10 某公司來了9名新雇員，工作時(shí)間不能互相交談。為了盡快互相了解，他們決定利用每天吃午飯時(shí)間相互交談。于是，每天在吃午飯時(shí)他們圍在一張圓桌旁坐下，他們是這樣安排的，每一次每人的左、右鄰均與以前的人不同。問這樣的安排法能堅(jiān)持多久？解：平面上9個(gè)互不相同的點(diǎn)分別代表9個(gè)新雇員。因?yàn)槊總€(gè)人都可以為其他每個(gè)人的左或右鄰，所以用兩點(diǎn)的聯(lián)線表示相應(yīng)的兩個(gè)

9、人互為左右鄰。于是得到了有9個(gè)頂點(diǎn)的完全圖K9。于是，我們的問題中的一種坐法就是K9的一個(gè)哈密頓回路。由于每次的安排中，每人的左、右鄰均與以前的人不同，所以我們的問題就是求K9中有多少個(gè)兩兩無公共邊的哈密頓回路。由圖1.6.5不難發(fā)現(xiàn)，K9中恰有4個(gè)兩兩無公共邊的哈密頓回路。它們是：，。于是，他們的這種安排法僅能維持4天。例10可推廣為n個(gè)雇員的一般情況問題。這時(shí)，當(dāng)n為奇數(shù)時(shí)，這種安排法僅能維持(n-1)/2天；當(dāng)n為偶數(shù)時(shí)，這種安排法僅能維持(n-2)/2天。習(xí)題課3例2設(shè)，其中為正整數(shù)，。若存在個(gè)頂點(diǎn)的簡(jiǎn)單圖，使得頂點(diǎn)的度為，則稱是可圖解的。下面給出的各序列中哪些是可圖解的？哪些不是，為

10、什么？（1） （1，1，1，2，3）； （6） （1，3，3，3）； （2） （0，1，1，2，3，3）； （7） （2，3，3，4，5，6）； （3） （3，3，3，3）； （8） （1，3，3，4，5，6，6）； （4） （2，3，3，4，4，5）； （9） （2，2，4）； （5） （2，3，4，4，5）； （10） （1，2，2，3，4，5）。解：（1），（2），（3）全是可圖解的，它們對(duì)應(yīng)的圖分別如圖3中所示；其余的各序列都不是可圖解的。在（4），（7），（10）中均有奇數(shù)個(gè)奇度頂點(diǎn)，根據(jù)握手定理的推論，它們自然都不是可圖解的。另外在階簡(jiǎn)單圖中，每個(gè)頂點(diǎn)的度至多為，因而（5）和（9）

11、均不可圖解。若（6）是可圖解的，則設(shè)，因?yàn)榈亩榷际?，因而要求與之間有邊關(guān)聯(lián)，但因的度為1，這是不可能的，所以（6）也是不可圖解的。在（8）中，因而每個(gè)頂點(diǎn)至多6度。若（8）是可圖解的，設(shè)，因而均應(yīng)與相鄰，這也是不可能的，因而（8）也不可圖解。 (a) (b) (c)圖3例3 至少要?jiǎng)h除多少條邊，才能使不連通且其中有一個(gè)連通分支恰有個(gè)頂點(diǎn)？簡(jiǎn)述理由。 證：要使刪除邊后的圖邊數(shù)最多，則刪除的邊最少。滿足有一個(gè)連通分支恰有個(gè)頂點(diǎn)的圖的最大邊數(shù)為： 則至少應(yīng)該刪除的邊數(shù)為： 。例4若是一個(gè)恰有兩個(gè)奇度頂點(diǎn)和的無向圖，則連通連通。證： 顯然成立。 假設(shè)不連通，則有個(gè)分支：，由題意不在一個(gè)分支上，于是含

12、有的頂點(diǎn)的分支只有一個(gè)奇度數(shù)頂點(diǎn)與握手定理的推論矛盾。于是假設(shè)不成立，即是連通的。例5設(shè)為階簡(jiǎn)單無向圖，且為奇數(shù)，和的補(bǔ)圖中度數(shù)為奇數(shù)的頂點(diǎn)的個(gè)數(shù)是否一定相等？試證明你的結(jié)論。解：一定相等。因?yàn)闉槠鏀?shù)，則對(duì)于奇數(shù)個(gè)頂點(diǎn)的階無向完全圖，每個(gè)頂點(diǎn)的度數(shù)必為偶數(shù)。若的奇度數(shù)頂點(diǎn)為個(gè)，則對(duì)應(yīng)補(bǔ)圖在這個(gè)頂點(diǎn)的度數(shù)必為（偶數(shù)奇數(shù)）奇數(shù)。另外，對(duì)于中度數(shù)為偶數(shù)的頂點(diǎn)，其在補(bǔ)圖中，這些頂點(diǎn)的度數(shù)仍為（偶數(shù)偶數(shù)）偶數(shù)。所以，中度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)與中度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)相同。例6證明：完全圖中至少存在彼此無公共邊的兩條哈密頓回路和一條哈密頓路？證：在中，由定理可知，必有一條哈密頓回路；令為中刪除中全部邊之后的圖

13、，則中每個(gè)頂點(diǎn)的度均為，故仍為哈密頓圖，因而存在中的哈密頓回路，顯然與無公共邊。再設(shè)為中刪除中的全部邊后所得圖，則每個(gè)頂點(diǎn)的度均為。又由定理可知為半哈密頓圖，因而中存在哈密頓路。設(shè)為中的一條哈密頓路，顯然無公共邊。例7 已知7個(gè)人中，會(huì)講英語(yǔ)；會(huì)講英語(yǔ)和漢語(yǔ)；會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)；會(huì)講漢語(yǔ)和日語(yǔ)；會(huì)講意大利語(yǔ)和德語(yǔ)；會(huì)講俄語(yǔ)、日語(yǔ)和法語(yǔ)；會(huì)講德語(yǔ)和法語(yǔ)。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？證：用7個(gè)頂點(diǎn)代表7個(gè)人，若兩人能交談（會(huì)講同一種語(yǔ)言），就在代表他們的頂點(diǎn)之間連一條無向邊，所得無向圖如圖4所示，此圖中存在哈密頓回路：（如圖4粗邊所示），于是按圖4所示的順序

14、安排座位即可。 (a)(b) (c)圖4例8將無向完全圖的邊隨意地涂上紅色或綠色，證明：無論何種涂法，總存在紅色的或綠色的。證：設(shè)的頂點(diǎn)為。給的邊任意用紅、綠色涂上，由鴿巢原理可知，由引出的5條邊中存在3條涂同種顏色的邊。不妨設(shè)存在3條紅色的邊，又不妨設(shè)這3條邊的另一個(gè)端點(diǎn)分別是（也可重新給頂點(diǎn)排序）。 若構(gòu)成的中的邊再有一條紅色邊。比如（）著的是紅色，構(gòu)成的三角形為紅色的。若構(gòu)成的的邊全是綠色的邊，則存在綠色邊的。這就證明了我們的結(jié)論。例9已知9個(gè)人，其中和兩個(gè)人握過手，各和3個(gè)人握過手，和4個(gè)人握過手，各和5個(gè)人握過手，和6個(gè)人握過手。證明這9個(gè)人中一定可以找出3個(gè)人互相握過手。分析：以為

15、頂點(diǎn)，握過手就連一條邊，得到一個(gè)無向圖。只要證明中有三角形子圖，即可得一定有3個(gè)人互相握過手。 證：設(shè)為圖的9個(gè)頂點(diǎn)，握過手就連一條邊，于是得到圖。根據(jù)題意有：，。與相鄰的點(diǎn)有6個(gè)，其中必有一點(diǎn)為之一，因此有。與相鄰的其余5個(gè)點(diǎn)中必存在一點(diǎn)與相鄰如圖4所示，否則有，矛盾。由此三個(gè)人互相握過手。 圖5 圖6 圖7例10如圖6所示的圖是哈密頓圖。試證明：若圖中的哈密頓回路中含邊，則它一定同時(shí)也含。證：設(shè)為圖中一條哈密頓回路，在中，假設(shè)不在中，要推出矛盾。圖中除外，與關(guān)聯(lián)的邊各有兩條，而只能各有一條邊在中，由對(duì)稱性設(shè)在中（不可能或同時(shí)在中）。這就相當(dāng)于在圖7中所示的圖中求一條哈密頓回路，而此時(shí)，均為

16、圖中割點(diǎn)，這是不可能的，因而必在中。例11某次會(huì)議有20人參加，其中每個(gè)人都至少有10個(gè)朋友，這20人圍一圓桌入席，要想使與每個(gè)人相鄰的兩位都是朋友是否可能？根據(jù)什么？證：可能。依題意，若用頂點(diǎn)代表人，兩人是朋友時(shí)相應(yīng)頂點(diǎn)間連一條邊，則得到一個(gè)無向圖，該題轉(zhuǎn)化為求哈密頓回路問題。由于對(duì)任意,有，因而。 又定理可知，為哈密頓圖，中存在哈密頓回路，按此回路各點(diǎn)位置入席即為所求。例12 設(shè)是一個(gè)個(gè)頂點(diǎn)的連通圖。和是的兩個(gè)不鄰接的頂點(diǎn),并且。證明：是哈密頓圖是哈密頓圖。證明： 顯然成立。 假設(shè)不是哈密頓圖，則由題意知，在中必有一條從到的哈密頓路。不妨設(shè)此路為，令，則在中與鄰接的頂點(diǎn)為，其中。此時(shí)頂點(diǎn)不

17、能與頂點(diǎn)鄰接。否則有哈密頓回路，因此至少與中的個(gè)頂點(diǎn)不鄰接。于是，從而，即，與題設(shè)矛盾。故假設(shè)不成立，因此是哈密頓圖。例13設(shè)為階無向簡(jiǎn)單圖，已知，證明中存在長(zhǎng)度為偶數(shù)的回路。證：對(duì)無向簡(jiǎn)單圖的頂點(diǎn)個(gè)數(shù)進(jìn)行數(shù)學(xué)歸納證明：當(dāng)時(shí)，為完全圖，結(jié)論顯然成立，所得的回路的長(zhǎng)度為4。設(shè)當(dāng)時(shí)結(jié)論成立，長(zhǎng)度為偶數(shù)的回路為。則當(dāng)時(shí)，長(zhǎng)度為偶數(shù)的回路也在頂點(diǎn)數(shù)為的圖中，則結(jié)論成立。例14設(shè)是個(gè)頂點(diǎn)的簡(jiǎn)單無向圖，設(shè)中最長(zhǎng)的路的長(zhǎng)度為，起點(diǎn)與終點(diǎn)分別為,，而且。證明：中必有與不完全相同但長(zhǎng)度也為的路。證：設(shè)圖的最長(zhǎng)的路為：，其長(zhǎng)度為。因?yàn)樽铋L(zhǎng)的路，所以與,相鄰的頂點(diǎn)必在上。若和相鄰，則構(gòu)成一個(gè)回路，回路長(zhǎng)為；若和不相鄰，設(shè)與相鄰的頂點(diǎn)為，其中，則必與某個(gè)鄰接。否則，至多與最長(zhǎng)路上其余的頂點(diǎn)鄰接，所以這是不可能的。于是是中的一個(gè)回路，此回路長(zhǎng)度為。去掉這個(gè)回路的任意一條邊，便得到一條相應(yīng)的最長(zhǎng)的路，所以對(duì)于這個(gè)回路有個(gè)不同的最長(zhǎng)的路且。故中必有與不完全相同，但長(zhǎng)度也為的路。例15 一個(gè)一維立方體是這樣的無向圖：頂點(diǎn)集為長(zhǎng)為的所有字符串之集，兩個(gè)頂點(diǎn)鄰接當(dāng)且僅當(dāng)相應(yīng)