2012江蘇省數(shù)學(xué)競賽《提優(yōu)教程》教案：第68講_圖論問題(二)

《2012江蘇省數(shù)學(xué)競賽《提優(yōu)教程》教案：第68講_圖論問題(二)》由會員分享，可在線閱讀，更多相關(guān)《2012江蘇省數(shù)學(xué)競賽《提優(yōu)教程》教案：第68講_圖論問題(二)（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 第68講 圖論問題(二) 本講主要內(nèi)容：本講將繼續(xù)研究用圖來解決問題的方法． 偶圖 取圖G＝(V，E)，如果V＝X∪Y，X∩Y＝?，其中X＝{x1，x2，…，xn}，Y＝{y1，y2，…，ym}，且xi與xj(1≤i＜j≤n)，ys與yt (1≤s＜t≤m)均互不相鄰，則稱G為偶圖． 色數(shù)：將圖G的頂點涂上顏色，如果至少要k種顏色才能使任意兩個相鄰的頂點顏色不同，則稱G的色數(shù)為k．顯然，偶圖的色數(shù)≤2．即偶圖色數(shù)不超過2． A類例題 例1 在空間中給定2n個不同的點A1，A2，…，A2n，n＞1，其中任意三點不共線．設(shè)M是n2+1條以給定的點為端點的線段的集合．⑴證明：存在一

2、個三角形，其頂點為給定的點，其邊都屬于M．⑵證明：若集合M的元素不超過n2個，則這樣的三角形可能不存在．(1973年奧地利數(shù)學(xué)競賽) 分析 可以從簡單的情況開始試驗，發(fā)現(xiàn)規(guī)律再證明．從K4(4階完全圖，見67講)共有多少條線及多少個三角形、擦去1條線去掉幾個三角形入手得出結(jié)論，對于K5、K6也能用此法得到結(jié)論，但對于p＞6，Kp難用此法，如何過渡到一般情況？可以用數(shù)學(xué)歸納法． 證明：n＝2時，在4個點間連了5條線，由于4階完全圖在4個點間共可連出6條線，這6條線連出了4個以此4點中的某3點為頂點的三角形．而每條線的兩個端點與(除這條線的兩個端點外的)另兩個頂點可以連出共2個三角形，故去掉任

3、何一條邊都使連出三角形數(shù)減少2，于是在4個點間連5條線必連出了以此4點中的3點為頂點的三角形． 設(shè)n＝k時，2k個點間連有k2＋1條線時，必有三角形出現(xiàn)．則當n＝k＋1時，2(k＋1)個點間連了(k＋1)2＋1條線．此時，任取兩個相鄰的頂點v1，v2，如果在其余的頂點中有某個頂點與v1，v2都連了線，例如v3與v1，v2都連了線(圖4(1))，則出現(xiàn)了三角形．如果其余所有的點與此二點都至多連出1條線(圖4(2))，則去掉點v1，v2及與這兩點相鄰的邊，此時，余下2k個點，至多去掉了2k＋1條邊，余下至少(k＋1)2＋1－(2k＋1)＝k2＋1條邊，由歸納假設(shè)知，其中必有三角形． 綜上可知，

4、命題成立． 說明 若2n個點間連了n2條邊，可以把這2n個點分成兩組，每組n個點，規(guī)定同組的點間都不連線，不同組的任何兩點都連1條線，這樣得到了一個完全偶圖Kn，n，此時共計連了n2條線，但任取三點，必有兩點在同一組，它們之間沒有連線，于是不出現(xiàn)三角形． 例2 一個舞會有n(n≥2)個男生與n個女生參加，每個男生都與一些女生(不是全部)跳過舞，而每個女生都至少與1名男生跳過舞，證明，存在男生b1，b2與女生g1，g2，其中b1與g1跳過舞，b2與g2跳過舞．但b1與g2沒有跳過舞，b2與g1沒有跳過舞． 分析 就是要給出一種選擇方法，按此方法操作，即可選出滿足要求的兩個男生與兩個女生

5、．可以用極端原理來證明這樣的存在性命題． 證明 取所有男生中與女生跳舞人數(shù)最多的一個，設(shè)是b1．b1至少與1名女生沒有跳過舞，取沒有與b1跳過舞的一名女生為g2，g2至少與1名男生跳過舞，設(shè)為b2，顯然b1不是b2，現(xiàn)在考慮所有沒有與b2跳過舞的女生，她們不能都沒有與b1跳過舞，(否則沒有與b1跳舞的女生人數(shù)就比沒有與b2跳舞的人數(shù)多，b1就不是與女生跳舞人數(shù)最多者)．即至少有1個女生沒有跟b2跳過舞但跟b1跳過舞．這個女生即為g1． 說明 這里就得到了一個偶圖{b1，b2}∪{g1，g2}．(圖中，括號內(nèi)的數(shù)字表示證明中出現(xiàn)的先后順序)．極端原理常用于證明存在性命題． 情景再現(xiàn)

6、1．求證：頂點多于1的樹是偶圖． 2．證明 偶圖的色數(shù)≤2，反之，色數(shù)≤2的圖是偶圖． B類例題 例3 某鎮(zhèn)有居民1000人，每人每天把昨天聽到的消息告訴自己認識的人，已知任何消息只要鎮(zhèn)上有人知道，都會經(jīng)過這樣的方式逐漸地為全鎮(zhèn)的人所知道．證明可以選出90名代表，使得同時向他們報告一個消息，經(jīng)過10天，這一消息就為全鎮(zhèn)的人知道． 分析 就是要給出一個把1000個點的連通圖分成90個子圖的方法，使每個點都在其中一個子圖中，且每個子圖的最長的鏈的長度不超過10．這樣，只要把每個子圖的最長鏈的一個端點選為“代表”，就能完成這個任務(wù)． 證明 用1000個點代表1000個居民，兩名居民相識

