離散數(shù)學(xué)圖論第1頁，共65頁，2023年，2月20日，星期一圖論抽象的圖一個圖G是一個三元組〈V(G),E(G),φG〉，其中V(G)是一個非空的結(jié)點集合，E(G)是邊集合，φG是從邊集合到結(jié)點集合的函數(shù)。如果把φG總是看成是結(jié)點之間的一種關(guān)聯(lián)，并在E(G)中清楚地描述這種關(guān)聯(lián)，那么一個圖G通常簡記為一個二元組序偶形式G=〈V，E〉，其中V是一個非空結(jié)點集合，E是連接結(jié)點的邊的集合。第2頁，共65頁，2023年，2月20日，星期一圖論圖的抽象性及方向性圖的結(jié)點與連接都是一種抽象的表示，其位置與長度沒有意義。如果邊是兩個結(jié)點之間的有序偶，則稱該邊是有向邊，記為〈vi,vj〉。包含有向邊的圖為有向圖。如果邊是兩個結(jié)點之間的無序偶，則稱該邊為無向邊，記為（vi,vj

）。包含無向邊的圖為無向圖。注意：既有有向邊又有無向邊的圖稱為混合圖。第3頁，共65頁，2023年，2月20日，星期一圖論鄰接點與特殊的圖在一個圖中，若兩個結(jié)點由一條邊關(guān)聯(lián)，則稱這兩結(jié)點是鄰接點。不與其它任何結(jié)點相關(guān)聯(lián)的結(jié)點稱為孤立結(jié)點。僅由孤立結(jié)點組成的圖稱為零圖。僅由一個結(jié)點組成的圖稱為平凡圖。任意兩個結(jié)點都相鄰的圖稱為完全圖。第4頁，共65頁，2023年，2月20日，星期一圖論思考有n個結(jié)點的無向完全圖Kn有多少條邊？有向圖的情形呢？第5頁，共65頁，2023年，2月20日，星期一圖論鄰接邊關(guān)聯(lián)于同一結(jié)點的兩條不同的邊則稱為鄰接邊。關(guān)聯(lián)于同一結(jié)點的兩條相同的邊則稱為自回路或環(huán)。環(huán)既可以是有向的，也可以是無向的。第6頁，共65頁，2023年，2月20日，星期一圖論有向圖的度設(shè)〈vi,vj〉是有向圖G=〈V，E〉中的任意一條有向邊，vi是該邊的起始結(jié)點，vj是終止結(jié)點。在有向圖G=〈V，E〉中，以一結(jié)點為起始結(jié)點的邊的個數(shù)稱為該結(jié)點的出度；以一結(jié)點為終止結(jié)點的邊的個數(shù)稱為該結(jié)點的入度。一結(jié)點的出度和入度之和稱為該結(jié)點的度數(shù)，記作deg(v)。第7頁，共65頁，2023年，2月20日，星期一圖論有向圖度數(shù)的性質(zhì)在任何有向圖中，所有結(jié)點的入度之和等于所有結(jié)點的出度之和，并等于圖中邊的個數(shù)。孤立結(jié)點的入度和出度均為0有向環(huán)的對應(yīng)結(jié)點的入度和出度均增加1第8頁，共65頁，2023年，2月20日，星期一圖論無向圖的度在無向圖G=〈V，E〉中，與結(jié)點相關(guān)聯(lián)的邊的個數(shù)稱為該結(jié)點的度數(shù)，記作deg(v)。在無向圖G=〈V，E〉中，結(jié)點度數(shù)的總和是邊數(shù)的兩倍。在無向圖G=〈V，E〉中，度數(shù)為奇數(shù)的結(jié)點必定是偶數(shù)個。第9頁，共65頁，2023年，2月20日，星期一圖論補圖給定一個圖G=〈V，E〉，構(gòu)造另一個圖，它的結(jié)點集合與G相同，而邊的集合則為相同完全圖中邊集合與E的差集，稱該圖為原圖G相對于完全圖的補圖，記作~G。第10頁，共65頁，2023年，2月20日，星期一圖論子圖設(shè)G=〈V，E〉是一個圖，如果有另一個圖G‘=〈V’，E‘〉，使得V’是V的子集，E‘是E的子集，則稱G‘是G的子圖。如果G的子圖G‘包含G的所有結(jié)點，則稱該子圖為G的生成子圖。第11頁，共65頁，2023年，2月20日，星期一圖論差圖設(shè)G‘=〈V’，E‘〉是G=〈V，E〉的子圖，若給定另外一個子圖G“=〈V”，E“〉使得E“=E-E‘

