圖論30電子科大楊春(完整版)
【正文】 n 強(qiáng)連通圖、單向連通圖、弱連通圖 (1)、強(qiáng)連通圖 (2)、弱連通圖 (3)、單向連通圖 若 D的基礎(chǔ)圖是連通的，稱(chēng) D是弱連通圖； 若 D的中任意兩點(diǎn)是單向連通的，稱(chēng) D是單向連通圖。 極大可平面圖的平面嵌入稱(chēng)為極大平面圖。特別是，若最大匹配飽和了 G的所有頂點(diǎn)，稱(chēng)它為 G的一個(gè)完美匹配。歐拉閉跡又稱(chēng)為歐拉環(huán)游，或歐拉回路。 (5) 根樹(shù) 一棵非平凡的有向樹(shù) T，如果恰有一個(gè)頂點(diǎn)的入度為 0，而其余所有頂點(diǎn)的入度為 1，這樣的的有向樹(shù)稱(chēng)為根樹(shù)。 樹(shù)、森林，生成樹(shù)，最小生成樹(shù)、根樹(shù)、完全 m元樹(shù)。 分析：四個(gè)頂點(diǎn)的簡(jiǎn)單圖最少邊數(shù)為 0，最多邊數(shù)為 6，所以 可按邊數(shù)進(jìn)行枚舉。 (2) 簡(jiǎn)單圖：無(wú)環(huán)無(wú)重邊的圖稱(chēng)為簡(jiǎn)單圖。 3 1 0 x t 0 1 2 ?1 ? 0 1 n (3) 圖的度序列： 一個(gè)圖 G的各個(gè)點(diǎn)的度 d1, d2,…, dn構(gòu)成的非負(fù)整數(shù)組 (d1, d2,…, dn)稱(chēng)為 G的度序列 。 5 1 0 x t 0 1 2 ?1 ? 0 1 n (6) 補(bǔ)圖與自補(bǔ)圖 1) 對(duì)于一個(gè)簡(jiǎn)單圖 G =（ V, E），令集合 ? ?1 ,E uv u v u v V? ? ?則圖 H =（ V， E1\E） 稱(chēng)為 G的補(bǔ)圖，記為 HG?2) 對(duì)于一個(gè)簡(jiǎn)單圖 G =（ V, E），若 ，稱(chēng) G為自補(bǔ)圖。 (1) 樹(shù) 不含圈的圖稱(chēng)為無(wú)圈圖，樹(shù)是連通的無(wú)圈圖。其中入度為 0的點(diǎn)稱(chēng)為樹(shù)根，出度為 0的點(diǎn)稱(chēng)為樹(shù)葉，入度為 1，出度大于 1的點(diǎn)稱(chēng)為內(nèi)點(diǎn)。 對(duì)于連通圖 G，如果 G中存在經(jīng)過(guò)每條邊的跡，則稱(chēng)該跡為 G的一條歐拉跡。 (3) 最優(yōu)匹配 設(shè) G=(X, Y)是邊賦權(quán)完全偶圖， G中的一個(gè)權(quán)值最大的完美匹配稱(chēng)為 G的最優(yōu)匹配。 (3) 極大外平面圖：若一個(gè)可平面圖 G存在一種平面嵌入，使得其所有頂點(diǎn)均在某個(gè)面的邊界上，稱(chēng)該圖為外可平面圖。 若 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ù)。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圖。 定理 19 每個(gè)沒(méi)有割邊的 3正則圖是一個(gè) 1因子和 1個(gè) 2因子之和。每名學(xué)生申請(qǐng)的職位如下： A : b, c 。 F E D C B A G a b c d e f g 解：如果令 X=｛ A, B, C, D, E, F, G｝ ,Y=｛ a, b, c, d, e, f , g｝ ,X中頂點(diǎn)與 Y中頂點(diǎn)連線當(dāng)且僅當(dāng)學(xué)生申請(qǐng)了該工作。平均每天要安排 7節(jié)課。這樣得到比賽狀態(tài)圖。 A2: MA, LA, G 。 2)、 點(diǎn)著色問(wèn)題 40 1 0 x t 0 1 2 ?1 ? 0 1 n A10: GT, S。 L9 L8 L7 L6 L5 L4 L3 L2 L1 G 問(wèn)題轉(zhuǎn)化為求 G的點(diǎn)色數(shù)。 所以，最小相位為 4。 GT MA G AC LA S 選課狀態(tài)圖 41 1 0 x t 0 1 2 ?1 ? 0 1 n 如果我們用同一顏色給同一時(shí)段的課程頂點(diǎn)染色，那么，問(wèn)題轉(zhuǎn)化為在狀態(tài)圖中求對(duì)應(yīng)于點(diǎn)色數(shù)的著色。 A4: G, LA, AC 。 37 1 0 x t 0 1 2 ?1 ? 0 1 n 狀態(tài)圖為： F D A G C E B 圖 G 由于 n=2 3+1, 所以 k=3。 36 1 0 x t 0 1 2 ?1 ? 0 1 n 例 3 (比賽安排問(wèn)題 ) Alvin (A)曾邀請(qǐng) 3對(duì)夫婦到他的避暑別墅住一個(gè)星期。 著色問(wèn)題 1)、 邊著色問(wèn)題 例 2 (排課表問(wèn)題 ) 在一個(gè)學(xué)校中，有 7個(gè)教師 12個(gè)班級(jí)。 C : b, e 。 4)、對(duì)偶圖的性質(zhì) 定理 22 平面圖 G的對(duì)偶圖必然連通 . 5)、極大平面圖的性質(zhì) 定理 23 設(shè) G是至少有 3個(gè)頂點(diǎn)的平面圖，則 G是極大平面圖，當(dāng)且僅當(dāng) G的每個(gè)面的次數(shù)是 3且為單圖。若 n≧3 且 1( ) 12nEG ????????? 則 G是 H圖；并且，具有 n個(gè)頂點(diǎn) 條邊的非 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è)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1