7、，則在兩點之間連一線，如此可得一圖，依條件，這個圖是連通圖．若圖中有圈，則我們?nèi)サ羧χ械囊贿吺谷Ρ黄茐亩挥绊憟D的連通性，經(jīng)過有限次這種手續(xù)，可得樹T1000． 在T1000中取一條主干v1v2…vn，取v11作為1個代表，把邊v11v12去掉，則此圖分成了2個連通分支，在含有v1的一棵樹中，每點到v11的路的長度都不超過10，否則v1v2…vn在T1000中不是主干，故v11知道的消息在10天內(nèi)可以傳遍它所在分支的點集所代表的居民；余下另一分支再取其主干，又按此法得出第二個代表v22，依此類推，則T1000分割成若干棵樹：同樣，在含v22，v33，…的樹中，v22，v33，…知道的消息在1

8、0天內(nèi)都能傳遍樹的點集所代表的居民；由于1000=11×89+21，且每一個小分支樹可能還有分支，從而其頂點數(shù)可能超過11，所以這樣分法，至多分出89棵樹并余下一個至多有21個點的樹，該樹的鏈長≤20，取此鏈的中心v，則該鏈上每個點到v的距離都≤10．現(xiàn)在取v11，v22，v33，…為代表，最后一棵樹取其中心v為第90名代表，只要將消息告訴這些代表，則在10天之后，每個分支樹的點集所表示的居民全都知道這個消息，問題已獲解決． 說明 注意每次在最長鏈上截去一段后，余下的鏈的主干不一定就是原來主干的截剩部分，所以每次都要重新確定主干． 例4 一個國家的國王打算建n個城市且修(n－1)條道路

9、，使每條道路連接兩個城市而不經(jīng)過其他城市．而每兩個城市都可以互相到達，其間的最短距離恰是1，2，…，C＝n(n－1)這些數(shù)，問在下列情況下，國王的打算能否實現(xiàn)：(1)n＝6；(2)n＝1998． 分析 就是要畫一個樹，使任兩個頂點的距離都不能相同．對于頂點數(shù)少的情況估計是可能存在的，而要得到n＝6圖可以用構(gòu)造法．對于n＝1998，估計不會存在，所以可以用反證法證明． 為了得到n＝6的情形，長度為1與2的線段是要取的，否則得不到1，2，這兩條線段連結(jié)可以得到長度3，為得到距離為15、14、…的線段，可以取某兩個城市間距離為8(15的一半)，此時8＋7＝15，8＋6＝14，8＋5＝13可以通過

10、增加一條長度為5的線段如圖得到，再增加一條長為4的線即可得到全部的15個數(shù)． 解 (1) n＝6時，國王的打算可以實現(xiàn)，城市和道路的分布可依據(jù)圖所示． ⑵ n＝1998時，國王的打算不能實現(xiàn)，因為符合要求的道路網(wǎng)存在的必要條件是：n或(n－2)是完全平方數(shù)，證明如下： 用點表示城市，用線表示連接城市的道路，得到一個圖G．由題設(shè)，知G是n階連通圖，又其線的數(shù)目恰為(n－1)，故G是n階樹，因而G的任兩點之間只存在唯一的通道．把G的頂點二染色：任取一個點A，對于圖中任一點，若它沿唯一的通道到A的距離是一個偶數(shù)，則把此點染紅(A也應(yīng)染紅，因A到A的距離為0，0是偶數(shù))，否則染藍． 設(shè)紅點的數(shù)

11、目為x，則藍點的數(shù)目為y＝n－x．考慮距離為奇數(shù)的點對，易知：兩點之間的距離為奇數(shù)，當且僅當這兩個點一紅一藍．由一個紅點和一個藍點組成的點對有xy個．又在1，2，…，n(n－1)中，當n(n－1)為偶數(shù)時，其中的奇數(shù)有n(n－1)個；當n(n－1)為奇數(shù)時，奇數(shù)有[n(n－1)＋2]個．于是，如果國王的打算可以實現(xiàn)，則必須滿足 xy＝n(n－1) ① 或 xy＝[n(n－1)＋2] ②． 此時，對于①，有4x(n－x)＝n(n－1)，即 4x2－4nx+n2－n＝0， 解得 x＝，相應(yīng)的y＝． 同樣，對于②： 有x＝，y＝． 故只有n或(n－2)是

12、完全平方數(shù)時，國王的愿望才可能實現(xiàn)．但1998和1998－2＝1996都不是完全平方數(shù)，故當n＝1998時，國王的打算不可能實現(xiàn)． 說明 我們只證明了這個條件是必要條件，沒有證明這個條件是充分的．對于n＝6，有6－2＝4是完全平方數(shù)，有可能存在滿足要求的圖，再通過構(gòu)造出滿足要求的圖，才能確定解存在． 例5證明：任意的9個人中，必有3個人互相認識或4個人互相不認識． 分析 即證明，在任意的K9中，把邊涂成紅或藍兩種顏色，則必存在紅色K3或藍色的K4．或在一個有9個頂點的圖G中，必存在K3，或在其補圖中，存在K4． 證明⑴ 如果存在一個頂點，從這點出發(fā)的8條線中，有至少4條為紅色，設(shè)從