，且V”中僅包含E“的邊所關(guān)聯(lián)的結(jié)點，則稱G“是圖G與子圖G‘的差圖，或稱子圖G‘相對于圖G的補圖，記作

G“=G-G‘

。顯然，同時有G‘=G-G“

。第12頁，共65頁，2023年，2月20日，星期一圖論圖的同構(gòu)設(shè)G=〈V，E〉和G‘=〈V’，E‘〉都是圖，且兩個圖的結(jié)點和邊分別存在一一對應(yīng)關(guān)系，且保持相應(yīng)的關(guān)聯(lián)，則稱兩個圖同構(gòu)。兩個圖同構(gòu)說明一個圖的兩種畫法。第13頁，共65頁，2023年，2月20日，星期一圖論路與回路設(shè)G=〈V，E〉是圖，v0,v1,…,vn

∈V，e1,e2,…,en∈E,其中ei=<vi-1,vi>,交替序列v0e1v1e2…envn稱為從v0連接到vn的路。v0是此路的起點，vn是此路的終點。路中邊的數(shù)目是此路的長度。當(dāng)起點與終點相等時，此路稱為回路。注意：對于簡單圖的情形，可以僅用結(jié)點序列或邊序列來表示路或回路。第14頁，共65頁，2023年，2月20日，星期一圖論特殊的路與回路跡：路中所有的邊均不相同；通路：路中所有的結(jié)點均不相同；圈：回路中除起點與終點外的結(jié)點均不相同；第15頁，共65頁，2023年，2月20日，星期一圖論路的性質(zhì)在一個具有n個結(jié)點的圖中，如果從結(jié)點vj到結(jié)點vk存在一條路，則從結(jié)點vj到結(jié)點vk一定存在一條不多于n-1條邊的路，即存在一條邊數(shù)小于n的通路。此結(jié)論對于有向圖和無向圖都適用嗎？第16頁，共65頁，2023年，2月20日，星期一圖論無向圖的連通性在無向圖G中，結(jié)點u和v之間如果存在一條路，則稱這兩個結(jié)點是連通的。如果G中任意兩個結(jié)點之間都連通，那么稱圖G為連通圖。第17頁，共65頁，2023年，2月20日，星期一圖論無向圖的連通分支如果無向圖G不連通，而G1是G的子圖，且G1是連通的，則稱G1是G的一個連通子圖。如果連通子圖G1是最大的連通子圖，即增加任意一個G中的結(jié)點到G1，將使得G1成為不連通，那么稱G1是G的一個連通分支。G的連通分支的個數(shù)記為w(G)。一個無向圖G是連通的當(dāng)且僅當(dāng)w(G)=1。第18頁，共65頁，2023年，2月20日，星期一圖論思考結(jié)點的連通性是結(jié)點集V上的一個等價關(guān)系！連通性所劃分的等價類是什么？第19頁，共65頁，2023年，2月20日，星期一圖論點割集設(shè)無向圖G〈V，E〉為連通圖，若有點集V1是V的真子集，使得圖G在刪除了V1中所有結(jié)點后，所得的子圖是不連通的，而在刪除了V1的任意真子集后，所得的子圖仍然是連通的，則稱V1是G的一個點割集；如點割集中僅有一個結(jié)點則稱此結(jié)點為割點。第20頁，共65頁，2023年，2月20日，星期一圖論割點的判定設(shè)無向圖G=〈V，E〉是連通圖，結(jié)點v是G的割點的充要條件是存在結(jié)點u和w，使得u和w的每一條路都經(jīng)過結(jié)點v.第21頁，共65頁，2023年，2月20日，星期一圖論點連通度若G是不完全圖，定義點連通度k(G)為結(jié)點數(shù)最少的點割集的結(jié)點數(shù)，即從G中最少刪除k(G)個結(jié)點后，圖G即成為不連通。注意：若G不連通，則k(G)=0；若G存在割點，則k(G)=1；規(guī)定完全圖Kp的k(Kp)=p-1（為什么？）。第22頁，共65頁，2023年，2月20日，星期一圖論邊割集設(shè)無向圖G=〈V，E〉為連通圖，若有邊集E1是E的真子集，使得圖G在刪除了E1中所有邊后，所得的子圖是不連通的，而在刪除了E1的任意真子集后，所得的子圖仍然是連通的，則稱E1是G的一個邊割集；如邊割集中僅有一條邊則稱此邊為割邊（或稱為橋），即使得w(G-e)>w(G).第23頁，共65頁，2023年，2月20日，星期一圖論邊連通度設(shè)G是不完全圖，G的邊連通度λ(G)為邊數(shù)最少的邊割集的邊數(shù)，即從G中刪除λ(G)條邊后圖G即成為不連通。若G不連通，則λ(G)=0；若G存在割邊，則λ(G)=1；若G是平凡圖，則λ(G)=0；若G是完全圖Kp，則λ(Kp)=p-1。第24頁，共65頁，2023年，2月20日，星期一圖論點連通度與邊連通度的性質(zhì)對于任何一個無向圖G，有k(G)≤λ(G)。第25頁，共65頁，2023年，2月20日，星期一圖論有向圖中結(jié)點之間的可達性設(shè)G=〈V，E〉是有向圖，若存在從結(jié)點u到結(jié)點v的一條路，則稱從u可達v。顯然，可達不一定是雙向的！比較：無向圖中結(jié)點之間的連通性與有向圖中結(jié)點的可達性注意：可達性只有自反性和傳遞性，所以它不是等價關(guān)系！第26頁，共65頁，2023年，2月20日，星期一圖論有向圖的連通性在一個有向圖G=〈V，E〉中，（1）任意兩個結(jié)點之間都是互相可達的，則稱G是強連通的；（2）任意兩個結(jié)點之間至少從一個結(jié)點到另外一個結(jié)點是可達的，則稱圖G是單連通的；（3）如果在G中刪除邊的方向而得到的無向圖是連通的，則稱G是弱連通的。第27頁，共65頁，2023年，2月20日，星期一圖論有向圖的連通分支設(shè)G=〈V，E〉是有向圖，（1）G1是具有強連通性質(zhì)的最大子圖，則稱G1是G的強連通分支（強分圖）；（2）G1是具有單連通性質(zhì)的最大子圖，則稱G1是G的單連通分支（單分圖）；（3）G1是具有弱連通性質(zhì)的最大子圖，則稱G1是G的弱連通分支（弱分圖）。第28頁，共65頁，2023年，2月20日，星期一圖論強連通有向圖的性質(zhì)一個有向圖G是強連通的，當(dāng)且僅當(dāng)G中有一個回路，它至少包含每個結(jié)點一次。一個有向圖G的每一個結(jié)點位于且僅位于G的一個強連通分支中。第29頁，共65頁，2023年，2月20日，星期一圖論圖的矩陣表示回憶：關(guān)系的鄰接矩陣表示。設(shè)G=〈V，E〉是圖，V={v1,v2,…,vn}，建立n階方陣A(G)=(aij)，使得

