組合數(shù)學(xué)市公開課獲獎?wù)n件

1、第 11 章圖 論 引 導(dǎo)第1頁第1頁11.1 基 本 性 質(zhì)11.1基本性質(zhì)圖G是個二元組 G=(V，E)；其中，V是圖G頂點(diǎn)集合，且V是有限集；E V V=(x，y)|x，y V，x y稱為圖G邊集，且若邊 =(x，y) E，則邊 =(y，x) E，且， 被視為同一條邊。這樣圖G，我們也稱作簡樸圖。 頂點(diǎn)集合V中頂點(diǎn)個數(shù)稱為圖G階。 若 =(x，y) E是圖G一條邊，則說邊連接頂點(diǎn)x和y；或者說，頂點(diǎn)x和y是鄰接；或者說，頂點(diǎn)x和y均依附于邊，即， x和， y和 是關(guān)聯(lián)。第2頁第2頁例 G是一個5階圖 G=(V,E)其中 V=a, b, c, d, e；E=(a, b), (b, c),

2、(c, d), (d, a), (e, a), (e, b), (e, d)G可圖示為11.1 基 本 性 質(zhì)第3頁第3頁 假如邊集E是一個多重集，則 G=(V,E) 是一個多重圖。在多重圖 G=(V,E) 中，若邊 =(x, y) 在E中出現(xiàn)了m次，則稱m是邊重?cái)?shù)，記作 m(x,y)。 對于多重圖 G=(V,E) ，若邊集E中允許出現(xiàn)形如(x, x) 邊，則稱G是普通圖，其中邊 (x, x) 稱作球。11.1 基 本 性 質(zhì)第4頁第4頁例11.1 基 本 性 質(zhì)第5頁第5頁 對于圖G=(V, E)，若V中任意一對不同頂點(diǎn)x, y，都有(x, y) E，則稱G是一個 n=|V|階完全圖。對于n

3、階簡樸完全圖而言，它所包含邊數(shù)是 n(n-1)/2。把此圖、記作Kn。例K1K2K3K4K511.1 基 本 性 質(zhì)第6頁第6頁 對于圖 G=(V, E)，若在平面上存在一個畫法，使得E中任意兩條邊均不相交（僅能在頂點(diǎn)處相交），則稱G是一個平面圖。 在普通圖 G=(V, E)中， x V，頂點(diǎn)x度deg(x)是與x關(guān)聯(lián)邊條數(shù)。尤其，若 =(x, x) E，則使x度增長了2。設(shè) V=x1,x2,xn，則deg(xi)=di，i=1, 2, , n，使得d1 d2 dn 0，則稱 （ d1, d2, , dn ）是圖G度序列。定理11.1.1 設(shè)G 是一個普通圖，則其所有頂點(diǎn)度數(shù) 之和 d1+d2

4、+ +dn 是一個偶數(shù)，從而，其奇度頂點(diǎn)個數(shù)也必為偶數(shù)。11.1 基 本 性 質(zhì)第7頁第7頁 設(shè)G=(V, E), G=(V, E)均是普通圖。若存在1-1相應(yīng)： ： V V使得： x, y V，(x, y)在E中重?cái)?shù)等于(x),(y)在E中重?cái)?shù)，則稱G和G是同構(gòu)，相應(yīng)稱為G和G一個同構(gòu)。11.1 基 本 性 質(zhì)第8頁第8頁例 設(shè) G=( a1, a2, a3, a4, E) G=( x1, x2, x3, x4, E) 定義(ai)=xi i=1, 2, 3, 4 且若 ( ai, aj)E，iff (xi, xj) E 則 G 和G同構(gòu)。a1a2a3a4x1x2x3x411.1 基 本 性

5、 質(zhì)第9頁第9頁例11.1 基 本 性 質(zhì)第10頁第10頁例11.1 基 本 性 質(zhì)第11頁第11頁定理11.1.2 兩個同構(gòu)普通圖含有相同度序列。 反之，則不一定。11.1 基 本 性 質(zhì)第12頁第12頁 設(shè)G（V，E）是一個普通圖， x0，xmV，若存在（xi,xi+1）E,i=0,1,2,m-1 則稱由這m個邊構(gòu)成序列: （x0,x1）,(x1,x2),(xm-1,xm)是連接頂點(diǎn)x0和xm一條長度為m路徑，記作： x0 x1x2xm若x0 xm，則稱該路徑為開，不然為閉路徑。 無重復(fù)邊路徑稱為跡；無重復(fù)頂點(diǎn)路徑稱為鏈；x0 xm鏈稱為圈。11.1 基 本 性 質(zhì)第13頁第13頁 設(shè)G=