13、v1引出的4條線為紅色，引到v2，v3，v4，v5．若此4點中的某2點間連了紅色線，則存在紅色K3，若此4點間均連藍線，則存在藍色K4． ⑵ 如果從任一點出發(fā)的8條線中，紅色線都少于4條．于是從每點出發(fā)的藍色線都至少5條．但由于任何圖中的奇頂點個數(shù)為偶數(shù)，故不可能這9個頂點都引出5條藍線．于是至少有一個頂點引出的藍線≥6條，例如從v1到v2，v3，…，v7都引藍線，則在v2，v3，…，v7這6個點的圖中，必存在紅色三角形或藍色三角形，于是G中必有紅色K3，或藍色K4． 鏈接 拉姆賽(Ramsey)問題 本題實際上說的是：在有n個頂點的圖G中，有一個K3，或在其補圖中(在K9中去掉G的

14、所有邊后余下的圖即G的補圖)有一個K4，二者必有一成立．n＝9是保證這一個結(jié)論成立的n的最小值．一般的，在一個有t個頂點的圖中存在Km，或在其補圖中存在Kn，t的最小值是多少？這就是拉姆賽問題．記滿足上述要求的t的最小值為r(m，n)． 則有 r(m，n)＝r(n，m)， r(1，n)＝r(m，1)＝1，r(2，n)＝n，r(m，2)＝m． 并可證： 定理一 在m≥2，n≥2時，r(m，n)≤r(m，n－1)＋r(m－1，n)． 現(xiàn)在已經(jīng)求出的r(m，n)有：r(3，3)＝6，r(3，4)＝9，r(3，5)＝14，r(3，6)＝18，r(3，7)＝23；r(4，4)＝18．

15、 定理二 設(shè)完全圖KN的邊涂了n種顏色，則在N充分大時，KN中必有一個同色三角形．設(shè)rn是使KN中有同色三角形存在在N的最小值，則 ⑴ r1＝3，r2＝6，r3＝17； ⑵ rn≤n(rn－1－1)＋2； ⑶ rn≤1＋1＋n＋n(n－1)＋…＋＋＋n!． 上述兩個定理都是拉姆賽定理的特例，更一般的結(jié)論請參閱單墫教授的有關(guān)圖論的著作．例如《趣味的圖論問題》等 情景再現(xiàn) 3．平面α上有n條直線，把α分成若干區(qū)域，證明：可以用兩種顏色就可使相鄰的區(qū)域都涂上不同的顏色． 4．在8×8的棋盤上填入1~64的所有整數(shù)，每格填一個數(shù)，每個數(shù)填一次．證明：總能找到兩個相鄰的格子(有公共邊的

16、兩個方格就是相鄰的方格)，這兩個方格中填的數(shù)相差不小于5． 5．證明：任意14人中，必有3人互相認識或有5人互相不認識． C類例題 例6 1990個人分成n組，滿足 (a) 每個組中沒有人認識同組的所有的人； (b) 每個組中，任意三人中至少有兩人互不認識； (c) 每個組中兩個互不認識的人，必可在同組中恰好找到一個他們都認識的人． 證明：在每一組中，各人在該組中認識的人數(shù)都相同．并求分組個數(shù)n的最大值．(1990亞洲與太平洋地區(qū)數(shù)學(xué)競賽) 分析 條件都是針對某一組的，所以證明應(yīng)在某個組內(nèi)進行，由于兩點或連線，或未連線，故可以分兩點未連線及兩點已連線的情況證明． 要求組數(shù)最

17、多，應(yīng)使每組的人數(shù)最少．故求應(yīng)每組人數(shù)的最小值． 解 取其中一組M，設(shè)|M|＝m，用m個點表示組M中的人，若兩人認識，則在相應(yīng)點間連一條線．于是題設(shè)條件可寫為： (a) M中任何一點，與M中其余的點沒有都連線，即設(shè)x∈M，用d(x)表示x在M中的次數(shù)．則d(x)≤m－1． (b) M中沒有連出三角形； (c) 設(shè)x，y∈M．若x，y未連線，則存在唯一z∈M，與x，y均連線． 原題即求證：M中每個點向M中點連的線數(shù)均相等． 由于M中沒有點與其余所有的點都連了線，故存在x，y∈M，且x，y未連線．由(c)存在惟一z∈M，且z與x，y都連了線． ⑴ 記M中除z外與x連線的點集為A，與y

18、連線的點集為B，由(c)，A∩B=?，且由(b)，A、B中任何兩點均不相鄰．對于p∈A，由于p與y不相鄰，則有唯一點與p及y都相鄰，此點必在B中，設(shè)為q，同樣，B中任何一點q￠，也必與A中唯一點p￠相鄰．且若p1、p2∈A，則在B中與它們相鄰的點q1、q2互不相同，否則與(c)矛盾(p1、p2若與B中的q都連線，則它們與兩個不同的點x及q都連了線)．這說明A與B的元素有一一對應(yīng)關(guān)系，|A|=|B|．則d(x)=d(y)． ⑵ 若x，y連線，則由(a)，存在u∈M，u與x未連線，則d(x)=d(u)．若u與y也未連線，則由上證，d(u)=d(x)=d(y)．若u與y連線，則存在v∈M，v與y未

19、連線，d(v)=d(y)，當v與x未連線時，d(x)=d(v)=d(y)；當v與x連線時，由(c)，v與u必不連線，于是d(v)=d(u)，從而d(x)=d(y)．故每組中的人認識本組的人數(shù)相同． ⑶ 為了求分組個數(shù)的最大值，應(yīng)找出滿足條件的組中人數(shù)的最小值，由(a)，有x，y∈M，x與y不相鄰．于是由(c)，存在z∈M，與x、y都相鄰．由(a)，必還有u，u與z不相鄰(否則z與同組的點都相鄰)；于是由(c)，u必與x、y之一相鄰，設(shè)u與x相鄰，于是u與y不相鄰．故又存在v與u、y相鄰．這樣就有了5個點．從而每組至少5個點．而圖中5個點滿足全部要求． 于是至多可分出1990÷5＝398組．

