圖論部分第六章圖的基本概念

難解問題

難解問題并不是說沒有算法，而是說沒有好的算法，計(jì)算機(jī)運(yùn)行時(shí)間太長。1．旅行商（貨郎擔(dān)）問題：Kp邊帶權(quán)圖，若p=60，則有60!個(gè)哈密頓回路。需要幾百年的時(shí)間才能找到最小哈密頓回路。

一般情況下所給的圖不一定是Kp，需要兩步：（1）有回路否？（2）有最小回路否？2．最小覆蓋問題：3．最大獨(dú)立集：4．最大團(tuán)問題：5．判斷圖是否有哈密頓（回）路問題.總結(jié)(1)有算法，但沒有好的，即沒有找到快速算法;(2)這樣的問題有幾百個(gè)，稍微一變就有幾千個(gè)；(3)這些問題都是等價(jià)的。若有一個(gè)有好的算法，則都有好的算法；若證明有一個(gè)沒有好的算法，則都沒有好的算法.易解問題6．最短路(徑)問題：

1959年迪克斯特拉(E.W.Dijkstra)給出了求邊帶權(quán)圖的最短路算法。這個(gè)算法能求出從給定頂點(diǎn)到圖中其他每個(gè)頂點(diǎn)的最短路。這就是求邊帶權(quán)無向圖中兩個(gè)給定頂點(diǎn)間的最短路問題。第六章圖的基本概念習(xí)題課1例1設(shè)d=(d1,d2,…,dn),其中di為非負(fù)整數(shù)，i=1,2,…,n。若存在n個(gè)頂點(diǎn)的(簡單)無向圖,使得頂點(diǎn)vi的度為di，則稱d是可圖解的。下面給出的各序列中哪些是可圖解的？哪些不是，為什么？（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）。例2

有n個(gè)藥箱，若每兩個(gè)藥箱里有一種相同的藥，而每種藥恰好放在兩個(gè)藥箱中，問藥箱里共有多少種藥？例3設(shè)G是有個(gè)p頂點(diǎn)，q條邊的無向圖，各頂點(diǎn)的度數(shù)均為3。則

(1)若q=3p-6,證明:G在同構(gòu)意義下唯一，并求p,q。

(2)若p=6，證明:G在同構(gòu)的意義下不唯一。例4已知p階(簡單)無向圖中有q條邊，各頂點(diǎn)的度數(shù)均為3，又2p=q+3，試畫出滿足條件的所有不同構(gòu)的G。例59個(gè)學(xué)生，每個(gè)學(xué)生向其他學(xué)生中的3個(gè)學(xué)生各送一張賀年卡。確定能否使每個(gè)學(xué)生收到的卡均來自其送過卡的相同人？為什么？解:否，不存在9（奇數(shù)）個(gè)頂點(diǎn)的3－正則圖。習(xí)題課2例1

若G是一個(gè)恰有兩個(gè)奇度頂點(diǎn)u和v的無向圖，則G連通

G+uv連通。例2

設(shè)V={v1,v2,…,vp}，計(jì)算以V為頂點(diǎn)集的無向圖的個(gè)數(shù)是多少？(KP有多少個(gè)生成子圖)例3

設(shè)V={v1,v2,…,vp},q≤p(p-1)/2，計(jì)算以V為頂點(diǎn)集具有q條邊的無向圖的個(gè)數(shù)是多少？例4

設(shè)G是（p,q）圖，r≤q，則具有r條邊的G的生成子圖有多少？答案：

2p(p-1)/2，Cqp(p-1)/2

，Crq。例5

證明：若無向圖G是不連通的，則G的補(bǔ)圖GC是連通的。書上例題例1

某工廠生產(chǎn)由6種不同顏色的紗織成的雙色布。雙色布中，每一種顏色至少和其他3種顏色搭配。證明:可以挑出3種不同的雙色布,它們含有所有6種顏色。（迪拉克）與例8等價(jià)的例題：例2

今要將6個(gè)人分成3組（每組2個(gè)人）去完成3項(xiàng)任務(wù)，已知每個(gè)人至少與其余5個(gè)人中的3個(gè)人能相互合作，問：

(1)能否使得每組2個(gè)人都能相互合作？

(2)你能給出幾中方案？（兩種）ⅰ習(xí)題3例1設(shè)G是一個(gè)有p(p≥3)個(gè)頂點(diǎn)的連通圖。u和v是G的兩個(gè)不鄰接的頂點(diǎn),并且degu+degv≥p。證明：G是哈密頓圖

