資源描述：
《哈工大圖論習(xí)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第一章習(xí)題1．畫出具有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。8．設(shè)G是一個(gè)(p，q)圖，δ(G)≥[p/2]，試證G是連通的。9．證明：在一個(gè)連通圖中，兩條最長的路有一個(gè)公共的頂點(diǎn)。10．在一個(gè)有n個(gè)人的宴會(huì)上，每個(gè)人至少
2、有m個(gè)朋友(2≤m≤n)。試證：有不少于m+1個(gè)人，使得他們按某種方法坐在一張圓桌旁，每人的左、右均是他的朋友。11．一個(gè)圖G是連通的，當(dāng)且僅當(dāng)將V劃分成兩個(gè)非空子集V1和V2時(shí)，G總有一條聯(lián)結(jié)V1的一個(gè)頂點(diǎn)與V2的一個(gè)頂點(diǎn)的邊。12．設(shè)G是圖。證明：若δ(G)≥2，則G包含長至少是δ(G)+1的回路。13．設(shè)G是一個(gè)(p，q)圖，證明：(a)q≥p，則G中有回路；(b)若q≥p+4，則G包含兩個(gè)邊不重的回路。14．證明：若圖G不是連通圖，則Gc是連通圖。15．設(shè)G是個(gè)(p，q)圖，試證：(a)δ(G)·δ(GC)≤[(p-1)/2]([(p+1)/2]+1
3、)，若p≡0，1，2(mod4)(b)δ(G)·δ(GC)≤[(p-3)/2]·[(p+1)/2]，若p≡3(mod4)16．證明：每一個(gè)自補(bǔ)圖有4n或4n+1個(gè)頂點(diǎn)。17．構(gòu)造一個(gè)有2n個(gè)頂點(diǎn)而沒有三角形的三次圖，其中n≥3。18.給出一個(gè)10個(gè)頂點(diǎn)的非哈密頓圖的例子，使得每一對(duì)不鄰接的頂點(diǎn)u和v，均有degu+degv≥919．試求Kp中不同的哈密頓回路的個(gè)數(shù)。20．試證：圖四中的圖不是哈密頓圖。21．完全偶圖Km，n為哈密頓圖的充分必要條件是什么？22．菱形12面體的表面上有無哈密頓回路？23．設(shè)G是一個(gè)p(p≥3)個(gè)頂點(diǎn)的圖。u和v是G的兩個(gè)不鄰接的
4、頂點(diǎn)，并且degu+degv≥p。證明：G是哈密頓圖當(dāng)且僅當(dāng)G+uv是哈密頓圖。24．設(shè)G是一個(gè)有p個(gè)頂點(diǎn)的圖。證明：若p>2δ(G)，則有長至少為2δ(G)的路。25．證明具有奇數(shù)頂點(diǎn)的偶圖不是哈密頓圖。26．證明：若p為奇數(shù)，則Kp中有(p-1)/2個(gè)兩兩無公共邊的哈密頓回路。28．中國郵路問題：一個(gè)郵遞員從郵局出發(fā)投遞信件，然后返回郵局。若他必須至少一次走過他所管轄范圍內(nèi)的每條街道，那么如何選擇投遞路線，以便走盡可能少的路程。這個(gè)問題是我國數(shù)學(xué)家管梅谷于1962年首先提出的，國外稱之為中國郵路問題。(1)試將中國郵路問題用圖論述語描述出來。(2)中國郵
5、路問題、歐拉圖問題及最短路問題之間有何聯(lián)系。5/5第二章習(xí)題1．畫出具有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。8．設(shè)G是一個(gè)(p，q)圖，δ(G)≥[p/2]，試證G是連通的。9．證明：在一個(gè)連通圖中，兩條最長的路有一個(gè)公
6、共的頂點(diǎn)。10．在一個(gè)有n個(gè)人的宴會(huì)上，每個(gè)人至少有m個(gè)朋友(2≤m≤n)。試證：有不少于m+1個(gè)人，使得他們按某種方法坐在一張圓桌旁，每人的左、右均是他的朋友。11．一個(gè)圖G是連通的，當(dāng)且僅當(dāng)將V劃分成兩個(gè)非空子集V1和V2時(shí)，G總有一條聯(lián)結(jié)V1的一個(gè)頂點(diǎn)與V2的一個(gè)頂點(diǎn)的邊。12．設(shè)G是圖。證明：若δ(G)≥2，則G包含長至少是δ(G)+1的回路。13．設(shè)G是一個(gè)(p，q)圖，證明：(a)q≥p，則G中有回路；(b)若q≥p+4，則G包含兩個(gè)邊不重的回路。14．證明：若圖G不是連通圖，則Gc是連通圖。15．設(shè)G是個(gè)(p，q)圖，試證：(a)δ(G)·δ(
7、GC)≤[(p-1)/2]([(p+1)/2]+1)，若p≡0，1，2(mod4)(b)δ(G)·δ(GC)≤[(p-3)/2]·[(p+1)/2]，若p≡3(mod4)16．證明：每一個(gè)自補(bǔ)圖有4n或4n+1個(gè)頂點(diǎn)。17．構(gòu)造一個(gè)有2n個(gè)頂點(diǎn)而沒有三角形的三次圖，其中n≥3。18．在圖1.4.5中，一只車從位置A出發(fā)，在半張棋盤上走，每步走一格，走了若干步后到了位置B。證明：至少有一個(gè)格點(diǎn)，沒有車走過，或被走過不至一次。19.給出一個(gè)10個(gè)頂點(diǎn)的非哈密頓圖的例子，使得每一對(duì)不鄰接的頂點(diǎn)u和v，均有degu+degv≥920．試求Kp中不同的哈密頓回路的個(gè)數(shù)
8、。21．完全偶圖Km，n為哈密頓圖的充分必要條件是什
