圖論25電子科大楊春-文庫(kù)吧資料
2025-01-09 13:02本頁(yè)面
【正文】 不斷這樣作下去，可得到 G的頂點(diǎn)排序： x1,x2,…,x n 18 1 0 x t 0 1 2 ?1 ? 0 1 n 該頂點(diǎn)序列的特征是，對(duì)于 1≦i≦n 1,xi與某個(gè) xi+k鄰接 。由于 x1與 x2分屬于不同塊，所以 x1與 x2不鄰接。 v G xn 塊 塊 塊 17 1 0 x t 0 1 2 ?1 ? 0 1 n 由于 G本身 2連通 ，所以 Gxn的每個(gè)僅含有一個(gè)割點(diǎn)的塊中均有點(diǎn)與 xn鄰接。 情形 2 設(shè) G是連通度為 2的正則非完全圖。 1) 在上面條件下，我們證明： G中存在三點(diǎn) x1, x2, xn,使得 G ｛ x1, x2｝ 連通， x1與 x2不鄰接，但 x1, x2與 xn均鄰接； x1 x2 xn G 16 1 0 x t 0 1 2 ?1 ? 0 1 n 情形 1 設(shè) G是 3連通的正則非完全圖。所以定理結(jié)論顯然成立。于是 G1是可Δ (G)頂點(diǎn)正常著色的，從而， G是可 Δ (G)正常頂點(diǎn)著色的； 若 G1是非正則單圖，則 由數(shù)學(xué)歸納， G1是可 Δ (G)頂點(diǎn)正常著色的，從而， G是可 Δ (G)正常頂點(diǎn)著色的。下設(shè) G是階數(shù)為 n的非正則連通單圖。 證明：不失一般性，我們可以假設(shè) G是正則的， 2連通的，最大度 Δ ≥3的簡(jiǎn)單圖。這就是下面著名的布魯克斯定理。這樣的著色方案起到了對(duì)上面算法的一個(gè)改進(jìn)作用。 10 1 0 x t 0 1 2 ?1 ? 0 1 n 例 2 給出下圖的 Δ +1正常點(diǎn)著色。 (1) 令 п (v1)=1, i=1。 對(duì)于 G來(lái)說(shuō)，可以給出其 Δ (G)+1正常點(diǎn)著色算法?？紤]一般的 n階圖 G。 當(dāng) n=1時(shí)，結(jié)論顯然成立。 (二 )、圖的點(diǎn)色數(shù)的幾個(gè)結(jié)論 定理 1 對(duì)任意的圖 G，有： ( ) ( ) 1GG? ? ? ? 分析：事實(shí)上，定理結(jié)論容易想到，因?yàn)槿我庖粋€(gè)頂點(diǎn)度數(shù)至多為 Δ ，因此，正常著色過(guò)程中，其鄰點(diǎn)最多用去 Δ種顏色，所以，至少還有一種色可供該點(diǎn)正常著色使用。用點(diǎn)色數(shù)種顏色對(duì)圖 G正常著色，稱為對(duì)圖 G的最優(yōu)點(diǎn)著色。所以，對(duì)應(yīng)的實(shí)際問(wèn)題也是分類問(wèn)題。 ()? 例 1 說(shuō)明下圖的點(diǎn)色數(shù)是 4。 GT MA G AC LA S 選課狀態(tài)圖 5 1 0 x t 0 1 2 ?1 ? 0 1 n 定義 1 設(shè) G是一個(gè)圖，對(duì) G的每個(gè)頂點(diǎn)著色，使得相鄰頂點(diǎn)著不同顏色，稱為對(duì) G的正常頂點(diǎn)著色； 如果用 k種顏色可以對(duì) G進(jìn)行正常頂點(diǎn)著色，稱 G可 k正常頂點(diǎn)著色； 對(duì)圖 G正常頂點(diǎn)著色需要的最少顏色數(shù)，稱為圖 G的點(diǎn)色數(shù)。 把課程模型為圖 G的頂點(diǎn)，兩頂點(diǎn)連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門(mén)課程。 A9: AC, S, LA。 A7: GT, MA, LA 。 A5: AC, LA, S 。 A3: MA, G, LA。 (學(xué)生用 Ai表示） A1: LA, S ?，F(xiàn)有 10名學(xué)生 (如下所示 )需要選修這些課程。 (一 )、相關(guān)概念 課程安排問(wèn)題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。 1 0 x t 0 1 2 ?1 ? 0 1 n Email: 圖論及其應(yīng)用 任課教師：楊春 數(shù)學(xué)科學(xué)學(xué)院 1 1 0 x t 0 1 2 ?1 ? 0 1 n 本次課主要內(nèi)容 (一 )、相關(guān)概念 (二 )、圖的點(diǎn)色數(shù)的幾個(gè)結(jié)論 (三 )、四色與五色定理 圖的頂點(diǎn)著色 (四 )、頂點(diǎn)著色的應(yīng)用 2 1 0 x t 0 1 2 ?1 ? 0 1 n 跟圖的邊著色問(wèn)題一樣，生活中的很多問(wèn)題，可以模型為圖的頂點(diǎn)著色問(wèn)題來(lái)處理。例如課程安排問(wèn)題。要開(kāi)設(shè)的課程為：圖論 (GT), 統(tǒng)計(jì)學(xué) (S),線性代數(shù)(LA), 高等微積分 (AC), 幾何學(xué) (G), 和近世代數(shù) (MA)。根據(jù)這些信息，確定開(kāi)設(shè)這些課程所需要的最少時(shí)間段數(shù)，使得學(xué)生選課不會(huì)發(fā)生沖突。 A2: MA, LA, G 。 A4: G, LA, AC 。 A6: G, AC。 A8: LA,GT, S 。 3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1