aij=1，vi與vj鄰接；

aij=0，否則，則稱A(G)為圖G的鄰接矩陣。第30頁，共65頁，2023年，2月20日，星期一圖論可達性矩陣設(shè)G=〈V，E〉是圖，V={v1,v2,…,vn}，建立n階方陣P(G)=(aij)，使得

aij=1，從vi到vj至少存在一條路；

aij=0，否則，則稱P(G)為圖G的可達性矩陣。比較：可達性矩陣與鄰接矩陣的區(qū)別第31頁，共65頁，2023年，2月20日，星期一圖論思考鄰接矩陣與可達矩陣之間有什么聯(lián)系？如何從鄰接矩陣計算出可達矩陣？第32頁，共65頁，2023年，2月20日，星期一圖論歐拉路和歐拉回路設(shè)G=〈V，E〉是無孤立結(jié)點的圖，若存在一條路，經(jīng)過圖G中每條邊一次且僅一次，則該條路稱為歐拉路；若存在一條回路，經(jīng)過圖G中每條邊一次且僅一次，則該條回路稱為歐拉回路。含有歐拉回路的圖稱為歐拉圖。第33頁，共65頁，2023年，2月20日，星期一圖論歐拉圖的判別準(zhǔn)則無向圖G具有一條歐拉路的充分必要條件是G是連通圖且只有兩個度數(shù)為奇數(shù)的結(jié)點或者沒有奇數(shù)度的結(jié)點。無向圖G是歐拉圖的充分必要條件是G是連通圖且沒有奇數(shù)度的結(jié)點。第34頁，共65頁，2023年，2月20日，星期一圖論歐拉圖的應(yīng)用哥尼斯堡七橋問題一筆畫問題第35頁，共65頁，2023年，2月20日，星期一圖論有向圖的歐拉路與歐拉回路給定有向圖G，通過圖中每邊一次且僅有一次的一條單向路，稱為單向歐拉路；通過圖中每邊一次且僅有一次的一條單向回路，稱為單向歐拉回路。第36頁，共65頁，2023年，2月20日，星期一圖論有向圖的歐拉路與歐拉回路的判別準(zhǔn)則有向圖G具有一條單向歐拉回路，當(dāng)且僅當(dāng)G是連通的，且每個結(jié)點的出度等于入度。有向圖G具有一條單向歐拉路，當(dāng)且僅當(dāng)G是連通的，而且除兩個結(jié)點外，每個結(jié)點的出度等于入度，而這兩個結(jié)點中，一個結(jié)點的入度比出度大1，另一個結(jié)點的出度比入度大1。第37頁，共65頁，2023年，2月20日，星期一圖論漢密爾頓路與回路給定一個圖G，若存在一條路經(jīng)過圖中的每個結(jié)點一次且僅一次，這條路稱為漢密爾頓路。若存在一條回路，經(jīng)過圖中的每個結(jié)點一次且僅一次（端點除外），這條路稱為漢密爾頓回路。具有漢密爾頓回路的圖稱為漢密爾頓圖。第38頁，共65頁，2023年，2月20日，星期一圖論思考?xì)W拉圖與漢密爾頓圖的相似與區(qū)別漢密爾頓圖的判別條件能夠有歐拉圖那么漂亮嗎？第39頁，共65頁，2023年，2月20日，星期一圖論漢密爾頓圖的性質(zhì)若圖G=〈V，E〉具有漢密爾頓回路，則對于V的每個非空子集S均有