G+uv是哈密頓圖。例2證明：完全圖K9中至少存在彼此無公共邊的兩條哈密頓圈和一條哈密頓路？例3

判斷如圖所示的圖是否為哈密頓圖，若是寫出哈密頓圈，否則證明其不是哈密頓圖。

例4(1)證明具有奇數(shù)頂點(diǎn)的偶圖不是哈密頓圖；用此結(jié)論證明如圖所示的圖不是哈密頓圖。

(2)完全偶圖Km,n為哈密頓圖的充要條件是什么？例5

試求Kp中不同的哈密頓圈的個(gè)數(shù)。例6

給出一個(gè)10個(gè)頂點(diǎn)的非哈密頓圖的例子，使得每一對不鄰接的頂點(diǎn)u和v，均有degu+degv≥9。例7證明：彼德森圖不是哈密頓圖。例8圖G是哈密頓圖。試證明：若圖中的哈密頓回路中含邊e1，則它一定同時(shí)也含e2。例9菱形12面體的表面上有無哈密頓回路？例10設(shè)G=(V,E)是連通圖且頂點(diǎn)數(shù)為p,最小度數(shù)為δ，若p>2δ,則G中有一長至少為2δ的路。例11設(shè)G=(V,E)是p(p>3)個(gè)頂點(diǎn)的簡單無向圖,設(shè)G中最長路L的長度為l(l≥2)，起點(diǎn)與終點(diǎn)分別為u,v，而且degu+degv≥p。證明：G中必有與L不完全相同但長度也為L的路。例12已知a,b,c,d,e,f,g7個(gè)人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？ⅰ例13設(shè)G為p個(gè)頂點(diǎn)的簡單無向圖。則

(1)若G的邊數(shù)q=(p-1)·(p-2)/2+2，證明G為哈密頓圖。

(2)若G的邊數(shù)q=(p-1)·(p-2)/2+1，則G是否一定為哈密頓圖？例14已知9個(gè)人v1,v2,…,v9，其中v1和兩個(gè)人握過手，v2,v3,v4,v5各和3個(gè)人握過手，v6和4個(gè)人握過手，v7,v8各和5個(gè)人握過手，v9和6個(gè)人握過手。證明:這9個(gè)人中一定可以找出3個(gè)人互相握過手。第七章樹和割集(習(xí)題課1)例1

若無向圖G中有個(gè)p頂點(diǎn)，p-1條邊，則G為樹。這個(gè)命題正確嗎？為什么？例2畫出具有4、5、6、7個(gè)頂點(diǎn)的所有非同構(gòu)的無向樹。例3設(shè)無向圖G是由K(K≥2)棵樹構(gòu)成的森林，至少在G中添加多少條邊才能使G成為一棵樹？例4設(shè)T是一棵樹，T有3個(gè)度為3頂點(diǎn)，1個(gè)2度頂點(diǎn)，其余均是1度頂點(diǎn)。則(1)求T有幾個(gè)1度頂點(diǎn)？(2)畫出滿足上述要求的不同構(gòu)的兩棵樹。例5設(shè)樹T中有2n個(gè)度為1的頂點(diǎn),有3n個(gè)度為2的頂點(diǎn),有n個(gè)度為3的頂點(diǎn),則這棵樹T有幾個(gè)頂點(diǎn)和幾條邊？例6設(shè)T是一棵樹且△(T)≥k,證明:T中至少有k個(gè)度為1的頂點(diǎn)。例7設(shè)G是一個(gè)(p,q)圖,若q≥p,證明G中必有圈。例8證明:任一非平凡樹最長路的兩個(gè)端點(diǎn)都是樹葉。例9證明:恰有兩個(gè)頂點(diǎn)度數(shù)為1的樹必為一條通路。例9(1)一棵無向樹有ni個(gè)度數(shù)為i的頂點(diǎn),i=1,2,…,k。n2,n3,….nk均為已知數(shù)，問n1應(yīng)為多少？(2)在(1)中，若nr(3≤r≤k)未知，nj(j≠r)均為已知數(shù)，問nr應(yīng)為多少？例11設(shè)d1,d2,…,dp是p個(gè)正整數(shù),p≥2,且。證明:存在一棵頂點(diǎn)度數(shù)為d1,d2,…,dp的樹。習(xí)題課２例１設(shè)G是連通圖，滿足下面條件之一的邊應(yīng)具有什么性質(zhì)？（1）在G的任何生成樹中；（2）不在G的任何生成樹中。例2