20、 例7 給定平面上的點集P＝{P1，P2，…，P1994}, P中任三點均不共線,將P中的所有的點任意分成83組，使得每組至少有3個點，且每點恰好屬于一組，然后將在同一組的任兩點用一條線段相連，不在同一組的兩點不連線段，這樣得到一個圖案G，不同的分組方式得到不同的圖案，將圖案G中所含的以P中的點為頂點的三角形個數(shù)記為m(G)． (1)求m(G)的最小值m0； (2)設(shè)G*是使m(G*)＝m0的一個圖案，若G*中的線段(指以P的點為端點的線段)用4種顏色染色，每條線段恰好染一種顏色．證明存在一個染色方案，使G*染色后不含以P的點為頂點的三邊顏色相同的三角形．(1994年

21、全國高中數(shù)學(xué)聯(lián)賽) 分析 估計當各組點數(shù)盡可能接近時三角形個數(shù)最少．因此只要證明當兩組點數(shù)差≥2時，不能達到最小值．可以用逐步調(diào)整法來證明．第⑵小問可以用構(gòu)造法來解．注意K5的邊2染色時，可以找到不存在同色三角形的染色法，于是可以據(jù)此構(gòu)造出滿足要求的圖來． 解：設(shè)G中分成的83個子集的元素個數(shù)分別為ni(1≤i≤83)，ni＝1994．且3≤n1≤n2≤…≤n83． 則m(G)= C．即求此式的最小值． 設(shè)nk+1＞nk+1．即nk+1－1≥nk+1．則C＋C－(C＋C)＝C－C＜0．這就是說，當nk+1與nk的差大于1時，可用nk+1－1及nk+1代替nk+1及nk，而其余的

22、數(shù)不變．此時，m(G)的值變?。? 于是可知，只有當各ni的值相差不超過1時，m(G)才能取得最大值． 1994=83×24+2．故當81個組中有24個點，2個組中有25個點時，m(G)達到最小值． m0＝81C＋2C＝81×2024＋2×2300＝168544． ⑵ 取5個點為一小組，按圖1染成a、b二色．這樣的五個小組，如圖2，每個小圓表示一個五點小組．同組間染色如圖1，不同組的點間的連線按圖2染成c、d兩色．這25個點為一組，共得83組．染色法相同．其中81組去掉1個點及與此點相連的所有線．即得一種滿足要求的染色． 例8有n人聚會，已知每人至少認識其中的個人．而對任意的個人，

23、或者其中有兩人認識，或者余下的n－人中有兩人相識．證明：當n≥6時，這n個人中必有3人兩兩認識．(1996年全國聯(lián)賽) 分析 本題與例6類似，要通過分析連線的情況找出三角形來．由于題中給出了，故應(yīng)分n為偶數(shù)或奇數(shù)的情況分別討論． 證明 作一個圖，用n個點表示這n個人，凡二人認識，則在表示此二人的點間連一條線．問題即，在題設(shè)條件下，存在以這n點中的某三點為頂點的三角形．設(shè)點a連線條數(shù)最多，在與a連線的所有點中點b連線最多，與a連線的點除b外的集合為A，與b連線的點除a外的集合為B． 1° 設(shè)n＝2k，則每點至少連k條線，集合A、B中都至少有k－1個點． ⑴若存在一點c，與a、b都連線，則

24、a、b、c滿足要求； ⑵若沒有任何兩點與a、b二點都連線(圖1)，則由A∩B＝?，|A∪B|≤2k－2，|A|≥k－1，|B|≥k－1， 故得 |A|＝|B|＝k－1，且圖中每點都連k條線．若A中任何兩點間均未連線，B中任兩點也未連線，則A∪中不存在兩點連線，B∪{a}中也不存在兩點連線．與已知矛盾．故在A(或B)中必存在兩點，這兩點間連了一條線，則此二點與a(b)連出三角形， 2° 設(shè)n＝2k+1．則每點至少連k條線，A、B中都至少有k－1個點． ⑴若存在一點c，與a、b都連線，則a、b、c滿足要求； ⑵若沒有任何兩點與此二點都連線，且|A|≥k，則由|B|≥k－1(圖2)，

25、A∩B＝?，|A∪B|≤2k－1，可得|A∪B|＝2k－1，|A|＝k，|B|＝k－1，若A中任何兩點間均未連線，B中任兩點也未連線，則A∪中不存在兩點連線，B∪{a}中也不存在兩點連線．與已知矛盾．故A(或B)中存在兩點，這兩點間連了一條線，則此二點與a連出三角形， ⑶若沒有任何兩點與此二點都連線，且|A|＝k－1，即每點都只連k條線．這時，必有一點與a、b均未連線，設(shè)為c (圖3)．c與A中k1個點連線，與B中k2個點連線，k1+k2＝k，且1≤k1，k2≤k－1．否則若k2＝0，則A∪中各點均未連線，B∪{a，c}中各點也未連線．矛盾．故k1，k2≥1．且由于n≥6，則

26、k1＋k2≥3，故k1，k2中至少有一個不小于2，不妨設(shè)k1≥2，現(xiàn)任取B中與c連線的一點b1，由于b1與B中其余各點均未連線，若b1與A中的所有與c連線的點均未連線，則b1連線數(shù)≤2+k－1－k1≤k－1，矛盾，故b1至少與此k1個點中的一點連線．故證． 情景再現(xiàn) 6．在正整數(shù)n與δ滿足什么條件時，可以作出一個n階δ正則圖． 即是：已知n個點，其中某些點間連了一條線，且每個點都恰好與δ個點連了線．問δ可以取什么樣的數(shù)值？ 7． 某次體育比賽，每兩名選手賽一場，每場一定決出勝負，通過比賽確定優(yōu)秀選手，選手A被確定為優(yōu)秀選手的條件為：對任何其他選手B，或A勝B，或存在選手C，有A勝C