w(G-S)≦|S|成立。其中w(G-S)是G中刪除S中結(jié)點后得到的圖的連通分支數(shù)。第40頁，共65頁，2023年，2月20日，星期一圖論漢密爾頓圖的判別沒有充分必要條件！注意：對于V的每個非空子集S均有

w(G-S)≦|S|成立的圖不一定是漢密爾頓圖。例如：Peterson圖。第41頁，共65頁，2023年，2月20日，星期一圖論漢密爾頓路與回路的構(gòu)造設(shè)G是具有n個結(jié)點的簡單圖，如果G中每一對結(jié)點度數(shù)之和大于等于n-1，則在G中存在一條漢密爾頓路。注意：上述條件只是充分的而不是必要的！設(shè)G是具有n個結(jié)點的簡單圖，如果G中每一對結(jié)點度數(shù)之和大于等于n，則在G中存在一條漢密爾頓回路。第42頁，共65頁，2023年，2月20日，星期一圖論圖的閉包與漢密爾頓圖給定具有n個結(jié)點的圖G=〈V，E〉，若將圖G中度數(shù)之和至少是n的非鄰接結(jié)點連接起來，并重復(fù)上述操作，直到不再有這樣的結(jié)點對為止，最終所得到的圖，稱為是原圖G的閉包，記作C(G)。當(dāng)且僅當(dāng)一個簡單圖的閉包是漢密爾頓圖時，這個簡單圖是漢密爾頓圖。第43頁，共65頁，2023年，2月20日，星期一圖論漢密爾頓圖的應(yīng)用周游世界游戲第44頁，共65頁，2023年，2月20日，星期一圖論平面圖設(shè)G=〈V，E〉是一個無向圖，如果能夠把G的所有結(jié)點和邊畫在平面上，且使得任何兩條邊除了端點之外沒有其他的交點，就稱G是一個平面圖。注意：只要有一個同構(gòu)圖是平面圖，就可判定它是平面圖。第45頁，共65頁，2023年，2月20日，星期一圖論平面圖的面及邊界設(shè)G是一個連通平面圖，由圖中的邊所包圍的區(qū)域，在此區(qū)域內(nèi)既不包含圖的結(jié)點，也不包含圖的邊，這樣的區(qū)域稱為G的一個面；包圍該面的諸邊所構(gòu)成的回路稱為這個面的邊界。第46頁，共65頁，2023年，2月20日，星期一圖論面的次數(shù)平面圖中一個面的邊界的回路長度稱為該面的次數(shù)，記作deg(r).在一個有限平面圖中每個面的次數(shù)之和等于其邊數(shù)的兩倍。注意：不要遺漏無限面！一個面內(nèi)部的邊需要計算兩次！第47頁，共65頁，2023年，2月20日，星期一圖論平面圖的歐拉定理設(shè)有一個連通平面圖G=〈V，E〉，它的結(jié)點數(shù)(v)、邊數(shù)(e)和面數(shù)(r)之間歐拉公式成立，即

