哈工大圖論習(xí)題

1、2作者:日期:3 / 7第一章習(xí)題I.畫出具有 4 個(gè)頂點(diǎn)的所有無向圖(同構(gòu)的只算一個(gè))。2畫出具有 3 個(gè)頂點(diǎn)的所有有向圖(同構(gòu)的只算一個(gè))。3畫出具有 4 個(gè)、6 個(gè)、8 個(gè)頂點(diǎn)的三次圖。4某次宴會(huì)上，許多人互相握手。證明：握過奇數(shù)次手的人數(shù)為偶數(shù)(注意，0 是偶數(shù))。5證明：哥尼斯堡七橋問題無解。6.設(shè) u 與 v 是圖 G 的兩個(gè)不同頂點(diǎn)。 若 u 與 v 間有兩條不同的通道(跡)， 則 G 中是否 有回路？7. 證明：一個(gè)連通的(p , q)圖中 q p-1。&設(shè) G 是一個(gè)(p , q)圖，3(G) p/2，試證 G 是連通的。9. 證明：在一個(gè)連通圖中，兩條最長的路有一個(gè)

2、公共的頂點(diǎn)。10.在一個(gè)有 n 個(gè)人的宴會(huì)上，每個(gè)人至少有 m 個(gè)朋友(2 m 2，貝UG 包含長至少是3(G)+1的回路。13. 設(shè) G 是一個(gè)(p , q)圖，證明：(a)q p，則 G 中有回路；(b) 若 q p+4,則 G 包含兩個(gè)邊不重的回路。14. 證明：若圖 G 不是連通圖，則 G 是連通圖。15. 設(shè) G 是個(gè)(p , q)圖，試證：(a)3(G)3(GC) 3。18. 給出一個(gè) 10 個(gè)頂點(diǎn)的非哈密頓圖的例子，使得每一對不鄰接的頂點(diǎn)u 和 v,均有degu+degv 919. 試求 Kp 中不同的哈密頓回路的個(gè)數(shù)。20. 試證：圖四中的圖不是哈密頓圖。21. 完全偶圖 Km

3、 n 為哈密頓圖的充分必要條件是什么？22 .菱形 12 面體的表面上有無哈密頓回路？23. 設(shè) G 是一個(gè) p(p 3)個(gè)頂點(diǎn)的圖。u 和 v 是 G 的兩個(gè)不鄰接的頂點(diǎn)， 并且 degu+degv p。證明：G 是哈密頓圖當(dāng)且僅當(dāng)G+uv 是哈密頓圖。24.設(shè) G 是一個(gè)有 p 個(gè)頂點(diǎn)的圖。證明：若 p23(G)，則有長至少為 23(G)的路。25. 證明具有奇數(shù)頂點(diǎn)的偶圖不是哈密頓圖。26. 證明：若 p 為奇數(shù)，則 Kp 中有(p-1)/2 個(gè)兩兩無公共邊的哈密頓回路。28.中國郵路問題：一個(gè)郵遞員從郵局出發(fā)投遞信件，然后返回郵局。若他必須至少一次走過他所管轄范圍內(nèi)的每條街道，那么如何

4、選擇投遞路線，以便走盡可能少的路程。這個(gè)問題是我國數(shù)學(xué)家管梅谷于1962 年首先提出的，國外稱之為中國郵路問題。(1) 試將中國郵路問題用圖論述語描述出來。(2) 中國郵路問題、歐拉圖問題及最短路問題之間有何聯(lián)系。4 / 7第二章習(xí)題I.畫出具有 4 個(gè)頂點(diǎn)的所有無向圖(同構(gòu)的只算一個(gè))。2畫出具有 3 個(gè)頂點(diǎn)的所有有向圖(同構(gòu)的只算一個(gè))。3畫出具有 4 個(gè)、6 個(gè)、8 個(gè)頂點(diǎn)的三次圖。4某次宴會(huì)上，許多人互相握手。證明：握過奇數(shù)次手的人數(shù)為偶數(shù)(注意，0 是偶數(shù))。5證明：哥尼斯堡七橋問題無解。6.設(shè) u 與 v 是圖 G 的兩個(gè)不同頂點(diǎn)。 若 u 與 v 間有兩條不同的通道(跡)， 則

5、G 中是否 有回路？7. 證明：一個(gè)連通的(p , q)圖中 q p-1。&設(shè) G 是一個(gè)(p , q)圖，3(G) p/2，試證 G 是連通的。9. 證明：在一個(gè)連通圖中，兩條最長的路有一個(gè)公共的頂點(diǎn)。10.在一個(gè)有 n 個(gè)人的宴會(huì)上，每個(gè)人至少有 m 個(gè)朋友(2 m 2，貝UG 包含長至少是3(G)+1的回路。13. 設(shè) G 是一個(gè)(p , q)圖，證明：(a)q p，則 G 中有回路；(b) 若 q p+4,則 G 包含兩個(gè)邊不重的回路。14. 證明：若圖 G 不是連通圖，則 G 是連通圖。15. 設(shè) G 是個(gè)(p , q)圖，試證：(a)3(G)3(GC) 3。18. 在圖 1

6、.4.5 中，一只車從位置 A 出發(fā)，在半張棋盤上走，每步走一格，走了若干步 后到了位置 B。證明：至少有一個(gè)格點(diǎn)，沒有車走過，或被走過不至一次。19. 給出一個(gè) 10 個(gè)頂點(diǎn)的非哈密頓圖的例子，使得每一對不鄰接的頂點(diǎn)u 和 V，均有degu+degv 920. 試求 Kp 中不同的哈密頓回路的個(gè)數(shù)。21. 完全偶圖 Km n 為哈密頓圖的充分必要條件是什么？22 .菱形 12 面體的表面上有無哈密頓回路？23.設(shè)G是一個(gè)p(p 3)個(gè)頂點(diǎn)的圖。u 和 v 是 G 的兩個(gè)不鄰接的頂點(diǎn)，并且 degu+degv p 證明：G 是哈密頓圖當(dāng)且僅當(dāng) G+uv 是哈密頓圖。24.設(shè) G 是一個(gè)有 p

7、個(gè)頂點(diǎn)的圖。證明：若 p23(G)，則有長至少為 23(G)的路。25.證明具有奇數(shù)頂點(diǎn)的偶圖不是哈密頓圖。26. 證明：若 p 為奇數(shù)，則 Kp 中有(p-1)/2 個(gè)兩兩無公共邊的哈密頓回路。27.中國郵路問題： 一個(gè)郵遞員從郵局出發(fā)投遞信件，然后返回郵局。若他必須至少一次走過他所管轄范圍內(nèi)的每條街道，那么如何選擇投遞路線，以便走盡可能少的路程。這個(gè)問題是我國數(shù)學(xué)家管梅谷于1962 年首先提出的，國外稱之為中國郵路問題。(1) 試將中國郵路問題用圖論述語描述出來。(2) 中國郵路問題、歐拉圖問題及最短路問題之間有何聯(lián)系。5 / 7第三章習(xí)題I.分別畫出具有 4、5、6 個(gè)頂點(diǎn)的所有樹(同構(gòu)

8、的只算一個(gè))。2 證明：每個(gè)非平凡樹是偶圖。3. 設(shè) G 是一棵樹且 (G) k，證明：G 中至少有 k 個(gè)度為 1 的頂點(diǎn)。4. 令 G 是一個(gè)有 p 個(gè)頂點(diǎn)，k 個(gè)支的森林，證明：G 有 p-k 條邊。5. 設(shè) T 是一個(gè) k+1 個(gè)頂點(diǎn)的樹。證明：若圖 G 的最小度3(G) k,則 G 有一個(gè)同構(gòu)于 T 的子圖。6.棵樹 T 有 n2個(gè)度為 2 的頂點(diǎn)，n3個(gè)度為 3 的頂點(diǎn)，加個(gè)度為 k 的頂點(diǎn)，貝UT 有多少個(gè)度為 1 的頂點(diǎn)？7.設(shè) G 是一個(gè)連通圖。試證：G的子圖G 是 G 的某個(gè)生成樹的子圖，當(dāng)且僅當(dāng)G1沒有回路。&證明：連通圖的任一條邊必是它的某個(gè)生成樹的一條邊。9.

9、設(shè) G 是一個(gè)邊帶權(quán)連通圖，G 的每條邊均在 G 的某個(gè)回路上。試證：若 G 的邊 e 的 權(quán)大于 G 的任一其他邊的權(quán)，則 e 不在 G 的任一最小生成樹中。10. 設(shè) G=(V, E, w)是一個(gè)邊帶權(quán)連通圖，對任意 x E, w(x) 0。試證：G 的一個(gè)生 成樹 T是 G 的最小生成樹，當(dāng)且僅當(dāng)時(shí) G 的任一與 T 的距離為 1 的生成樹 T滿足條件：在 T 中而不在 T中的邊 e 的權(quán) w(e)不大于在中而不在 T 中的邊 e的權(quán) w(e )。II.某鎮(zhèn)有 1000 人，每天他們中的每個(gè)人把昨天聽到的消息告訴他認(rèn)識(shí)的人。已知任何消息，只要鎮(zhèn)上有人知道，都會(huì)經(jīng)這種方式逐漸地為全鎮(zhèn)上所有

10、人知道。試證：可選出90個(gè)居民代表使得只要同時(shí)向他們傳達(dá)某一消息，經(jīng)10 天就會(huì)為全鎮(zhèn)居民知道。12. P 個(gè)頂點(diǎn)的圖中，最多有多少個(gè)割點(diǎn)？13.證明：恰有兩個(gè)頂點(diǎn)不是割點(diǎn)的連通圖是一條路。14.證明：有一座橋的三次圖中至少有10 個(gè)頂點(diǎn)。15 設(shè) v 是圖 G 的一個(gè)割點(diǎn)，證明 v 不是 G 的補(bǔ)圖 G 的割點(diǎn)。16. 設(shè) v 是圖 G 的一個(gè)頂點(diǎn)。證明：v 是 G 的割點(diǎn)當(dāng)且僅當(dāng)有鄰接 v 的兩個(gè)不同的頂點(diǎn) u 和 W,使得 v 在 U 與 w 間的每一條路上。17. 割點(diǎn)的連通圖是否一定不是歐拉圖？是否一定不是哈密頓圖？有橋的連通圖是否 一定不歐拉圖和哈密頓圖。18. L 是連通圖 G

11、的一個(gè)回路，x 和 y 是 L 上的兩條邊。證明：G 有個(gè)割集 S 使得 x 與 y恰好是 L 與 S 的公共邊。第四章習(xí)題1.設(shè) G 是一個(gè)有 p 個(gè)頂點(diǎn)的圖，3(G) (p+k)-1)/2，試證：G 是 k-連通的。2. 若(p , q)圖 G 是 k-邊連通的，試證：q kp/2。3.設(shè) G 是 k-邊連通的，k0, E 是 G 的 k 條邊的集合。證明：G-E的支數(shù)小于或等于 2。4. 構(gòu)造一個(gè)(p , q)圖 G 使得3(G)=p/2-1，入(G)0。構(gòu)造一個(gè) k-連通圖 G,以及 G 的 k 個(gè)頂點(diǎn)之集 V,使得 G-V的支數(shù)大于 2。6. G 是一個(gè)三次正則圖，試證：x(G)=入

12、(G)。7. 設(shè) r 2, G 是 r 正則圖。證明：入(G) r/2。6 / 7&構(gòu)造一個(gè)圖 G,使得x(G)=3，入(G)=4 ,3(G)=5。9.證明：圖 G 是 2-邊連通的當(dāng)且僅當(dāng)任兩個(gè)不同頂點(diǎn)間至少有兩條邊不重路。7 / 710.設(shè) G=(V, E)是 2-邊連通圖，X 和 Y 是 V 的子集，|X| 2, |Y| 2 且 XQY=。在 G 中加入兩個(gè)新的頂點(diǎn)s 和 t , s 與 X 的每個(gè)頂點(diǎn)之間聯(lián)成一條邊，t 與 Y 的每個(gè)頂點(diǎn)間加一條邊，這樣得到的圖記為G。試證：G 是 2-連通的。11. 若 G 是頂點(diǎn)數(shù) p 11 的平面圖，試證 G 不是平面圖。12 設(shè) S=X

13、1, X2, X3,，Xn是平面上 n 個(gè)頂點(diǎn)的集合，n3,其中任兩頂點(diǎn)的距離 至少是 1。證明：S 中至多有 3n-6 對頂點(diǎn)，其距離為 1。13. 證明：不存在 7 條棱的凸多面體。14. 圖 G 的最短回路的長度稱為G 的圍長；若 G 中無回路，則定義 G 的圍長為無窮大。(i)證明：圍長為 r 的平面連通圖 G 中有q 3(ii)利用(i)證明 Petersen 圖(見圖 3.6.4)不是平面圖。15. 設(shè) G 是一個(gè)沒有三角形的平面圖。 應(yīng)用歐拉公式證明 G 中有一個(gè)頂點(diǎn) v 使得 degvw3。16.設(shè) G 是一個(gè)平面圖。證明： G*同構(gòu)于 G 當(dāng)且僅當(dāng) G 是連通的。17. 證明

14、：若 G 是自對偶的，則 q=2p-2.18. 設(shè) G 是一個(gè)沒有三角形的圖。應(yīng)用教學(xué)歸綱法證明G 是 4可著色的(事實(shí)上，可以證明 G 是 3可著色的)。19. 設(shè) G 是一個(gè)有 p 個(gè)頂點(diǎn)的 d-正則圖，證明：k(G) p/(p-d)。20. 試用 5-色定理的證明方法來證明4 色定理，在哪一點(diǎn)證明會(huì)失敗呢？21. 設(shè) G 是一個(gè)(p，q)圖，證明：k(G) p/(p -2p)。22. 證明：若 G 的任兩個(gè)奇數(shù)長的回路都有一個(gè)公共頂點(diǎn)，則k(G)w5。23. 證明：每個(gè)哈密頓平面圖都是4-可著色的。24. 設(shè) G 是一個(gè)立方體哈密頓圖，證明：k(G)=3。25. 若 r 是奇數(shù)且 G 是

15、 r-正則圖，證明：k(G)=r+1。26. 若 G 是彼德森圖，證明：k (G)=4。第五章習(xí)題1. 給出有向圖的子圖、生成子圖、導(dǎo)出子圖的定義。2. 畫出具有三個(gè)頂點(diǎn)的所有互不同構(gòu)的有向圖的圖解。3. 具有 p 個(gè)頂點(diǎn)的完全有向圖中有多少條?。?. 設(shè) D 是一個(gè)有 p 個(gè)頂點(diǎn) q 條弧的有向圖。若D 是連通的，證明p-1wqwp(p-1)。5. 設(shè) D 是一個(gè)有 p 個(gè)頂點(diǎn) q 條弧的強(qiáng)連通的有向圖，則q 至少是多大？6. 在有向圖中，含有所有頂點(diǎn)和所有弧的有向閉跡稱為有向歐拉閉跡。一個(gè)有向圖若含有有向歐閏閉跡，則稱此有向圖為有向歐拉圖。證明：有向圖D=(V，A)是有向歐拉圖當(dāng)且僅當(dāng) D

16、 是連通的且對任意的 v V，總有 id(v)=od(v)。7. 證明：有向圖 D 是單向連通的當(dāng)且僅當(dāng)D 有一條生成通道。8. 設(shè) A 是一個(gè) nXn 布爾矩陣，試證：(IVA)=(lVA)(IVA)=IVAVA其中 I 是 nxn 單位矩陣。其次，證明：對任意的正整數(shù)r，有8 / 7(IVA)(r)=IVAVA(2)V VA(r)9. 設(shè) B 是有向圖 D=(V，A)的鄰接矩陣，|V|=p。試證 D 的可達(dá)矩陣 R 為 R=(IVB)(p)9 / 710.有向圖 D 的圖解如圖一所示(1)寫出 D 的鄰接矩陣及可達(dá)矩陣。11. 設(shè) D 為圖二中的有向圖，試求12. 已知有向圖 D 的鄰接矩陣 B，13. 設(shè) T 是一個(gè)正則 m 元有序樹，它有 no個(gè)葉子，T 有多有多少條?。?4. 令 T 是一個(gè)正則 m 元樹，它有 i 個(gè)內(nèi)頂點(diǎn)(出度為 m)。若 E 為所有內(nèi)頂點(diǎn)深度之和,i 為所有葉頂點(diǎn)深度之和，證明：l=(m-1)l+mi。15. 設(shè) T 是一個(gè)有 no個(gè)葉子的二元樹，出度為2 的頂點(diǎn)為 n2,試證：no=n2+1。16.具有三個(gè)頂點(diǎn)的有序樹共有多少個(gè)？具有三個(gè)頂點(diǎn)的有根樹有多個(gè)？注意，同構(gòu)的 只算一個(gè)。17