27、而C勝B．如果按這個條件確定的優(yōu)秀選手只有1名．求證：這名選手勝所有其余的選手．(1988年中國數(shù)學(xué)冬令營) 8．給定空間中的9個點，任意4點不共面，每兩點間連一線段．求最小的n值，使當對其中任意n條線段用紅、藍兩色之一任意染色時，都一定出現(xiàn)一個三邊同色的三角形．(1992中國數(shù)學(xué)奧林匹克) 習(xí)題13 1．⑴ 如果在偶圖G=(X，Y，E)中，|X|>|Y|，且X中每個頂點的次數(shù)都不小于δ，求證：Y中至少有一個頂點的次數(shù)>δ． ⑵ 若圖G為偶圖，且G有圈，則G的圈的長為偶數(shù)．反之，若圖G有圈，且所有的圈長為偶數(shù)，則G為偶圖． 2．設(shè)C是100階3正則圖，現(xiàn)用紅、白兩色給這100個點

28、著色，其中紅點40個，白點60個，如果一條線的兩個端點都是紅色，則將這條線也染成紅色；如果一條線的兩個端點都是白色，則將這條線也染成白色，現(xiàn)已知紅色線有38條，問白色線有多少條？ 3．若干人相聚，其中有些人彼此認識，若⑴如果某兩個人認識的人數(shù)相等，則他們沒有共同的熟人；⑵有一個人至少有100個熟人．證明：可以找到一個參加聚會的人，他恰好有100個熟人． 4．有2n個學(xué)生，每天出去散步，每兩人一組，如果每一對學(xué)生只在一起散步一次，這樣的散步至多可以持續(xù)多少天？ 5．20名選手參加14場單打比賽，每名選手都至少參加過1場．證明：必有某6場比賽的參賽者是12名不同的選手．(1989年美國數(shù)學(xué)競

29、賽) 6．在n′n棋盤的方格中分別填寫1，2，…，n2(n≥2)，每格一個數(shù)．證明：必有兩個相鄰方格(有公共邊的方格)，方格中的兩個數(shù)的差至少為n．(1988年捷克數(shù)學(xué)競賽) 7．把Kn中的每條線段染上紅色或藍色．把某一點出發(fā)引出兩條同色線段組成的角叫做同色角．證明：同色角的總數(shù)不小于n(n－1)(n－3)． 8．用黑白兩種顏色去涂正九邊形的頂點，每個頂點只涂黑、白兩色之一，證明：在以這九點為頂點的所有三角形中，必有兩個頂點同色的全等三角形． 9．⑴ 將完全圖K5中的10條線段進行染色，使得有公共端點的線顏色不相同．至少要用幾種顏色？ ⑵ 將完全圖K2n中的所有線段染上顏色，使得有公

30、共端點的線顏色不相同．至少要用幾種顏色？ ⑶ 證明：將完全圖K2n－1中的所有線段染上顏色，使得有公共端點的線顏色不相同．至少要用2n－1種顏色． 10．某團體中任意兩個認識的人都沒有共同的熟人，而任意兩個不認識的人都恰有兩個彼此共同的熟人．證明：該團體中每個人認識的人數(shù)都相同．(1975南斯拉夫數(shù)學(xué)競賽) 11．某次體育比賽，每兩名選手各賽一場，無平局．通過比賽確定優(yōu)秀選手．設(shè)A為選手，如果對其他任意選手B，要么A勝B，要么存在選手C，使得A勝C，C勝B，則A即是優(yōu)秀選手．證明：如果按上述規(guī)則選出的優(yōu)秀選手只有1名，則這名選手勝其他所有的選手．(1987年中國數(shù)學(xué)奧林匹克) 12．排

31、球比賽中，每兩隊都各比賽一場．對兩個球隊A與B，如果A勝B，或者存在某個球隊C，使得A勝C，C勝B，則稱A優(yōu)于球隊B．比賽結(jié)束后，優(yōu)于其他所有球隊的球隊即被授予冠軍稱號．比賽結(jié)束后能否恰有兩個冠軍隊？(1988年前蘇聯(lián)數(shù)學(xué)競賽) 本節(jié)“情景再現(xiàn)”解答： 1．證明 任取樹T的一個懸掛點v1，把v1涂紅，所有與v1距離為奇數(shù)的頂點都涂藍，所有與v1距離為偶數(shù)的頂點都涂紅，所有涂紅的頂點組成集合X，所有涂藍的頂點組成集合Y，則得到一個二色圖，即為偶圖． 2．證明 設(shè)G＝(X，Y，E)是偶圖，把X中的點全部涂成紅色，把Y中的點全部涂成藍色，則所得的圖中，相鄰的頂點涂色都不同，即只用2色即可涂

32、完G的所有頂點，使相鄰的頂點涂色不同．又如果G沒有邊，則只用1種顏色即可把G的所有頂點涂好，且沒有任何相鄰的頂點同色(因沒有頂點相鄰)，故偶圖的色數(shù)≤2． 反之若圖G的色數(shù)≤2，若色數(shù)＝1，表示G中任何兩頂點都不相鄰，即G沒有邊，此時，設(shè)G為n階的，可把G中k(1≤k≤n－1)個點涂成一種紅色，另外n－k個點涂成藍色，即得一個二色圖，涂紅的點集為X，涂藍的點集為Y，即為偶圖．若色數(shù)＝2，即用兩種顏色可以把所有頂點涂色，且同色點都不相鄰，則取涂一種顏色的點的集合為X，涂另一種顏色的點的集合為Y，則得到一個偶圖．即色數(shù)≤2的圖是偶圖． 3．證明 n=1時，1條直線把平面分成2部分，可用兩種顏色