非平凡連通圖G是樹當(dāng)且僅當(dāng)G的的每條邊都是橋。例3

設(shè)T是一棵樹，p≥2

，則（1）p個(gè)頂點(diǎn)的樹至多有多少個(gè)割點(diǎn)；（2）p個(gè)頂點(diǎn)的樹有多少個(gè)橋？例4

證明或否定斷言：連通圖G的任意邊是G的某一棵生成樹的弦。第八章習(xí)題課１定理1

設(shè)G=(V1∪V2，E)是一個(gè)偶圖，|V1|≤|V2|。G中存在從V1到V2的完全匹配

是V1中任意k個(gè)頂點(diǎn)(k=1,2,…,|V1|)至少與V2中的k個(gè)頂點(diǎn)相連接。例１現(xiàn)有4名教師：張、王、李、趙，要求他們?nèi)ソ?門課程：數(shù)學(xué)、物理、電工和計(jì)算機(jī)科學(xué)。已知張能教數(shù)學(xué)和計(jì)算機(jī)科學(xué)；王能教物理和電工；李能教數(shù)學(xué)、物理和電工；趙只能教電工。如何安排才能使4位教師都能教課，并且每門課都有人教？共有幾種方案？用相異性條件判斷一個(gè)偶圖是否存在完全匹配常常很不方便，下面的充分條件比較便于實(shí)際應(yīng)用。定理2

設(shè)G=(V1∪V2，E)是一個(gè)偶圖，|V1|≤|V2|。G中存在從V1到V2的完全匹配的充分條件是存在正整數(shù)t，使得V1中每個(gè)頂點(diǎn)的度大于等于t，V2中每個(gè)頂點(diǎn)的度小于等于t。該條件稱為t條件。例２某年級共開設(shè)7門課程，由7位教師承擔(dān)。已知每位教師都能擔(dān)任其中的3門課程。他們將自己能擔(dān)任的課程報(bào)到教務(wù)處后，教務(wù)處人員發(fā)現(xiàn)每門課都恰好有3位教師能擔(dān)任。問教務(wù)處人員能否安排這7位教師每人擔(dān)任1門課，并且每門課都有人承擔(dān)。例3

某雜志發(fā)表了7個(gè)征求答案的題目，當(dāng)從讀者寄來的解答中挑選每題的兩個(gè)解答時(shí)，編輯發(fā)現(xiàn)所有14個(gè)選出來的解答恰好是7個(gè)讀者提出來的，而且每個(gè)人正好提出了兩個(gè)答案。證明：編輯可以這樣發(fā)表每道題的一個(gè)解答，使得在發(fā)表的解答中，這7個(gè)讀者每人都恰有一個(gè)解答。定理3

從t條件可以推出相異性條件。注意：定理3中反過來不能推出t條件。推論1

任何r-正則偶圖G＝(V1∪V2,E)必有一個(gè)完美匹配，其中r≥1。第九章平面圖和圖的著色習(xí)題課１1.設(shè)G是有k個(gè)分支、f個(gè)面的(p,q)平面圖，則p-q+f=k+1。2.證明：下列4個(gè)圖均是可平面圖。3．如圖所示的圖G是否為平面圖？是否為極大平面圖？為什么？4.證明：極大平面圖G一定是連通圖。5.設(shè)G是有p(p≥3)個(gè)頂點(diǎn)的簡單平面連通圖，且G的每個(gè)面均是由3條邊圍成，證明：G是極大平面圖。（若G是極大平面圖，則G的每個(gè)面都是三角形）6.由6個(gè)頂點(diǎn)，12條邊構(gòu)成的平面連通圖G中，每個(gè)面由幾條邊圍成？為什么？7．證明：若每個(gè)頂點(diǎn)的度數(shù)大于等于3時(shí)，則不存在有7條邊的平面連通圖。(等價(jià)命題：證明：不存在7條棱的凸多面體)8.設(shè)G是頂點(diǎn)p≥11的平面圖，證明：G的補(bǔ)圖Gc是非平面圖。(設(shè)G是頂點(diǎn)p≥11的圖，證明：G與G的補(bǔ)圖Gc至少有一個(gè)是非平面圖。)9.設(shè)G是平面連通圖，頂點(diǎn)為p面數(shù)f，證明:(1)若p≥3，則f≤2p-4。(2)若δ(G)=4,則G中至少有6個(gè)頂點(diǎn)的度數(shù)≤5。10．設(shè)G是邊數(shù)q<30的平面圖,證明:G中存在頂點(diǎn)v，使得degv≤4。習(xí)題課21.說明圖中所示圖(1)(2)是否是非平面圖？2．證明:彼得森圖不是平面圖。

