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

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

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

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

4、點的度數(shù)都為3，則不同構的無向圖有兩個，如圖3所示。 圖389個學生，每個學生向其他學生中的3個學生各送一張賀年卡。確定能否使每個學生收到的卡均來自其送過卡的相同人？為什么？解：否，因為不存在9（奇數(shù)）個頂點的3正則圖習題課2例3設為正整數(shù)，則（1）為何值時，無向完全圖是歐拉圖？為何值時為半歐拉圖？（2）為何值時為歐拉圖？ （3）為何值時為哈密整圖？（3）為何值時，輪圖為歐拉圖？證：（1）一般情況下，不考慮無向圖。因此因為各頂點的度均為，若使為歐拉圖，必為偶數(shù)，因而必為奇數(shù)。即為奇數(shù)時，完全圖是歐拉圖。若或為奇數(shù)時，是半歐拉圖。（2）當均為偶數(shù)時，為歐拉圖。（3）當時，為哈密整圖。（4）設為輪

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

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

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

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

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

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）全是可圖解的，它們對應的圖分別如圖3中所示；其余的各序列都不是可圖解的。在（4），（7），（10）中均有奇數(shù)個奇度頂點，根據(jù)握手定理的推論，它們自然都不是可圖解的。另外在階簡單圖中，每個頂點的度至多為，因而（5）和（9）

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

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

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

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

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

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

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