6、(V，E)是一個普通圖， x，yV，G中均存在連接x和y路徑，則稱G是連通圖；不然G是非連通圖。 設(shè)G=( V, E )是一個連通圖， x，yV , x和y之間距離是連接x和y 路徑最短長度，記作d（x，y）。 11.1 基 本 性 質(zhì)第14頁第14頁 設(shè)G=( V, E )是普通圖，G=(U, F)也是普通圖，使得： 且 (x, y) F，有x，yU，則稱G是G普通子圖。進(jìn)一步，若 x，yU，(x, y) E，必有(x, y) F，則稱G是GU導(dǎo)出普通子圖，記為GuG；在G中，若UV，則稱G為G生成子圖。 11.1 基 本 性 質(zhì)第15頁第15頁11.1 基 本 性 質(zhì)第16頁第16頁定理1

7、1.1.3 設(shè)G=( V, E )是普通圖，則V存在劃分 V1，V2，, Vk： 使得： i）由Vi導(dǎo)出普通子圖Gi=( Vi, Ej )是連通， 1ik； )若ij，則 xVi和 yVj，G中不存在連接 x和y路徑。并稱Gi是G連通分量 (連通分支， 連通分圖)，1ik。 ViVj= ij, Vi 1i k 11.1 基 本 性 質(zhì)第17頁第17頁定理11.1.4 設(shè)G=( V, E )，G=( V, E)，則G與G同構(gòu)必有： )若G是簡樸圖，則G也是簡樸圖； ) G與G含有相同數(shù)目的連通分量； )若G存在一個長度為m圈，則G亦然； )若G存在一個m階完全圖Km是G(導(dǎo)出)普通子 圖，則G

8、亦然。 11.1 基 本 性 質(zhì)第18頁第18頁 設(shè)G=( V, E )是n階普通圖 ，V( x1, x2, , xn)?，F(xiàn)定義nn矩陣 A(aij)nn： aij連接xi和xj邊數(shù)目 1 i， j n則稱A是G鄰接矩陣。11.1 基 本 性 質(zhì)第19頁第19頁例Ax1 x2 x3 x4 x5 x60 1 2 0 1 01 1 0 0 2 02 0 0 1 1 10 0 1 1 2 21 2 1 2 0 00 0 1 2 0 0 x1 x2 x3 x4 x5 x611.1 基 本 性 質(zhì)第20頁第20頁11.2 歐 拉 跡11.2 歐拉跡 設(shè)G(V, E)是一個普通圖。若 x, yV， 連接x

9、和y跡包括了E中每一條邊，則該跡稱作歐拉跡。 比如第21頁第21頁引理11.2.1 設(shè)G(V,E)是普通圖，若 x V，deg(x)為偶數(shù)，則G每條邊均屬于一條閉跡，因而也屬于一個圈。定理11.2.2 設(shè)G(V,E)是連通普通圖，則G中存在閉歐拉跡，iff x V，deg(x)是偶數(shù)。例11.2 歐 拉 跡第22頁第22頁定理11.2.3 設(shè)G(V,E)是連通普通圖，則G中存在一條開歐拉跡 iff G中正好有兩個奇度頂點(diǎn)u，v。 且G中任意一條開歐拉跡均連接u和v。 例11.2 歐 拉 跡第23頁第23頁定理11.2.4 設(shè)G(V,E)是連通普通圖，G中奇度頂點(diǎn)個數(shù)m0，則G邊可劃分為m/2個

10、開跡，但不能劃分為少于m/2個開跡。 例11.2 歐 拉 跡第24頁第24頁例11.2 歐 拉 跡第25頁第25頁 中國郵遞員問題：設(shè)G(V,E)是連通普通圖，G中是否存在一條最短路徑r，使得 ，e至少在r中出現(xiàn)一次。定理11.2.5 設(shè)G(V,E)是一個含有K|E|條邊連通普通圖，則G中存在一條長度為2K閉路徑r，使得 ，e在r中出現(xiàn)次數(shù)等于e重?cái)?shù)2倍。 分析 G： G* G*中每條邊重?cái)?shù)均是G中每條邊重?cái)?shù)2倍，且共有2K條邊。依據(jù)定理11.2.2，G*中存在一條閉歐拉跡。此歐拉跡即G中所求。11.2 歐 拉 跡第26頁第26頁例11.2 歐 拉 跡第27頁第27頁11.3 Hamilton

11、鏈和Hamilton圈11.3 Hamilton鏈和Hamilton圈 設(shè)G(V,E)是一個簡樸圖，是否存在一個圈r，使得 ，x在r中出現(xiàn)一次且僅出現(xiàn)一次。 若這樣圖存在，則稱其為Hamilton圈。相應(yīng)，若G中存在一條鏈，使得 ，x在該鏈中出現(xiàn)一次且僅出現(xiàn)一次，則該鏈?zhǔn)?Hamilton鏈。 第28頁第28頁例 關(guān)于Kn（n 3）例11.3 Hamilton鏈和Hamilton圈第29頁第29頁 設(shè) G(V,E) 是一個連通簡樸圖，若 ，使得圖G*（V，Ee）是非連通圖，則稱邊e是圖G一個橋。定理11.3.1 帶有橋連通圖中不存在Hamilton圈。11.3 Hamilton鏈和Hamilt