33、涂． 設(shè)n=k時，k條直線把平面分成的區(qū)域有滿足題意的涂色法，當n=k+1時，先畫出其中k條直線，而暫把第k+1條直線擦去．這時k條直線把平面分成的區(qū)域可以涂色．涂好色后，把第k+1條直線畫出，凡在這條直線某一側(cè)的部分，涂色不動，而在直線另一側(cè)的部分，把涂的色全部改為另一色，則所得涂色滿足題意．即n=k+1時，命題成立． 綜上可知，命題成立． 4．證明 取每個方格的中心，凡是相鄰的兩個方格，就把相應(yīng)的中心連一條線．這樣得到了一個圖G(圖中紅線組成的圖即為圖G)． 圖G的的直徑=14，，故圖G中任意兩點的距離≤14． 若相鄰兩個方格中填的數(shù)相差<5，則差≤4，于是圖G中所填兩個數(shù)的差≤

34、14×4=56．但圖中填了1與64，此二數(shù)必有一條鏈相連，此鏈的長≤14．即其差≤56，與64－1=63矛盾． 5．證明：以點表示人，紅色線表示認識，藍色線表示不認識． ⑴ 若存在一個點，從這點引出了至少5條紅線，例如從v1向v2，v3，…，v6引出了5條紅線，若v2，v3，…，v6間有某兩點間連了紅線，則這兩點與v1組成紅色三角形，否則此五點間全部連藍色線，為一藍色五邊形． ⑵ 若從任一點引出的紅線都少于5條，則每點引出的藍色線都至少9條．由例如從v1到v2，v3，…，v10均連藍色線，則由例5可知v2，v3，…，v10中或存在紅色三角形或存在藍色四邊形，于是原圖中或有紅色三角形，或此

35、藍色四邊形與v1合成一藍色五邊形．故證． 6．證明：由于共計連了nδ條線．故δ應(yīng)是不超過n－1且使nδ為整數(shù)的那些正整數(shù)值． 反之若正整數(shù)δ不超過n－1，且使nδ為整數(shù)，可構(gòu)造一種連法：取一圓分成n等分． 任取一數(shù)i，滿足1≤i≤，把圓上這n個點中，距離為i的點都連起來，這時當i≠時，每個點都連了2條線，當n為偶數(shù)，且i＝時，每個點都連了1條線． 如果n為奇數(shù)，則δ必須為偶數(shù)：δ＝2k，如果n為偶數(shù)，則δ可為奇數(shù)，也可為偶數(shù)． 若δ=2k＜n，依次取i＝1，2，…，k，按上法連線，則得到每個點都連了2k條線；若δ=2k+1＜n，則按上法連了2k條線，后再取i＝連線，此時每個點又連了1

36、條線，即每個點都連了2k+1條線．于是可知，可以連出滿足要求的圖． 如圖示即是一個16階5正則圖，分別取i=2，4，8畫出． 7．證明：取A為勝場最多者，若A勝所有選手，此時A為優(yōu)秀選手． 若A未全勝，則A必負于某個選手B，此時若找不到C，使A勝C而C勝B，即所有負于A的選手都負于B，則B比A勝場更多，矛盾．故必存在這樣的C勝B．故此時A為優(yōu)秀選手． 若只有1名優(yōu)秀選手，即優(yōu)秀選手只有A，于是其余選手均不是優(yōu)秀選手．若A負于B，由于B不是優(yōu)秀選手，則存在D，D勝A與B，若D不存在．即其余所有選手或負于A，或負于B，則B也為優(yōu)秀選手．故D必存在．現(xiàn)D勝A、B，由于D不是優(yōu)秀選手，同理，故

37、必能找到E，勝A、B、D，…，這樣一直下去，最后必有一人勝所有其余的人，為優(yōu)秀選手，與只有1名優(yōu)秀選手矛盾．故A全勝． 8．解：設(shè)染色的線段至少有33條，則因9個點之間兩兩連線有C＝36條，故不染色的線段至多有3條． 設(shè)點A引出不染色的線段，則去掉點A及所引出的線段．在剩下的點及線段中，若還有點B引出不染色的線段，同樣地再將B及引出的線段去掉，依次進行． 因不染色的線段至多3條，所以至多去掉3個頂點，則還剩下6個頂點，其兩兩連線都染上了紅色或藍色．即得到K6（6階完全圖）圖的2-染色．熟知，存在同色三角形． 其次，存在一個9頂點32條邊的圖，把圖的邊2-染色，可使圖中無同色三角形．如圖

38、所示，將9個點分成5組{V1，V2}、{V3，V4}、{V5，V6}、{V7，V8}、{V9}，兩組間連一條實線表示從這兩組中任取一點都連有紅線；兩組間連一條虛線表示從這兩組中任取一點都連有藍線；每一組內(nèi)部的點之間不連線．該圖構(gòu)成有9個頂點，有C－4＝32條邊，且不存在2-染色的同色三角形．從而，所求的最小n值為33． “習(xí)題68”解答： 1．⑴證明 X中所有點連線的總數(shù)應(yīng)等于Y中所有點連線的總數(shù)． 因X中的點共至少連出了|X|d條線．如果Y中點的次數(shù)都不大于d，則Y中點連出的線的條數(shù)≤|Y|d，由于|X|>|Y|，故|X|d>|Y|d．矛盾． ⑵證明，若G為偶圖，即其頂點可以二染

