![第5節(jié)圖著色的應(yīng)用_第1頁](http://file3.renrendoc.com/fileroot_temp3/2022-2/26/70f71958-7782-470b-ba85-de7fc727fd13/70f71958-7782-470b-ba85-de7fc727fd131.gif)
![第5節(jié)圖著色的應(yīng)用_第2頁](http://file3.renrendoc.com/fileroot_temp3/2022-2/26/70f71958-7782-470b-ba85-de7fc727fd13/70f71958-7782-470b-ba85-de7fc727fd132.gif)
![第5節(jié)圖著色的應(yīng)用_第3頁](http://file3.renrendoc.com/fileroot_temp3/2022-2/26/70f71958-7782-470b-ba85-de7fc727fd13/70f71958-7782-470b-ba85-de7fc727fd133.gif)
![第5節(jié)圖著色的應(yīng)用_第4頁](http://file3.renrendoc.com/fileroot_temp3/2022-2/26/70f71958-7782-470b-ba85-de7fc727fd13/70f71958-7782-470b-ba85-de7fc727fd134.gif)
![第5節(jié)圖著色的應(yīng)用_第5頁](http://file3.renrendoc.com/fileroot_temp3/2022-2/26/70f71958-7782-470b-ba85-de7fc727fd13/70f71958-7782-470b-ba85-de7fc727fd135.gif)
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第五節(jié)圖著色的應(yīng)用貯藏問題:某工廠生產(chǎn)n種化學(xué)制品c1,c2,cn,其中某些制品是互不相容.若它們相互,則會發(fā)生化學(xué)反應(yīng)甚至引起爆炸,為安全起見,該工廠必須把倉庫分成若干隔間,以便把不相容的化學(xué)制品儲藏在不同的隔間,試問該倉庫至少應(yīng)分成幾個(gè)隔間?解:構(gòu)建簡單圖G=,其中V(G)=c1,c2,cn 邊ci,cjE(G)化學(xué)制品ci與cj互不相容. 易知,倉庫的最少隔間數(shù)等于圖G的色素x(G).電視頻道分配問題 某地區(qū)內(nèi)有n家電視發(fā)射臺T1,T2,Tn.主管部門為每家電視發(fā)射臺分配一個(gè)頻道.為排除干擾,使用同一頻道的電視臺之間的距離必須大于指定的正數(shù)d,試問該地區(qū)至少需要多少頻道? 構(gòu)建簡單圖G=
2、,其中V(G)=T1,T2,Tn 邊Ti, TjE(G)Ti與Tj之間距離d. 易知,需要的最少頻道等于圖G的色素x(G).考試安排問題 某高校有n門選修課程v1,v2,vn需要進(jìn)行期末考試.同一學(xué)生不能在同一天里參加兩門課程的考試.問學(xué)校的期末考試需要幾天? 構(gòu)建簡單圖G=,其中V(G)=v1,v2,vn 邊vi, vjE(G)vi與vj被同一同學(xué)選修. 故考試需要的最小天數(shù)等于圖G的色素x(G).變址寄存器 在有效的編譯器里,當(dāng)把頻繁使用的變量暫時(shí)保存在中央處理單元而不是保存在常規(guī)內(nèi)存時(shí),可以加速循環(huán)的執(zhí)行.對于給定的循環(huán)來說,需要多少個(gè)變址寄存器? 可以這樣建立模型:設(shè)圖里的每個(gè)頂點(diǎn)表示
3、循環(huán)里的一個(gè)變量.若在循環(huán)執(zhí)行期間兩個(gè)頂點(diǎn)所表示的變量必須同時(shí)保存在變址寄存器里,則這兩個(gè)頂點(diǎn)之間有邊.因此,所需要的變址寄存器數(shù)就是該圖的色數(shù).順序著色算法 到目前為止,還沒有一個(gè)有效算法來確定色素.順序著色算法是一個(gè)求x(G)的有效算法:設(shè)G=是簡單無向圖,V=x1,x2xn用N(xi)表示與xi相鄰的全部頂點(diǎn)集合;對頂點(diǎn)xi著色C,記為(xi)=c.i:=1c:=1若對y xi (y)c, 則令(xi)=c并轉(zhuǎn)入第5步。c:=c+1并轉(zhuǎn)入第3步。(1) 若in,則i:=i+1并轉(zhuǎn)回第2步,否則停止.定理定理1 1設(shè)設(shè)G G是簡單連通圖,順序著色法產(chǎn)生是簡單連通圖,順序著色法產(chǎn)生G G的頂
4、的頂點(diǎn)的一個(gè)點(diǎn)的一個(gè) (G(G)+1+1著色,所以著色,所以 (G)(G)(G G)+1+1證明證明:順序著色法用語言描述就是一次考慮每一頂點(diǎn)順序著色法用語言描述就是一次考慮每一頂點(diǎn),將將尚未指定給與其鄰接的頂點(diǎn)的最小顏色指定給該頂點(diǎn)尚未指定給與其鄰接的頂點(diǎn)的最小顏色指定給該頂點(diǎn),特特別是決不能將兩個(gè)相鄰頂點(diǎn)指定為相同的顏色別是決不能將兩個(gè)相鄰頂點(diǎn)指定為相同的顏色,因此順序因此順序著色算法確實(shí)產(chǎn)生一個(gè)頂點(diǎn)著色著色算法確實(shí)產(chǎn)生一個(gè)頂點(diǎn)著色.最多存在最多存在 個(gè)頂點(diǎn)與個(gè)頂點(diǎn)與x xi i鄰接鄰接, ,故在故在x x1 1,x,x2 2,x,xi-1i-1中最多有中最多有 個(gè)頂點(diǎn)個(gè)頂點(diǎn)x xi i鄰
5、接鄰接. .所以所以, ,當(dāng)算法對頂點(diǎn)當(dāng)算法對頂點(diǎn)x xi i著色時(shí)著色時(shí), ,在顏色在顏色1,2, 1,2, +1+1中至少有一中至少有一種顏色尚未指定給與種顏色尚未指定給與x xi i鄰接的頂點(diǎn)并且算法將這些顏色鄰接的頂點(diǎn)并且算法將這些顏色中最小的指定給中最小的指定給x xi i, ,于是順序著色算法產(chǎn)生圖于是順序著色算法產(chǎn)生圖G G的頂點(diǎn)的的頂點(diǎn)的一個(gè)一個(gè) +1+1著色著色. .例例1 1試用順序著色法求圖試用順序著色法求圖G G的色數(shù)。的色數(shù)。1121211212121231321212121231 定理定理1給出了連通簡單圖給出了連通簡單圖G的色數(shù)的上界的色數(shù)的上界.1941年年R.L.Brooks證明了下面的定理證明了下面的定理.定理定理2.設(shè)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 胸外科護(hù)士工作心得
- 2025年全球及中國單擺銑頭行業(yè)頭部企業(yè)市場占有率及排名調(diào)研報(bào)告
- 2025-2030全球倒置行星滾柱絲杠行業(yè)調(diào)研及趨勢分析報(bào)告
- 2025年全球及中國虛擬試穿平臺行業(yè)頭部企業(yè)市場占有率及排名調(diào)研報(bào)告
- 2025年全球及中國汽車天線定位器行業(yè)頭部企業(yè)市場占有率及排名調(diào)研報(bào)告
- 2025年全球及中國重載有軌穿梭小車(RGV)行業(yè)頭部企業(yè)市場占有率及排名調(diào)研報(bào)告
- 2025年全球及中國絲素蛋白敷料行業(yè)頭部企業(yè)市場占有率及排名調(diào)研報(bào)告
- 2025-2030全球直線式桁架機(jī)器人行業(yè)調(diào)研及趨勢分析報(bào)告
- 2025-2030全球裝運(yùn)前檢驗(yàn)(PSI)服務(wù)行業(yè)調(diào)研及趨勢分析報(bào)告
- 2025年全球及中國電子鑰匙柜行業(yè)頭部企業(yè)市場占有率及排名調(diào)研報(bào)告
- 江西省部分學(xué)校2024-2025學(xué)年高三上學(xué)期1月期末英語試題(含解析無聽力音頻有聽力原文)
- GA/T 2145-2024法庭科學(xué)涉火案件物證檢驗(yàn)實(shí)驗(yàn)室建設(shè)技術(shù)規(guī)范
- 2024年中考語文試題分類匯編:非連續(xù)性文本閱讀(學(xué)生版)
- 2024年度窯爐施工協(xié)議詳例細(xì)則版B版
- 第一屆山東省職業(yè)能力大賽濟(jì)南市選拔賽制造團(tuán)隊(duì)挑戰(zhàn)賽項(xiàng)目技術(shù)工作文件(含樣題)
- 尿毒癥替代治療
- 【課件】2025屆高考英語一輪復(fù)習(xí)小作文講解課件
- 基底節(jié)腦出血護(hù)理查房
- 工程公司總經(jīng)理年終總結(jié)
- 2024年海南省高考地理試卷(含答案)
- 【企業(yè)盈利能力探析的國內(nèi)外文獻(xiàn)綜述2400字】
評論
0/150
提交評論