v-e+r=2.第48頁，共65頁，2023年，2月20日，星期一圖論歐拉定理的一些推廣與應(yīng)用設(shè)G是一個有v個結(jié)點e條邊的連通簡單平面圖，若v≧3則e≦3v-6.可以用上述定理判別有些圖不是平面圖。例如：K5不是平面圖；K3，3不是平面圖。第49頁，共65頁，2023年，2月20日，星期一圖論Kuratowski定理一個圖是平面圖，當(dāng)且僅當(dāng)它不包含與K3，3或K5在2度結(jié)點內(nèi)同構(gòu)的子圖。所謂在2度結(jié)點內(nèi)同構(gòu)指的是兩個圖或者是同構(gòu)的，或者是通過反復(fù)插入或除去度數(shù)為2的結(jié)點后同構(gòu)。第50頁，共65頁，2023年，2月20日，星期一圖論對偶圖給定平面圖G=〈V，E〉，它具有面F1，F(xiàn)2，…，F(xiàn)n，若有圖G*=〈V*，E*〉滿足下列條件：（1）對于圖G的任何一個面Fi，內(nèi)部有且僅有一個結(jié)點vi*∈V*;（2）對于圖G的任何二個面Fi和Fj的公共邊界ek，存在且僅存在一條邊ek*∈E*，使ek*=（vi*，vj*），且ek*與ek相交；（3）當(dāng)且僅當(dāng)ek只是一個面Fi的邊界時，vi*存在一個環(huán)ek*與ek相交。則稱圖G*是G的對偶圖。第51頁，共65頁，2023年，2月20日，星期一圖論對偶圖的性質(zhì)對偶是相互的！一個連通的平面圖的對偶圖也是連通平面圖。第52頁，共65頁，2023年，2月20日，星期一圖論思考對于圖的著色問題，即對平面圖中的面進行著色，使其相鄰的面的顏色均不相同，可以歸結(jié)為對其對偶圖中的結(jié)點進行著色，使對偶圖中的相鄰結(jié)點具有不同的顏色。第53頁，共65頁，2023年，2月20日，星期一圖論圖的著色方法對于圖G著色時，需要的最少的著色數(shù)稱為G的著色數(shù)，記作x(G).著色基本步驟：（1）將圖G中的結(jié)點按照度數(shù)的遞減次序進行排列；（2）用第一種顏色對第一點進行著色，并按照排列次序，對與前面著色點不鄰接的每一點著上同樣的顏色；（3）用第二種顏色對其余結(jié)點進行著色，重復(fù)（2），直到所有的結(jié)點全都著上色。第54頁，共65頁，2023年，2月20日，星期一圖論關(guān)于著色的結(jié)論對于完全圖K，有x(K)=n.任意平面圖G最多是5一色的。任意平面圖G是4一色的！第55頁，共65頁，2023年，2月20日，星期一圖論樹的基本概念一個連通且無回路的無向圖稱為樹。樹中度數(shù)為1的結(jié)點稱為樹葉。樹中度數(shù)大于1的結(jié)點稱為分枝點或內(nèi)點。一個無回路的無向圖稱為森林，它的每個連通分支是樹。第56頁，共65頁，2023年，2月20日，星期一圖論樹的等價定義給定圖T，以下的定義是等價的：（1）無回路的連通圖；（2）無回路且e=v-1；（3）連通且e=v-1；（4）無回路，但增加一條新邊，得到一個且僅有一個回路；（5）連通，但刪除任一邊后便不連通；（6）每一對結(jié)點之間有一條且僅有一條路。第57頁，共65頁，2023年，2月20日，星期一圖論生成樹若圖G的一個生成子圖是一棵樹，則稱該樹是G的一棵生成樹。生成樹中的邊稱為樹枝；圖G的不在生成樹中的邊稱為弦；顯然，所有弦組成的集合與生成樹相對于圖G互補。顯然，生成樹一般不唯一。第58頁