圖論30電子科大楊春-文庫(kù)吧資料
2025-01-06 13:43本頁(yè)面
【正文】 條邊的非 H圖只有 C1,n以及 C2,5. 12n ????????22 1 0 x t 0 1 2 ?1 ? 0 1 n 偶圖匹配與因子分解 定理 13 (Hall定理）設(shè) G=(X, Y)是偶圖，則 G存在飽和 X每個(gè)頂點(diǎn)的匹配的充要條件是： , ( ) ( * )S X N S S? ? ?對(duì)有 推論：若 G是 k (k0)正則偶圖，則 G存在完美匹配。tal—— 度序列判定法 ) 設(shè)簡(jiǎn)單圖 G的度序列是 (d1,d2,…,d n), 這里， d1≦d 2≦…≦d n,并且 n≧3. 若對(duì)任意的 mn/2,或者 dmm,或者 dnm ≧ n m,則 G是 H圖。 H圖的判定 定理 7 (必要條件 ) 若 G為 H圖，則對(duì) V(G)的任一非空頂點(diǎn)子集 S，有： ()G S S? ??20 1 0 x t 0 1 2 ?1 ? 0 1 n 定理 8 (充分條件 ) 對(duì)于 n≧3 的單圖 G，如果 G中有： () 2nG? ? 定理 9 (充分條件 ) 對(duì)于 n≧3 的單圖 G，如果 G中的任意兩個(gè)不相鄰頂點(diǎn) u與 v，有： ( ) ( )d u d v n?? 定理 10 (幫迪 —— 閉包定理 ) 圖 G是 H圖當(dāng)且僅當(dāng)它的閉包是 H圖。 歐拉圖、歐拉跡的判定 19 1 0 x t 0 1 2 ?1 ? 0 1 n 定理 6 下列陳述對(duì)于非平凡連通圖 G是等價(jià)的： (1) G是歐拉圖； (2) G的頂點(diǎn)度數(shù)為偶數(shù)； (3) G的邊集合能劃分為圈。 17 1 0 x t 0 1 2 ?1 ? 0 1 n 托蘭定理 定理 2 若 n階簡(jiǎn)單圖 G不包含 Kl+1，則 G度弱于某個(gè)完全 l 部圖 H，且若 G具有與 H 相同的度序列，則 : GH?定理 3 設(shè) T是 (n, m)樹(shù)，則： 樹(shù)的性質(zhì) 1mn??最小生成樹(shù)算法 18 1 0 x t 0 1 2 ?1 ? 0 1 n 偶圖判定定理 定理 4 圖 G是偶圖當(dāng)且僅當(dāng) G中沒(méi)有奇回路。 若 D的中任意兩點(diǎn)是雙向連通的，稱(chēng) D是強(qiáng)連通圖； 16 1 0 x t 0 1 2 ?1 ? 0 1 n (二 )、重要結(jié)論 握手定理及其推論 定理 1： 圖 G= (V, E)中所有頂點(diǎn)的度的和等于邊數(shù) m的 2倍，即： ()( ) 2v V Gd v m???推論 1 在任何圖中，奇點(diǎn)個(gè)數(shù)為偶數(shù)。 ()G?(3)、色多項(xiàng)式 對(duì)圖進(jìn)行正常頂點(diǎn)著色，其方式數(shù) Pk(G)是 k的多項(xiàng)式，稱(chēng)為圖 G的色多項(xiàng)式。 14 1 0 x t 0 1 2 ?1 ? 0 1 n 邊色數(shù)、點(diǎn)色數(shù)、色多項(xiàng)式 (1)、邊色數(shù) 設(shè) G是圖，對(duì) G進(jìn)行正常邊著色需要的最少顏色數(shù)，稱(chēng)為 G的邊色數(shù)，記為： ()G??(2)、點(diǎn)色數(shù) 對(duì)圖 G正常頂點(diǎn)著色需要的最少顏色數(shù)，稱(chēng)為圖 G的點(diǎn)色數(shù)。 (4) 平面圖的對(duì)偶圖：給定平面圖 G， G的對(duì)偶圖 G*如下構(gòu)造： 1) 在 G的每個(gè)面 fi內(nèi)取一個(gè)點(diǎn) vi*作為 G*的一個(gè)頂點(diǎn)； 2) 對(duì) G的一條邊 e, 若 e是面 fi 與 fj 的公共邊，則連接 vi*與 vj*，且連線(xiàn)穿過(guò)邊 e。 (3) 極大外平面圖：若一個(gè)可平面圖 G存在一種平面嵌入，使得其所有頂點(diǎn)均在某個(gè)面的邊界上，稱(chēng)該圖為外可平面圖。 13 1 0 x t 0 1 2 ?1 ? 0 1 n (2) 極大平面圖 : 設(shè) G是簡(jiǎn)單可平面圖，如果 G是 Ki (1≦ i≦ 4),或者在G的任意非鄰接頂點(diǎn)間添加一條邊后，得到的圖均是非可平面圖，則稱(chēng) G是極大可平面圖。 (1) 平面圖： 如果能把圖 G畫(huà)在平面上，使得除頂點(diǎn)外，邊與邊之間沒(méi)有交叉，稱(chēng) G可以嵌入平面，或稱(chēng) G是可平面圖。 注：要弄清楚因子分解和完美匹配之間的聯(lián)系與區(qū)別。 (3) 最優(yōu)匹配 設(shè) G=(X, Y)是邊賦權(quán)完全偶圖， G中的一個(gè)權(quán)值最大的完美匹配稱(chēng)為 G的最優(yōu)匹配。 (2) 最大匹配與完美匹配 最大匹配 M 如果 M是圖 G的包含邊數(shù)最多的匹配，稱(chēng) M是 G的一個(gè)最大匹配。 11 1 0 x t 0 1 2 ?1 ? 0 1 n 匹配、最大匹配、完美匹配、最優(yōu)匹配、因子分解。所經(jīng)過(guò)的閉途徑是 G的一個(gè)生成圈，稱(chēng)為 G的哈密爾頓圈。 對(duì)于連通圖 G，如果 G中存在經(jīng)過(guò)每條邊的跡，則稱(chēng)該跡為 G的一條歐拉跡。 10 1 0 x t 0 1 2 ?1 ? 0 1 n (1) 歐拉圖與歐拉環(huán)游 (2) 歐拉跡 對(duì)于連通圖 G，如果 G中存在經(jīng)過(guò)每條邊的閉跡，則稱(chēng) G為歐拉圖，簡(jiǎn)稱(chēng) G為 E圖。 途徑 (閉途徑 )，跡 (閉跡 ), 路 (圈 ), 最短路，連通圖，連通分支，點(diǎn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1