圖論25電子科大楊春-wenkub.com
2025-01-03 13:02 本頁面
【正文】 一方面， G中含有 K4,所以，點(diǎn)色數(shù)至少為 4； L9 L8 L7 L6 L5 L4 L3 L2 L1 G 36 1 0 x t 0 1 2 ?1 ? 0 1 n 另一方面，通過嘗試，用 4種色實(shí)現(xiàn)了正常點(diǎn)著色。在此路口處安置了交通燈。 解：把課程模型為圖 G的頂點(diǎn)，兩頂點(diǎn)連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門課程。 A7: GT, MA, LA 。 A3: MA, G, LA?，F(xiàn)有 10名學(xué)生 (如下所示 )需要選修這些課程。因此， п 可以擴(kuò)充為 G的 5正常頂點(diǎn)著色。 如果 x1與 x3屬于 H(1, 3) 的不同分支。 (1) 如果 d(u)=δ(G)5, 顯然 п 可以擴(kuò)充為 G的 5正常頂點(diǎn)著色； (2) 如果 d(u)=δ(G) = 5, 分兩種情況討論。 因 G是簡(jiǎn)單平面圖，所以 δ (G)≦5 設(shè) d(u)=δ (G)≦5 。 證明：我們對(duì)圖的頂點(diǎn)作數(shù)學(xué)歸納證明。 20世紀(jì) 70年代， Haken和他的學(xué)生 Appel著力用計(jì)算機(jī)方法證明 4色定理，借助于 Appel在編程方面的深厚功底。 希伍德文章之后， 4色問題研究進(jìn)程開始走向停滯?？掀帐莿P萊在劍橋大學(xué)的學(xué)生。 格斯里把他的證明通過他弟弟轉(zhuǎn)交給著名數(shù)學(xué)家摩爾根，引起摩爾根極大興趣并于當(dāng)天給數(shù)學(xué)家哈密爾頓寫了封相關(guān)信件。 定義 3 設(shè) G是至少有一條邊的簡(jiǎn)單圖，定義： 2 ( ) ( )( ) ( )( ) m a x m a x ( )u V G v N ud v d uG d v????? 其中 N(u)為 G中點(diǎn) u的鄰域。又顯然 G｛ x1, x2｝ 連通。 此時(shí)，存在點(diǎn) xn,使得 Gxn連通且有割點(diǎn) v, 于是 Gxn至少含有兩個(gè)塊。 所以，下面只需證明：假設(shè) G是正則的， 2連通的，最大度 Δ ≥3的簡(jiǎn)單圖，且不是完全圖或奇圈，有： ( ) ( )GG? ?? 分兩步完成證明。 設(shè) u是 G中頂點(diǎn)，且 d(u)=δ Δ ，考慮 G1=Gu 若 G1是正則單圖，則 Δ (G1)=Δ (G)1。 定理 2(布魯克斯， 1941) 若 G是連通的單圖，并且它既不是奇圈，又不是完全圖，則： ( ) ( )GG? ?? 數(shù)學(xué)家羅瓦斯在 1973年給出了如下證明。 v5 v4 v3 v2 v1 v6 解：色集 C=｛ 1, 2, 3, 4, 5｝ 1(1), ( ) = 1v? ? ? ? ?22( 2) , ( ) = 1 , ( ) 2 , 3 , 4 , 5 , 2C v C C v k? ? ?2(1), ( ) = 2v? ? ? ? ?33( 2) , ( ) = 1 , 2 , ( ) 3 , 4 , 5 , 3C v C C v k? ? ?11 1 0 x t 0 1 2 ?1 ? 0 1 n v5 v4 v3 v2 v1 v6 3(1), ( ) = 3v? ? ? ? ?44( 2) , ( ) = 3 , ( ) 1 , 2 , 4 , 5 , 1C v C C v k? ? ?4(1), ( ) = 1v? ? ? ? ?55( 2) , ( ) = 1 , ( ) 2 , 3 , 4 , 5 , 2C v C C v k? ? ?5(1), ( ) = 2v? ? ? ? ?65( 2) , ( ) = 1 , 2 , 3 , ( ) 4 , 5 , 4C v C C v k? ? ?6(1), ( ) = 4v?v5(2) v4(1) v3(3) v2(2) v1(1) v6(4) 12 1 0 x t 0 1 2 ?1 ? 0 1 n v5 v4 v3 v2 v1 v6 注 : (1)不能通過上面算法求出色數(shù)，例如，根據(jù)上面算法，我們求出了一個(gè) 4色方案，但 G是 3色圖： (2) Welsh—Powell稍微對(duì)上面算法做了一個(gè)修改，著色時(shí)按所謂最大度優(yōu)先策略，即使用上面算法時(shí)，按頂點(diǎn)度數(shù)由大到小的次序著色。 9 1 0 x t 0 1 2 ?1 ? 0 1 n G的 Δ (G)+1正常點(diǎn)著色算法 設(shè) G=(V, E), V=｛ v1,v2,…,v n｝ ,色集合 C=｛ 1,2,…, Δ +1｝ ,著色方案為 п 。 設(shè)對(duì)頂點(diǎn)數(shù)少于 n的圖來說，定理結(jié)論成立。 定義 2 色數(shù)為 k的圖稱為 k色圖。 GT MA G AC LA S GT MA G AC LA S 6 1 0 x t 0 1 2 ?1 ? 0 1 n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1