數(shù)學(xué)競賽：圖論講義

數(shù)學(xué)競賽：圖論講義大連市第二十四中學(xué)邰海峰重要的概念與定理完全圖每兩個頂點之間均有邊相連的簡單圖稱為完全圖,有個頂點的完全圖(階完全圖)記為.頂點的度圖中與頂點相關(guān)聯(lián)的邊數(shù)(環(huán)按2條邊計算)稱為頂點的度(或次數(shù)),記為.與分別表示圖的頂點的最小度與最大度.度為奇數(shù)的頂點稱為奇頂點,度為偶數(shù)的頂點稱為偶頂點.樹沒有圈的連通圖稱為樹,用表示,其中度為1的頂點稱為樹葉(或懸掛點).階樹常表示為.部圖假設(shè)圖的頂點集可以分解為個兩兩不相交的非空子集的并,即并且同一子集內(nèi)任何兩個頂點沒有邊相連,那么稱這樣的圖為部圖,記作.2部圖又叫做偶圖,記為.完全部圖在一個部圖中,,假設(shè)對任意均有邊連接和,那么稱圖為完全部圖,記為.歐拉跡包含圖中所有邊的跡稱為歐拉跡.起點與終點重合的歐拉跡稱為閉歐拉跡.歐拉圖包含歐拉跡的圖為歐拉圖.歐拉圖必是連通圖.哈密頓鏈(圈)經(jīng)過圖上各頂點一次并且僅僅一次的鏈(圈)稱為哈密頓鏈(圈).包含哈密頓圈的圖稱為哈密頓圖.平面圖假設(shè)一個圖可畫在平面上,即可作一個與同構(gòu)的圖,使的頂點與邊在同一平面內(nèi),且任意兩邊僅在端點相交,那么圖稱為平面圖.一個平面圖的頂點和邊把一個平面分成假設(shè)干個互相隔開的區(qū)域,稱為平面圖的一個面,在所有邊的外面的面稱為外部面,其余的稱為內(nèi)部面.競賽圖有向完全簡單圖稱為競賽圖.有個頂點的競賽圖記作.有向路在有向圖中,一個由不同的弧組成的序列,其中的起點為,終點為,稱這個序列為從到的有向路(簡稱路),為這個路的長,為路的起點,為路的終點.假設(shè),那么稱這個路為回路.定理1設(shè)是階圖,那么中個頂點的度之和為邊數(shù)的2倍.定理2對于任意圖,奇頂點的個數(shù)一定是偶數(shù).定理3(Turan定理)有個頂點且不含三角形的圖的最大邊數(shù)為.定理4圖為偶圖,當(dāng)且僅當(dāng)中不含長度為奇數(shù)的圈.定理5假設(shè)樹的頂點數(shù),那么中至少有兩個樹葉.定理6假設(shè)數(shù)有個頂點,那么的邊數(shù).定理7設(shè)是有個頂點、條邊的圖,那么以下命題等價:⑴圖是樹;⑵圖無圈,且;⑶圖連通,且.定理8階連通圖中以樹的邊數(shù)最少,且階連通圖必有一個子圖是樹.定理9(一筆畫定理)有限圖是一條鏈或圈(可以一筆畫成)的充要條件是是連通的,且奇頂點的個數(shù)為0或2.當(dāng)且僅當(dāng)奇頂點個數(shù)為0時,連通圖是一個圈.定理10在偶圖中,假設(shè),那么一定無哈密頓圈.假設(shè)與的差大于1,那么一定無哈密頓鏈.定理11設(shè)是階簡單圖,且對每一對頂點有,那么圖有哈密頓鏈.定理12設(shè)是階簡單圖,且對每一對不相鄰的頂點有,那么圖有哈密頓圈.定理13設(shè)是階簡單圖,假設(shè)每個頂點的度,那么圖有哈密頓圈.定理14假設(shè)圖有哈密頓圈,從中去掉假設(shè)干個點及與它們關(guān)聯(lián)的邊得到圖,那么圖的連通分支不超過個.定理15(歐拉公式)假設(shè)一個連通的平面圖有個頂點、條邊、個面,那么.定理16一個連通的平面簡單圖有個頂點、條邊,那么,對于連通的偶圖,那么有.定理17一個圖是平面圖當(dāng)且僅當(dāng)它不包含同胚于或的子圖.定理18設(shè)階競賽圖的頂點為,那么,且.定理19競賽圖中出度最大的點稱為“優(yōu)點”,“優(yōu)點”到其余各點都有長度不超過2的鏈.定理20競賽圖中存在一條長為的哈密頓路.定理21競賽圖中有一個回路是三角形的充要條件是有兩個頂點滿足.定理22(Ramsey定理)任意2色完全圖中必存在同色三角形.例題選講例1某天晚上21個人之間通了,有人發(fā)現(xiàn)這21人共通話102次,且每兩人至多通話一次.他還發(fā)現(xiàn),存在個人,第1個人與第2個人通了話,第2個人與第3個人通了話,……,第個人與第個人通了話,第個人又與第1個人通了話,他不肯透露的具體值,只說是奇數(shù).求證:21個人中必存在3人,他們兩兩通了話.證：用21個點表示21個人,假設(shè)兩人通那么對應(yīng)兩點連一條邊,構(gòu)成圖.由,中存在一個長度為的奇圈.要證:中存在三角形.設(shè)圖中長度最短的奇圈為,長度為.假設(shè),那么為三角形.假設(shè),設(shè)為,那么與之間無邊(),否那么,假設(shè)與相鄰,那么圈與圈長度之和為,故其中必然有一個長度小于的奇圈,與最短矛盾.假設(shè)除外的個點無三角形,由Turan定理,它們至多連了條邊.又其中任意一點不與的相鄰兩點相鄰(否那么存在三角形),所以它至多與中個點相鄰.故總邊數(shù)為().與圖共有102條邊矛盾.故圖中存在三角形,即存在三個人兩兩通話.例245個校友聚會,在這些人中,任意兩個熟人數(shù)目相同的校友互不認(rèn)識.問在參加校友聚會的所有人中,熟人最多的人的數(shù)目最多是多少?解:用45個點表示45個人,假設(shè)兩人認(rèn)識,那么對應(yīng)兩點間連一條邊,得圖.設(shè)共有個人熟人最多,每人有個熟人,這些人對應(yīng)的點構(gòu)成集合,其余的人對應(yīng)點構(gòu)成集合,顯然,.由題意知,中任何兩點不相鄰,且,中各頂點的度的最大值.下面證明:.假設(shè),那么中至少有23個點,每點的度為,且任意兩點不相鄰,那么從中發(fā)出的另一端是中點的邊共有條,而.所以,中至少有一個點的度大于,與矛盾.當(dāng)時,構(gòu)造完全偶圖,滿足題意.故熟人最多的人數(shù)最多為22人.例3在17名科學(xué)家中，每人都和其它人通信．在他們的通信中只討論三個題目．而且任意兩名科學(xué)家通信時，只討論一個題目．證明，其中至少有三名科學(xué)家，他們相互通信時，討論的是同一個題目．證:用頂點代表科學(xué)家,兩人相互通信那么連上一條邊.假設(shè)兩人在通信中討論第個題目,那么在此邊上染上第種顏色.在這個三色完全圖中,任取一個頂點,從它出發(fā)的16條邊中，至少有染上某一種顏色(設(shè)為第種顏色)的邊的數(shù)目不小于6．從其中取出6條第種顏色的邊,如果這些邊的另一端點所構(gòu)成的子圖中含第色邊，這就構(gòu)成第色三角形.否那么,就是兩色完全圖,由Ramsey定理知，其中必有單色三角形．這就是說，有三位科學(xué)家在通信中討論的是同一題目．證畢．例4設(shè)個新生中,任意3個人中有2個人互相認(rèn)識,任意4個人中有2個人互不認(rèn)識,求的最大值.A1A2A3A4A1A2A3A4A5A6A7A8兩點相鄰當(dāng)且僅當(dāng)兩人認(rèn)識.下面設(shè)個學(xué)生滿足題設(shè)要求,證明.為此,先證明如下兩種情況不可能出現(xiàn).⑴假設(shè)某人至少認(rèn)識6個人,記為.由Ramsey定理知,這6個人中或存在3個人互不認(rèn)識(與任意3個人中有2個人互相認(rèn)識矛盾),或存在3個人互相認(rèn)識,這時,與這3個人共4個人兩兩互相認(rèn)識,與矛盾.⑵假設(shè)某人至多認(rèn)識個人,那么剩下至少4個人均與互不認(rèn)識,從而,這4個人兩兩認(rèn)識,與矛盾.當(dāng)時,⑴與⑵必有一種情況出現(xiàn),故此時不滿足要求.當(dāng)時,要使⑴與⑵都不出現(xiàn),那么此時每個人恰好認(rèn)識其他5個人,于是,這9個人產(chǎn)生的“朋友對”的數(shù)目為,矛盾.由上述討論知,.綜上,的最大值為8.例5設(shè)是整數(shù),在一次會議上有位數(shù)學(xué)家,每一對數(shù)學(xué)家只能用會議規(guī)定的種辦公語言之一進(jìn)行交流,對于任意3種不同的辦公語言,都存在3位數(shù)學(xué)家用這3種語言互相交流.求所有可能的,并證明你的結(jié)論.證:當(dāng)位奇數(shù)時,結(jié)論成立.原命題等價于將完全圖的邊染以種顏色之一,使得對于任意3種顏色,都存在3個頂點,它們相互所連的邊為這3種顏色.由于種顏色有種選取方法,而頂點也有種選取方法,這就意味著每3個頂點相連的邊一定被染為確定的3種顏色,不能染為其他情況的顏色,反之亦然.特別地,對于每一個三角形其3條邊為3種不同顏色.固定顏色,恰好有個三角形,其有一條邊為顏色,而顏色為的邊可以與其他個頂點構(gòu)成個三角形.于是,有條邊被染為顏色.所以,不能為偶數(shù).當(dāng)為奇數(shù)時,將個頂點分別記為頂點,種顏色記為,連結(jié)頂點的邊染為顏色,其中.那么對于任意3種顏色,有同余方程組.利用消元法,可得在內(nèi)有唯一的解,且互不相同.所以,對于任意3種顏色,存在唯一的三角形,其3條邊的顏色為這3種顏色.例6一個元素都是0或1的方陣稱為二進(jìn)制方陣.假設(shè)二進(jìn)制方陣其主對角線〔左上角到右下角的對角線〕以上〔不包括主對角線〕的元素都相同，而且主對角線以下〔不包括主對角線〕的元素也相同，那么稱它為一個“好方陣”.給定正整數(shù).證明：存在一個正整數(shù)，使得對任意正整數(shù)和給定的二進(jìn)制方陣,可選出整數(shù)，從中刪除第行和第列后所得到的二進(jìn)制方陣是“好方陣”.證:記中第i行，第j列的元素為，表示n階完全圖.我們對的邊按如下方式染色：對于連接頂點的邊⑴假設(shè)，那么染紅色；⑵假設(shè)，那么染綠色；⑶假設(shè)，那么染藍(lán)色；⑷假設(shè)，那么染白色.按照上面的染色方式，那么一個單色完全子圖對應(yīng)于的一個“好子方陣”.事實上，假設(shè)是的頂點，我們可以刪去指標(biāo)的行和列，得到一個“好子方陣”.我們只需取使得，對任何，四染色的必定包含一個單色子圖.根據(jù)Ramsey定理，我們可取即可.例7現(xiàn)有十個互不相同的非零數(shù).現(xiàn)知它們之中任意兩個數(shù)的和或積是有理數(shù).證明:每個數(shù)的平方都是有理數(shù).證:考查其中任意6個數(shù).作一個圖,在它的6個頂點上分別放上我們的6個數(shù).如果某兩個數(shù)的和為有理數(shù),就在相應(yīng)的兩個頂點之間連一條藍(lán)邊;如果某兩個數(shù)的積為有理數(shù),就在相應(yīng)的兩個頂點之間連一條紅邊.由Ramsey定理,此圖中存在一個同色三角形.⑴假設(shè)存在藍(lán)色三角形,那么說明存在三個數(shù),使得都是有理數(shù).因而為有理數(shù),亦即為有理數(shù).同理可知和也都是有理數(shù).此時我們再來觀察其余的任意一個數(shù).顯然,無論由的有理性(由,所有的數(shù)均非0),還是由的有理性,都可以推出為有理數(shù).所以此時10個數(shù)都是有理數(shù).⑵假設(shè)存在紅色三角形,那么說明存在三個數(shù),使得都是有理數(shù).因而為有理數(shù),同理可知和也都是有理數(shù).如果三者中至少有一個為有理數(shù),那么只要按照前一種情況進(jìn)行討論,即可得知我們的10個數(shù)都是有理數(shù).現(xiàn)在設(shè),其中為有理數(shù),而.由于是有理數(shù),所以,其中為有理數(shù).再觀察其余的任意一個數(shù),假設(shè)或為有理數(shù),那么經(jīng)過與上述類似的討論,可知,其中為有理數(shù),因而為有理數(shù).而假設(shè)與都是有理數(shù),那么是有理數(shù),但為無理數(shù),矛盾.綜上,我們已證或者每個數(shù)都是有理數(shù),或者每個數(shù)的平方都是有理數(shù).練習(xí)1.旅行團(tuán)一行6人到一個城市觀光,此城市開放15個景點,每人可選擇假設(shè)干個景點參觀(亦可不選或全選).求證:或者必有3人,他們選擇的景點各不相同;或者必有4人,在他們選擇的景點中有相同的.2.設(shè)一次至少有5人參加的循環(huán)賽的結(jié)果滿足如下條件:假設(shè)A勝B,那么勝A而負(fù)于B的人數(shù)不少于勝B而負(fù)于A的人數(shù).證明:對任意兩人,總有另外兩人,使得假設(shè)勝,那么勝、勝、勝.3．在一個足球聯(lián)賽里有20支球隊.第一輪它們分成10對互相比賽,第二輪也分成10對互相比賽(每支球隊兩輪比賽的對手不一定不同).求證:在第三輪開賽之前,一定可以找到10支球隊,它們兩兩沒有比賽過.4.某國際社團(tuán)共有1978名成員，他們來自六個國家,用號碼給成員編號．證明至少有一名成員,他的編號是他的某個同胞的2倍,或者是兩位同胞編號之和．練習(xí)題答案1.證:用6個點表示6個人,再用15個點表示15個景點.假設(shè)某人選擇了某個景點,那么在相應(yīng)兩點之間連一條邊,得一偶圖.以表示點在圖中的鄰域,它表示第個人選擇的景點的集合().假設(shè)結(jié)論不真,那么⑴任意三個有公共元,且⑵任意四個無公共元.由⑴知,對每個,在中每取兩個與的交均非空,故可確定的一個元素,用這樣的方式可確定個元素.由⑵知,這些元素各不相同,故每個至少有個不同的元素.對每個這樣做,得到個元素.又由⑵知,每個元素至多是3個的公共元,故每個元素至多重復(fù)計算3次.故其中不同的元素至少有個,即至少有20個景點,矛盾.2.證：由題意知,假設(shè)A勝B且存在勝B而負(fù)于A的人,那么必存在勝A而負(fù)于B的人.任取兩選手且勝,分三種情況討論:⑴假設(shè)存在勝且有勝而負(fù)于,根據(jù)條件,存在勝而負(fù)于;⑵假設(shè)存在同時負(fù)于,那么勝而同時勝,同情形⑴;⑶假設(shè)不存在有同時勝(或同時負(fù)于)的人,在其余3人中,勝而負(fù)于的至少有2人,設(shè)為,且勝,那么符合題意.3.證:用20個點表示20個球隊,第一輪互相賽過的隊之間連紅線,第二輪互相賽過的隊之間連藍(lán)線,那么每個點都連有一紅一藍(lán)兩條邊,從而整個圖必由一個或假設(shè)干個偶圈組成.在每個偶圈中可以選出半數(shù)定點,任兩個不相鄰,共選出10支球隊,兩兩未賽過.4.證:用頂點表示成員，并加上編號．于是任意兩頂點編號差大于0而小于1978．如果這個差是第國成員的編號，那么將邊染上第種顏色,這樣我們就用六種顏色染了的所有邊.以下首先證明,六色完全圖中必定含有單色三角形．

取的任一頂點,與它關(guān)聯(lián)的1977條邊分為6種顏色，于是其中必有一種顏色的邊至少有條.不妨設(shè)是色邊．如果中以為頂點的完全子圖中含有色邊,那么