39、色，使相鄰頂點染色不同，對于G的任一圈，取圈上的任一頂點v1，從v1出發(fā)，沿圈前進，最后回到v1，經(jīng)過的頂點染色為x→y→x→…→y→x(最后回到起點，染色仍為x)，即經(jīng)過了偶數(shù)個頂點，故圈長為偶數(shù)． 若G的所有圈長都為偶數(shù)，不妨設(shè)G為連通的，否則可以分別考慮其連通分支．現(xiàn)取G的任一頂點v，規(guī)定從v到某個頂點v￠的一條鏈長為偶數(shù)時，把v￠染紅，否則把v￠染藍．設(shè)v1為圈上的任一頂點，則從v到v1存在兩個不全同的鏈，由于圈長為偶數(shù)，故此兩個鏈長奇偶性相同，于是每個頂點都可涂成確定的顏色，且相鄰的兩頂點涂成顏色不同．即G為偶圖． 2．解 因為紅色線的兩個端點都是紅色的，所以紅點的度的和3×40

40、＝120中有2×38＝76是與紅色線關(guān)聯(lián)的，另外的120一76＝44個度所關(guān)聯(lián)的線的兩個端點中一個是紅點，另一個是白點，所以白點的度的和3×60＝180中有44是與沒有染上顏色的線關(guān)聯(lián)的．也就是說，有180一44＝136個度是與白色線關(guān)聯(lián)的，所以白色線有136÷2＝68條． 3．證明：在所有的人當中，設(shè)A認識的人最多(如果認識的人數(shù)最多的人有幾個，則任取其中一人為A)． 則A認識的人數(shù)≥100，設(shè)A認識的人為B1，B2，…，Bn (n≥100)，又B1，B2，…，Bn分別認識b1，b2，…，bn人．由于Bi與Bj有共同的熟人A，故Bi與Bj認識的人數(shù)不同，這說明所有bi都互不相等．但所有b

41、i≤n，且由于Bi至少認識A，故bi>0． 所以b1，b2，…，bn恰等于1，2，…，n．但n≥100，故必有某個bi=100． 4．解 由于每人只能與其余2n－1人出去散步一次，故至多可能持續(xù)2n－1天． 為了保證這樣的散步可以安排，可以畫一個圓，把這個圓分成2n－1等分．把圓心袤為1，圓上的分點依次記為2，3，…，2n，先畫出一批弦：把1與2連起來，再連3與2n，4與2n－1，…，即把過3，4，…，n－1，n，n+1而與1，2連線垂直的弦連出，連線的兩人第一天出去散步，把這些連線繞1旋轉(zhuǎn)，連線的人(1與3，4與2，5與2n，…，)第二天散步，以后每天都是繞1旋轉(zhuǎn)，…，這樣經(jīng)過2n－1

42、天，每個人都與其余2n－1個人出去散步一次．即終止．(圖中連的實線表示第一天，虛線表示第二天，……) 除2n外，第i天，若k+m≡i(mod 2n－1)，(1≤k，m≤2n－1)，則k與m配對，而2n與余下1人配對． 這只要證明：對于每個k(1≤k≤2n－1)，與之配對的元素每天都不同，對于2n，每天與之配對的元素也不同． 5．解：用20個點表示這20個人，若某兩人比賽過就在表示這兩人的點間連1條線，題意即：已連了14條線，每點至少連了1條線．求證：有6條線，連的12個點互不相同． 設(shè)此20個點的度分別為d1，d2，…，d20，則d1+d2+…+d20=28． 把度為di的頂點處連接

43、的di－1條邊刪去．則至多刪去了(d1－1)+(d2－1)+…+(d20－1)=28－20=8條邊， 于是還剩下6條邊，但每個頂點的度≤1．即此6條邊連接12個頂點． 6．解：反設(shè)任何相鄰方格中寫的數(shù)都≤n－1． 取Ak={1，2，…，k}(1≤k≤n2－n)，Bk=(k+n，k+n+1，…，n2}，Ck={k+1，k+2，…，k+n－1}，則Ak，Bk元素不能相鄰．它們只能與Ck的元素相鄰．由于|Ck|=n－1，故必有一行及一列沒有Ck中的元素．這一行及這一列中只能是Ak的元或只能是Bk中的元．由Ak與Bk中的元不能相鄰，于是這一行及這一列必全為Ak中的元，或者全為Bk中的元． 對于

44、k=1，由于A1只有一個元，故相應(yīng)行與列中的元應(yīng)全是B1中的元，對于k=2，…，n－1，均有相同的結(jié)論即存在一行及一列全是Bk的元．而對于k=n2－2n+1，n2－2n+2，…n2－n，則存在一行及一列，全是Ak的元．即存在l，使B1，B2，Bl中的元能占滿一行及一列，而Al+1中的元則占了一行及一列．此兩行與兩列相交處的方格中的元即是Bl的元，又是Al+1的元．設(shè)為a則a∈{1，2，…，k+1}，且a∈{k+n，k+n+1，…n2}．由于n≥2，這是不可能的．故證． 7．證明：設(shè)從頂點Vi引出xi條紅線，n－1－xi條藍線，則從Vi共引出C個角，其中異色角有xi(n－1－xi)個，但xi(

45、n－1－xi)≤(n－1)2，故每個頂點引出同色角數(shù)≥(n－1)(n－2)－(n－1)2＝(n－1)(n－3)． 故同色角總數(shù)≥n(n－1)(n－3)． 8．證明：任意兩個頂點連線的中垂線必經(jīng)過另一個頂點，且除此3點外的另6點可分成3對，每對的兩個點關(guān)于這條中垂線對稱． 9個點涂成兩種顏色，必有一種顏色的點不超過4個，不妨設(shè)白點不超過4個． 設(shè)白點只有3個，取任意2個白點，除這兩個白點、這兩個白點的中垂線上的頂點及第3個白點與它關(guān)于這條中垂線的對稱點，余下2對對稱點中都是黑點，此4個黑點就可連出兩個全等三角形． 若白點有4個，這4個白點間可連6條線段，這6條連線的中垂線上的頂點有6個

