1、集合與圖論習題第一章 習 題1畫出具有4個頂點的所有無向圖(同構的只算一個)。2畫出具有3個頂點的所有有向圖(同構的只算一個)。3畫出具有4個、6個、8個頂點的三次圖。4某次宴會上，許多人互相握手。證明：握過奇數次手的人數為偶數(注意，0是偶數)。5證明：哥尼斯堡七橋問題無解。6設u與v是圖G的兩個不同頂點。若u與v間有兩條不同的通道(跡)，則G中是否有回路？7證明：一個連通的(p，q)圖中q p-1。8設G是一個(p，q)圖，(G)p/2，試證G是連通的。9證明：在一個連通圖中，兩條最長的路有一個公共的頂點。10在一個有n個人的宴會上，每個人至少有m個朋友(2mn)。試證：有不少于m+1個人

2、，使得他們按某種方法坐在一張圓桌旁，每人的左、右均是他的朋友。11一個圖G是連通的，當且僅當將V劃分成兩個非空子集V1和V2時，G總有一條聯結V1的一個頂點與V2的一個頂點的邊。12設G是圖。證明：若 (G) 2，則G包含長至少是(G)+1的回路。13設G是一個(p，q)圖，證明：(a)qp，則G中有回路； (b)若qp+4，則G包含兩個邊不重的回路。14證明：若圖G不是連通圖，則Gc 是連通圖。15設G是個(p，q)圖，試證：(a)(G)·(GC)(p-1)/2(p+1)/2+1)，若p0，1，2(mod 4)(b) (G)·(GC)(p-3)/2·(p+1)/

3、2，若p3(mod 4)16證明：每一個自補圖有4n或4n+1個頂點。17構造一個有2n個頂點而沒有三角形的三次圖，其中n3。18.給出一個10個頂點的非哈密頓圖的例子，使得每一對不鄰接的頂點u和v，均有degu+degv919試求Kp中不同的哈密頓回路的個數。20試證：圖四中的圖不是哈密頓圖。21完全偶圖Km，n為哈密頓圖的充分必要條件是什么？22菱形12面體的表面上有無哈密頓回路？23設G是一個p(p3)個頂點的圖。u和v是G的兩個不鄰接的頂點，并且degu+degvp。證明：G是哈密頓圖當且僅當G+uv是哈密頓圖。24設G是一個有p個頂點的圖。證明：若p>2(G)，則有長至少為2(

4、G)的路。 25證明具有奇數頂點的偶圖不是哈密頓圖。26證明：若p為奇數，則Kp中有(p-1)/2個兩兩無公共邊的哈密頓回路。28中國郵路問題：一個郵遞員從郵局出發投遞信件，然后返回郵局。若他必須至少一次走過他所管轄范圍內的每條街道，那么如何選擇投遞路線，以便走盡可能少的路程。這個問題是我國數學家管梅谷于1962年首先提出的，國外稱之為中國郵路問題。(1)試將中國郵路問題用圖論述語描述出來。(2)中國郵路問題、歐拉圖問題及最短路問題之間有何聯系。第三章 習 題 1分別畫出具有4、5、6個頂點的所有樹(同構的只算一個)。2證明：每個非平凡樹是偶圖。3設G是一棵樹且(G)k，證明：G中至少有k個度

5、為1的頂點。4令G是一個有p個頂點，k個支的森林，證明：G有p-k條邊。5設T是一個k+1個頂點的樹。證明：若圖G的最小度(G)k，則G有一個同構于T的子圖。6一棵樹T有n2個度為2的頂點，n3個度為3的頂點，nk個度為k的頂點，則T有多少個度為1的頂點？7.設G是一個連通圖。試證：G的子圖G1是G的某個生成樹的子圖，當且僅當G1沒有回路。8證明：連通圖的任一條邊必是它的某個生成樹的一條邊。9設G是一個邊帶權連通圖，G的每條邊均在G的某個回路上。試證：若G的邊e的權大于G的任一其他邊的權，則e不在G的任一最小生成樹中。10. 設G=(V，E，w)是一個邊帶權連通圖，對任意xE，w(x)0。試證

6、：G的一個生成樹T是G的最小生成樹，當且僅當時G的任一與T的距離為1的生成樹T滿足條件：在T中而不在T中的邊e的權w(e)不大于在T中而不在T中的邊e的權w(e)。11.某鎮有1000人，每天他們中的每個人把昨天聽到的消息告訴他認識的人。已知任何消息，只要鎮上有人知道，都會經這種方式逐漸地為全鎮上所有人知道。試證：可選出90個居民代表使得只要同時向他們傳達某一消息，經10天就會為全鎮居民知道。12.P個頂點的圖中，最多有多少個割點？13證明：恰有兩個頂點不是割點的連通圖是一條路。14證明：有一座橋的三次圖中至少有10個頂點。15設v是圖G的一個割點，證明v不是G的補圖Gc的割點。16設v是圖G