(1)收縮法；(2)歐拉公式法；(3)收縮到K3,3。3.設(shè)G是無向圖,p<8,則G與Gc中至少有一個(gè)是平面圖。4.設(shè)平面圖G的頂點(diǎn)數(shù)p=7,邊數(shù)q=15，證明G是連通的。習(xí)題課31．判斷下面命題是否正確，并說明理由。 任意平面圖G的對偶圖G*的對偶圖G**與G同構(gòu)。2.設(shè)G*是平面圖G的對偶圖，證明：p*=f，q*=q，

f*=p-k+1。其中k(k≥1)為G的連通分支數(shù)。3.證明：若G是自對偶的平面圖，則q=2p-2。其中p和q是G的邊與頂點(diǎn)數(shù)。4．把平面分成p個(gè)區(qū)域，每兩個(gè)區(qū)域都相鄰，問p最大為多少？5.證明：不存在具有5個(gè)面，每兩個(gè)面都共享一條公共邊的平面圖G。習(xí)題課41．求下列各類圖頂點(diǎn)的色數(shù)。

(1)p階零圖Np;(2)完全圖Kp;(3)p階輪圖Wp(輪圖至少有4個(gè)頂點(diǎn));(4)彼德森圖(如圖1所示);(5)如圖2所示。2.若圖G的色數(shù)（或頂點(diǎn)色數(shù)）K(G)=k，則G中至少有k(k-1)/2條邊。3.設(shè)G是一個(gè)沒有三角形的平面圖，則（1）證明：G中存在一個(gè)頂點(diǎn)v，使得degv≤3；（2）證明：G是4-可著色的。4.5四色問題在圖論中，也許是全部數(shù)學(xué)中，最著名、最難的問題是四色猜想。這個(gè)猜想說，在一個(gè)平面或球面上的任何地圖能夠只用四種顏色來著色，使沒有兩個(gè)相鄰的國家有相同的顏色。

在這里，每個(gè)國家必須是一個(gè)單連通區(qū)域構(gòu)成，兩個(gè)國家相鄰是指它們有一段公共邊界線，不能只有一個(gè)公共點(diǎn)。

1852年，格里斯（Guthrie）兄弟在通信中提出了四色問題，小格里斯求教與他的老師德摩根（Demorgan），德摩根與他的朋友在通信中討論過這個(gè)問題，但他們都無法給予解決。

1878年凱萊（Cayley）在倫敦?cái)?shù)學(xué)大會上宣布了這個(gè)問題，引起了數(shù)學(xué)界的廣泛注意。

1879年肯普（Kempe）、1880年Tait發(fā)表論文，聲稱證明了四色問題。

1890年，希伍德（Heawood）指出了肯普（Kempe）證明中的一處錯(cuò)誤，但卻利用肯普（Kempe）的方法證明了五色定理成立?？掀眨↘empe）的這個(gè)錯(cuò)誤使得他的論證是不完全的。不過，應(yīng)當(dāng)指出的是:肯普（Kempe）推理路線是1976年美國的阿普爾(K.Appel)、黑肯(W.Haken)和考齊(J.Koch)等3人所給出的成功證明的基礎(chǔ)。

1891年，彼德森（Petersen）指出了Tait證明中所存在的錯(cuò)誤，但Tait的方法也有其合理部分。經(jīng)過了一百年之后，這個(gè)貌似簡單的四色猜想才被美國的阿普爾(K.Appel)、黑肯(W.Haken)和考齊(J.Koch)等3人在1976年借助于計(jì)算機(jī)用了1200多個(gè)小時(shí)，100億個(gè)邏輯判斷才證明了四色定理。從而四色猜想成了四色定理。這個(gè)證明引起了廣泛的爭論，主要是因?yàn)橛?jì)算機(jī)在這里起到的重要作用。然而,四色定理的數(shù)學(xué)方法的證明還是一個(gè)沒有解決的問題。第十章習(xí)題課例1

設(shè)T=(V,A)是一個(gè)有根樹,其每個(gè)頂點(diǎn)的