哈工大集合與圖論習(xí)題

《哈工大集合與圖論習(xí)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、集合與圖論習(xí)題第一章習(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

2、．在一個(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

3、)·δ(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.給出一個(gè)10個(gè)頂點(diǎn)的非哈密頓圖的例子，使得每一對(duì)不鄰接的頂點(diǎn)u和v，均有degu+degv≥919．試求Kp中不同的哈密頓回路的個(gè)數(shù)。20．試證：圖四中的圖不是哈密頓圖。21．完全偶圖Km，n為哈密頓圖的充分必要條件是什么？22．菱形12面體的表面上

4、有無哈密頓回路？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)的圖。證明：若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é)家管梅谷

5、于1962年首先提出的，國外稱之為中國郵路問題。(1)試將中國郵路問題用圖論述語描述出來。(2)中國郵路問題、歐拉圖問題及最短路問題之間有何聯(lián)系。第三章習(xí)題1．分別畫出具有4、5、6個(gè)頂點(diǎn)的所有樹(同構(gòu)的只算一個(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的最小度δ(G)≥k，則G有一個(gè)同構(gòu)于T的子圖。6．一棵樹T有n2個(gè)度為2的頂點(diǎn)，n3個(gè)度為3的頂點(diǎn)，…，nk個(gè)度為k的頂點(diǎn)

6、，則T有多少個(gè)度為1的頂點(diǎn)？7.設(shè)G是一個(gè)連通圖。試證：G的子圖G1是G的某個(gè)生成樹的子圖，當(dāng)且僅當(dāng)G1沒有回路。8．證明：連通圖的任一條邊必是它的某個(gè)生成樹的一條邊。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)連通圖，對(duì)任意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′′中而不在T中的邊e′

7、的權(quán)w(e′)。11.某鎮(zhèn)有1000人，每天他們中的每個(gè)人把昨天聽到的消息告訴他認(rèn)識(shí)的人。已知任何消息，只要鎮(zhèn)上有人知道，都會(huì)經(jīng)這種方式逐漸地為全鎮(zhèn)上所有人知道。試證：可選出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ǔ)圖Gc的割點(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與

8、w間的每一條路上。17.割點(diǎn)的連通圖是否一定不是歐拉圖？是否一定不是哈密頓圖？有橋的連通圖是否一定不歐拉圖和哈密頓圖。18.L是連通圖G的一個(gè)回路，x和y是L上的兩條邊。證明：G有個(gè)割集S使得x與y恰好是L