7、的一個頂點。證明：v是G的割點當且僅當有鄰接v的兩個不同的頂點u和w，使得v在u與w間的每一條路上。17.割點的連通圖是否一定不是歐拉圖？是否一定不是哈密頓圖？有橋的連通圖是否一定不歐拉圖和哈密頓圖。18.L是連通圖G的一個回路，x和y是L上的兩條邊。證明：G有個割集S使得x與y恰好是L與S的公共邊。第四章 習 題1設G是一個有p個頂點的圖，(G)(p+k)-1)/2，試證：G是k-連通的。2若(p，q)圖G是k-邊連通的，試證：qkp/2。3設G是k-邊連通的，k>0，E是G的k條邊的集合。證明：G-E的支數小于或等于2。4構造一個(p，q)圖G使得(G)=p/2-1，(G)<(

8、G).5設k>0。構造一個k-連通圖G，以及G的k個頂點之集V，使得G-V的支數大于2。6G是一個三次正則圖，試證：(G)=(G)。7設r2，G是r正則圖。證明：(G)r/2。8構造一個圖G，使得(G)=3，(G)=4，(G)=5。9證明：圖G是2-邊連通的當且僅當任兩個不同頂點間至少有兩條邊不重路。10設G=(V，E)是2-邊連通圖，X和Y是V的子集，|X|2，|Y|2且XY=。在G中加入兩個新的頂點s和t，s與X的每個頂點之間聯成一條邊，t與Y的每個頂點間加一條邊，這樣得到的圖記為G。試證：G是2-連通的。11. 若G是頂點數p11的平面圖，試證Gc不是平面圖。12 設Sx1，x2，

9、x3，xn是平面上n個頂點的集合，n3，其中任兩頂點的距離至少是1。證明：S中至多有3n-6對頂點，其距離為1。13證明：不存在7條棱的凸多面體。14. 圖G的最短回路的長度稱為G的圍長；若G中無回路，則定義G的圍長為無窮大。()證明：圍長為r的平面連通圖G中有qr(p-2)/(r-2)，r3()利用( )證明Petersen圖(見圖)不是平面圖。15.設G是一個沒有三角形的平面圖。應用歐拉公式證明G中有一個頂點v使得degv 3。16設G是一個平面圖。證明：G*同構于G當且僅當G是連通的。17證明：若G是自對偶的，則q=2p-2.18.設G是一個沒有三角形的圖。應用教學歸綱法證明G是4可著色

10、的(事實上，可以證明G是3可著色的)。19.設G是一個有p個頂點的d-正則圖，證明：k(G)p/(p-d)。20.試用5-色定理的證明方法來證明4色定理，在哪一點證明會失敗呢？21.設G是一個(p，q)圖，證明：k(G)p2/(p2-2p)。22.證明：若G的任兩個奇數長的回路都有一個公共頂點，則k(G)5。23.證明：每個哈密頓平面圖都是4-可著色的。24.設G是一個立方體哈密頓圖，證明：k(G)=3。25.若r是奇數且G是r-正則圖，證明：k(G)=r+1。26.若G是彼德森圖，證明：k(G)=4。第五章 習 題1.給出有向圖的子圖、生成子圖、導出子圖的定義。2.畫出具有三個頂點的所有互不

11、同構的有向圖的圖解。3.具有p個頂點的完全有向圖中有多少條??？4.設D是一個有p個頂點q條弧的有向圖。若D是連通的，證明p-1qp(p-1)。5.設D是一個有p個頂點q條弧的強連通的有向圖，則q至少是多大？6.在有向圖中，含有所有頂點和所有弧的有向閉跡稱為有向歐拉閉跡。一個有向圖若含有有向歐閏閉跡，則稱此有向圖為有向歐拉圖。證明：有向圖D=(V，A)是有向歐拉圖當且僅當D是連通的且對任意的vV，總有id(v)=od(v)。7.證明：有向圖D是單向連通的當且僅當D有一條生成通道。8.設A是一個n×n布爾矩陣，試證：(IA)(2)=(IA)(IA)=IAA(2)其中I是n×n單

12、位矩陣。其次，證明：對任意的正整數r，有(IA)(r)=IA A(2)A(r)9.設B是有向圖D=(V，A)的鄰接矩陣，|V|=p。試證D的可達矩陣R為R=(IB)(p)10.有向圖D的圖解如圖一所示(1)寫出D的鄰接矩陣及可達矩陣。(2)寫出D關聯矩陣。11.設D為圖二中的有向圖，試求v2到其余每個頂點的長4的所有通道的條數。12.已知有向圖D的鄰接矩陣B，如何從B求D的可達矩陣R？ 13.設T是一個正則m元有序樹，它有n0個葉子，T有多有多少條弧？14令T是一個正則m元樹，它有i個內頂點(出度為m)。若E為所有內頂點深度之和，i為所有葉頂點深度之和， 證明：I=(m-1)I+mi。15.設T是一個有n0個葉子的二元樹，出度為2的頂點為n2，試證：n0=n2+1。16.具有三個頂點的有序樹共有多少個？具有三個頂