離散數(shù)學(xué)圖論第四講

1、 定義定義 漢密爾頓路，漢密爾頓回路漢密爾頓路，漢密爾頓回路給定圖給定圖G G，若存在一條路經(jīng)過圖中的每一個，若存在一條路經(jīng)過圖中的每一個結(jié)點恰好一次，這條路稱作結(jié)點恰好一次，這條路稱作漢密爾頓路漢密爾頓路。若。若存在一條回路，經(jīng)過圖中的每一個結(jié)點恰好存在一條回路，經(jīng)過圖中的每一個結(jié)點恰好一次，這個回路稱作一次，這個回路稱作漢密爾頓回路漢密爾頓回路。具有漢密爾頓回路的圖稱為漢密爾頓圖具有漢密爾頓回路的圖稱為漢密爾頓圖 定理定理 若圖若圖G G= =V V，E E具有漢密爾頓回路，具有漢密爾頓回路，則對于結(jié)點集則對于結(jié)點集V V的每一個非空子集的每一個非空子集S S均有均有 W W( (G GS

2、 S)|S|)|S|成立。其中成立。其中W W( (G GS S) )是是G GS S中連通分支數(shù)。中連通分支數(shù)。 (a)(b) 3正則圖正則圖彼得松圖彼得松圖思考：有割點的圖一定不是漢密爾頓圖。思考：有割點的圖一定不是漢密爾頓圖。 定理定理 設(shè)設(shè)G G具有具有n n個結(jié)點的簡單圖，如果個結(jié)點的簡單圖，如果G G中每中每一對結(jié)點的度數(shù)之和大于等于一對結(jié)點的度數(shù)之和大于等于n n-1-1，則在，則在G G中存在一條漢密爾頓路。中存在一條漢密爾頓路。 定理定理 設(shè)圖設(shè)圖G G是具有是具有n n個結(jié)點的簡單圖，如果個結(jié)點的簡單圖，如果G G中每一對結(jié)點的度數(shù)大于等于中每一對結(jié)點的度數(shù)大于等于n n，

3、則在，則在G G中中存在一條漢密爾頓回路。存在一條漢密爾頓回路。平面圖 定義定義 設(shè)設(shè)G GV V，E E是一個無向圖，如果是一個無向圖，如果能夠把能夠把G G的所有結(jié)點和邊畫在平面上，且使的所有結(jié)點和邊畫在平面上，且使任任何兩條邊除了端點外沒有其它的交點何兩條邊除了端點外沒有其它的交點，就稱，就稱G G是一個平面圖。是一個平面圖。 定義定義 圖圖G G的面和邊界的面和邊界 設(shè)設(shè)G G是一個連通平面圖，由圖中的邊所包圍的區(qū)是一個連通平面圖，由圖中的邊所包圍的區(qū)域，在區(qū)域內(nèi)既域，在區(qū)域內(nèi)既不包含圖的結(jié)點，也不包含圖的邊不包含圖的結(jié)點，也不包含圖的邊，這樣的區(qū)域稱為圖這樣的區(qū)域稱為圖G G的一個的

4、一個面，面，包圍包圍該面的諸邊所該面的諸邊所構(gòu)成的回路構(gòu)成的回路稱為這個稱為這個面的邊界。面的邊界。面的邊界的回路長面的邊界的回路長度稱作該度稱作該面的次數(shù)面的次數(shù)，記為，記為deg(r)deg(r)，思考：所有面的次數(shù)和邊數(shù)有關(guān)系嗎思考：所有面的次數(shù)和邊數(shù)有關(guān)系嗎定理定理7-5.2(7-5.2(歐拉定理歐拉定理) )設(shè)有一個設(shè)有一個連通平面圖連通平面圖G G，共有，共有v v個結(jié)點個結(jié)點e e條邊條邊r r塊面，則歐拉公式塊面，則歐拉公式 v-v-e e+ +r r2 2 成立。成立。定理定理7-5.3 7-5.3 設(shè)設(shè)G G為有為有v v個結(jié)點個結(jié)點e e條邊的條邊的連通簡連通簡單平面圖單

5、平面圖，若，若v3v3，則，則 e3v-6 e3v-6。 定義定義 圖是在圖是在2 2度結(jié)點內(nèi)同構(gòu)度結(jié)點內(nèi)同構(gòu)給定兩個圖給定兩個圖G G1 1和和G G2 2，如果它們是同構(gòu)的，或通，如果它們是同構(gòu)的，或通過反復(fù)插入或刪去度數(shù)為過反復(fù)插入或刪去度數(shù)為2 2的結(jié)點后，使的結(jié)點后，使G G1 1和和G G2 2同構(gòu)，則稱該圖是在同構(gòu)，則稱該圖是在2 2度結(jié)點內(nèi)同構(gòu)。度結(jié)點內(nèi)同構(gòu)。定理定理7-5.4(7-5.4(KuratowskiKuratowski庫拉托夫斯基定理庫拉托夫斯基定理) ) 一個平面圖，一個平面圖，當且僅當當且僅當它不包含與它不包含與K K3,33,3或或K K5 5在在2 2度結(jié)點內(nèi)同構(gòu)的子圖。度結(jié)點內(nèi)同構(gòu)