46、．但紅點只有5個，故或者某條中垂線經(jīng)過白點，即化為上一情形；或有某兩條中垂線過同一個紅點，于是，相應(yīng)的白點連線平行，故此4個白點可以連出兩個全等三角形． 9⑴解：由于從一點出發(fā)了4條線，故至少要4色，下面說明4色不夠：考慮從V1、V2連顏色a，則V3、V4、V5只有兩種可能連法(實質(zhì)相同)，如左圖．此時V3V4、V5V4兩條中必有一條無法染色，即需要至少5色，而5色可以染，只要作圖即得(如右圖)． ⑵證明：每點引出2n－1條線，即至少2n－1色，即色數(shù)≥2n－1． 又對于2n個點，可排出表：把點編號0，1，2，…，2n－1．把圓2n－1等分，0放在圓心，其余各號排成一圈，0與k連線及所有

47、與此連線垂直的弦用第k種顏色染，這樣2n－1種顏色即能染成．故證． ⑶ 證明：⑴由于K2n可用2n－1種顏色染色，故去掉其中一個頂點及其所連的邊，得到K2n－1，也可用2n－1種顏色染成．即所需色數(shù)≤2n－1． 若只用2n－2色，由于圖中共有(2n－1)(2n－2)條線，于是必有一種顏色染了[(2n－1)(2n－2)÷2]+1=n條線，這n條線若無公共頂點，則有2n個頂點，而此圖只有2n－1個頂點，故2n－2色不夠．故所需色數(shù)>2n－2．從而必須用2n－1色．證畢． 10．解：以n個點表示該團體中的人，兩人認識，則在表示兩人的點間連一條線，問題是：若兩點連了線，則它們不能與同一第三點連

48、線，即不出現(xiàn)三角形，若兩點間未連線，則它們恰與另兩個點都連了線． 首先證明任意兩個連線的點的次數(shù)相同．設(shè)AB連線，則它們除彼此外沒有連向同一點，設(shè)A與A1，…，Ak連了線，則A1，…，Ak間均不連線，B與A1，…，Ak均不連線．此時B與Ai除A外必還有一點連線，設(shè)為Bi，且Bi與Bj不同，否則A、Bi與3點都連了線．于是與Ai對應(yīng)的與B連線的點有k個．即|B|≥|A|，同理，|A|≥|B|．即|A|=|B|． 其次，若C、D未連線，則C、D都與E、F連線，則|C|=|E|，|D|=|E|，于是|C|=|E|=|F|．于是得證． 11．證明：取A為勝場最多者，則或A勝所有選手，此時A為優(yōu)秀

49、選手． 若A未全勝，則A必負于某個選手B，此時若找不到C，使A勝C而C勝B，即所有負于A的選手都負于B，則B比A勝場更多，矛盾．故必存在這樣的C勝B．故此時A為優(yōu)秀選手． 若只有1名優(yōu)秀選手，即優(yōu)秀選手只有A，于是其余選手均不是優(yōu)秀選手．若A負于B，由于B不是優(yōu)秀選手，則存在D，D勝A與B，若D不存在．即其余所有選手或負于A，或負于B，則B也為優(yōu)秀選手．故D必存在．現(xiàn)D勝A、B，由于D不是優(yōu)秀選手，同理，故必能找到E，勝A、B、D，…，這樣一直下去，最后必有一人勝所有其余的人，為優(yōu)秀選手，與只有1名優(yōu)秀選手矛盾．故A全勝． 12．解：首先證明：按此規(guī)則，至少有1個冠軍：若A全勝，則A必為

50、冠軍．若無人全勝，設(shè)A為勝場最多者，把余下的隊分成兩個集合：M={勝A的隊}，N={負于A的隊}．設(shè)B∈M，則可在N中找到C，使C勝B，反N中設(shè)找不到勝B的隊，則B勝N中所有的隊，于是B比A的勝場至少多1．與A的假設(shè)矛盾．故A優(yōu)于M中所有的隊，又A又優(yōu)于N中所有的隊，故A為冠軍． 設(shè)有兩個球隊都得了冠軍．不妨設(shè)為A與B，A與B必比賽，設(shè)A勝B，由于B也優(yōu)于A，故存在C使B勝C而C勝A．取勝A但負于B的隊的集合S，則由C的存在，S1?．及勝A又勝B的集合T．再取所有負于A的隊的集合M，于是S∪T∪M∪{A，B}即為全體參賽隊． 若T非空，則由于T是每兩隊也要比賽1場，故也可找出T中的冠軍隊D，D優(yōu)于T中每個隊．由于D勝B，故T優(yōu)于B及S中的每個隊，T勝A，故T優(yōu)于A及M中所有的隊．于是T也為全部隊的冠軍．與恰有兩個冠軍隊的假設(shè)矛盾．故T=?． 于是，用同樣的方法可知：S中也將產(chǎn)生冠軍隊，該冠軍隊也是全部隊的冠軍，矛盾．故不可能恰有兩個冠軍隊．