期末復(fù)習(xí)ppt課件-wenkub
2023-05-14 02:55:05 本頁面
【正文】 最小生成樹或最小代價樹。 (2) 森林 稱無圈圖 G為森林。如此得到的新圖稱為 G1與 G2的積圖。 GG?注：要求掌握自補(bǔ)圖的性質(zhì)。 u1v1 E1,當(dāng) 且僅當(dāng) u2v2 E2,且 u1v1與 u2v2的重數(shù)相同。 注：度序列的判定問題是重點(diǎn)。用 |V|表示頂點(diǎn)數(shù)； 2) E是由 V中的點(diǎn)組成的無序?qū)?gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對在 E中可以重復(fù)出現(xiàn)多次。用 |E|表示邊數(shù)。 (4) 圖的圖序列： 一個非負(fù)數(shù)組如果是某簡單圖的度序列，我們稱它為可圖序列，簡 稱圖序列。稱 G1與 G2同構(gòu)，記為： ?? ??12GG? 例 1 指出 4個頂點(diǎn)的非同構(gòu)的所有簡單圖。 1 0 x t 0 1 2 ?1 ? 0 1 n 7 (7) 聯(lián)圖 設(shè) G1,G2是兩個不相交的圖，作 G1+G2，并且將 G1中每個頂點(diǎn)和 G2中的每個頂點(diǎn)連接，這樣得到的新圖稱為 G1與 G2的聯(lián)圖。記為 12G G G?? 1 0 x t 0 1 2 ?1 ? 0 1 n 8 (9) 偶圖 所謂具有二分類（ X, Y）的偶圖（或二部圖）是指一個圖，它的點(diǎn)集可以分解為兩個 (非空 )子集 X和 Y，使得每條邊的一個端點(diǎn)在中，另一個端點(diǎn)在 Y中 . 注 : 掌握偶圖的判定。 1 0 x t 0 1 2 ?1 ? 0 1 n 9 (3) 生成樹 圖 G的一個生成子圖 T如果是樹，稱它為 G的一棵生成樹；若 T為森林，稱它為 G的一個生成森林。 注：要求熟練掌握最小生成樹的求法。 1 0 x t 0 1 2 ?1 ? 0 1 n 10 (6) 完全 m元樹 對于根樹 T，若每個分支點(diǎn)至多 m個兒子，稱該根樹為 m元根樹；若每個分支點(diǎn)恰有 m個兒子，稱它為完全 m元樹。 1 0 x t 0 1 2 ?1 ? 0 1 n 11 (1) 歐拉圖與歐拉環(huán)游 (2) 歐拉跡 對于連通圖 G，如果 G中存在經(jīng)過每條邊的閉跡，則稱 G為歐拉圖，簡稱 G為 E圖。所經(jīng)過的閉途徑是 G的一個生成圈，稱為 G的哈密爾頓圈。 (2) 最大匹配與完美匹配 最大匹配 M 如果 M是圖 G的包含邊數(shù)最多的匹配，稱 M是 G的一個最大匹配。 注：要弄清楚因子分解和完美匹配之間的聯(lián)系與區(qū)別。 1 0 x t 0 1 2 ?1 ? 0 1 n 14 (2) 極大平面圖 : 設(shè) G是簡單可平面圖，如果 G是 Ki (1≦ i≦ 4),或者在G的任意非鄰接頂點(diǎn)間添加一條邊后，得到的圖均是非可平面圖，則稱 G是極大可平面圖。 (4) 平面圖的對偶圖：給定平面圖 G， G的對偶圖 G*如下構(gòu)造： 1) 在 G的每個面 fi內(nèi)取一個點(diǎn) vi*作為 G*的一個頂點(diǎn)； 2) 對 G的一條邊 e, 若 e是面 fi 與 fj 的公共邊，則連接 vi*與 vj*，且連線穿過邊 e。 ()G?(3)、色多項式 對圖進(jìn)行正常頂點(diǎn)著色，其方式數(shù) Pk(G)是 k的多項式，稱為圖 G的色多項式。 1 0 x t 0 1 2 ?1 ? 0 1 n 18 托蘭定理 定理 2 若 n階簡單圖 G不包含 Kl+1，則 G度弱于某個完全 l 部圖 H，且若 G具有與 H 相同的度序列，則 : GH?定理 3 設(shè) T是 (n, m)樹，則： 樹的性質(zhì) 1mn??最小生成樹算法 1 0 x t 0 1 2 ?1 ? 0 1 n 19 偶圖判定定理 定理 4 圖 G是偶圖當(dāng)且僅當(dāng) G中沒有奇回路。 H圖的判定 定理 7 (必要條件 ) 若 G為 H圖，則對 V(G)的任一非空頂點(diǎn)子集 S，有： ()G S S? ?? 1 0 x t 0 1 2 ?1 ? 0 1 n 21 定理 8 (充分條件 ) 對于 n≧3 的單圖 G，如果 G中有： () 2nG? ? 定理 9 (充分條件 ) 對于 n≧3 的單圖 G，如果 G中的任意兩個不相鄰頂點(diǎn) u與 v，有： ( ) ( )d u d v n?? 定理 10 (幫迪 —— 閉包定理 ) 圖 G是 H圖當(dāng)且僅當(dāng)它的閉包是 H圖。若 n≧3 且 1( ) 12nEG ????????? 則 G是 H圖；并且，具有 n個頂點(diǎn) 條邊的非 H圖只有 C1,n以及 C2,5. 1 12n ???????? 1 0 x t 0 1 2 ?1 ? 0 1 n 23 偶圖匹配與因子分解 定理 13 (Hall定理）設(shè) G=(X, Y)是偶圖，則 G存在飽和 X每個頂點(diǎn)的匹配的充要條件是： , (
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1