12、on圈第30頁第30頁 設(shè) G(V,E) 是一個簡樸圖，且|V|=n。若 ，即x與y不鄰接，都有： deg（x）deg（y） n則稱圖G含有Ore性質(zhì)。定理11.3.2 設(shè)G是一個滿足Ore性質(zhì)，階數(shù)n 3簡樸圖，則G中存在Hamilton圈。11.3 Hamilton鏈和Hamilton圈xyyx第31頁第31頁11.4 二 分 多 重 圖11.4 二分多重圖 設(shè) G(V,E) 是一個多重圖，若V存在劃分X，Y： XY=V, XY = , X , Y 使得 (x，y)E，x，則稱圖G是一個二分多重圖，相應(yīng) X，Y稱為一個二分劃。第32頁第32頁例11.4 二 分 多 重 圖第33頁第33頁1

13、1.4 二 分 多 重 圖第34頁第34頁定理11.4.1 一個多重圖是二分 iff 它任意一個圈 長度均是偶數(shù)。分析 1) G(V,E)是二分多重圖 G任意一個圈長度均是偶數(shù)。 由于G是二分，因此G存在一個二分劃X,Y。 依據(jù)二分圖定義，G中任一路徑上之頂點(diǎn)必交替于X和Y之間，故|X|Y| 。 因此G任一圈其長度必是偶數(shù)。 11.4 二 分 多 重 圖第35頁第35頁 2) G(V,E)任一圈長度是偶數(shù) G是二分。設(shè)G是連通，任取一個x V，令 X = y | y到x距離是偶數(shù)，y V Y = y | y到x距離是奇數(shù)，y V則X，Y必是G一個分劃。不然，則有（a，b） E，使a，b X。即

14、 a - x 和 b - x 長度均是偶數(shù)。于是有圈： a - x b -x 其長為奇數(shù)。這與條件矛盾。故不存在（a，b） E使a，b X；同樣，也不存在(a，b) E使a，b Y。從而X，Y是G二分劃。 若G是不連通，則其每個連通分量均是二分。11.4 二 分 多 重 圖第36頁第36頁例 考慮全部n位二進(jìn)制數(shù)組成集合V，令 E=（x，y）|x，y V，x與y僅有一位不同則Qn=（V，E）是二分圖。因?yàn)榱?X= x | x有偶數(shù)個1，x V Y= x | x有奇數(shù)個1，x V則X，Y組成Qn一個二分劃。Q1Q2Q311.4 二 分 多 重 圖第37頁第37頁定理11.4.2 設(shè)G是一個含有二

15、分劃X，Y二分圖， 1）假如|X| |Y|，則G中不存在Hamilton圈； 2）假如|X| = |Y|，則G中不存在起始于X（或Y）中頂點(diǎn)又終止于X（或Y）中頂點(diǎn)Hamilton鏈； 3）假如|X|Y|+2，或|Y|X| +2則G中不存在Hamilton鏈； 4）假如|X| = |Y|+1，則G中不存在起始于X終止于Y中Hamilton鏈，反之亦然。11.4 二 分 多 重 圖第38頁第38頁例（騎士問題） 給定一個88棋盤，棋盤上一個格子表示一個位置，并遵循下列移動規(guī)則： 1 垂直移動2格并水平移動1格，或者 2 垂直移動1格并水平移動2格。 現(xiàn)在問題是：騎士從任意指定位置出現(xiàn)。按照移動規(guī)

16、則，是否存在一個也許，使得騎士在棋盤上每一格正好出項(xiàng)一次？騎士環(huán)游 假如存在上述也許，那么當(dāng)騎士到達(dá)最后一格時，遵循同樣移動規(guī)則，是否能夠回到本來起始置？重復(fù)環(huán)游11.4 二 分 多 重 圖第39頁第39頁58436037524164354946574261365340445948513855346347504556336239542273212413181531223619162712821429102514173309205281126 設(shè)G( V,E ) 是一個二分圖。G二分劃是X，Y。且|X|=m，|Y|=n，則記該二分圖為Km，n= ( X，Y，E ) 。11.4 二 分 多 重 圖第40頁第40頁11.5 樹11.5 樹 設(shè)G( V,E ) 是n階連通圖，且G中不含圈，則稱G是n階樹。定理11.5.1 一個n階連通圖至少有n-1條邊。另外，對于任意一個正整數(shù)n，存在一個正好為n-1條邊連通圖。從n個頂點(diǎn)，n-1條邊連通圖中去掉任意一條邊，得到一個不連通圖，因此，每條邊都是一