5-1引言v第六章圖七巧板涂色問題【問題】假設(shè)有下圖所示七巧板，使用至多4種不同顏色對七巧板涂色，要求每個區(qū)域涂一種顏色，相鄰區(qū)域的顏色互不相同。求涂色方案。抽象ABEDCFGDAFECGB【想法——數(shù)據(jù)模型】將七巧板的每個區(qū)域看成一個頂點，如果兩個區(qū)域相鄰，則這兩個頂點之間有邊相連，從而將七巧板抽象為圖結(jié)構(gòu)?！締栴}】某公司生產(chǎn)若干種化學(xué)制品，其中有些制品如果放在一起可能產(chǎn)生化學(xué)反應(yīng)，因此公司必須將倉庫分成相互隔離的若干區(qū)，請設(shè)計合理的倉庫分區(qū)。國際學(xué)術(shù)會議【想法——數(shù)據(jù)模型】將成員看成一個頂點，如果兩個成員可以直接交談，則這兩個頂點之間有邊相連，從而將分組問題抽象為圖結(jié)構(gòu)——二部圖。ABEDCF【問題】出席某國際會議的六個成員A、B、C、D、E、F，假設(shè)A會講漢語、法語和日語，B會講德語、日語和俄語，C會講英語和法語，D會講漢語和西班牙語，E會講英語和德語，F(xiàn)會講俄語和西班牙語，如將此六人分成兩組，能否出現(xiàn)同一組內(nèi)任意兩人不能直接交談的情況？V1={A,E,F}V2={B,C,D}【問題】排課問題。教室構(gòu)成一組頂點，課程構(gòu)成一組頂點，如果A教室可以安排B課程，則頂點A和B之間有一條邊。農(nóng)夫過河問題【問題】農(nóng)夫過河問題。一個農(nóng)夫帶著一只狼、一只羊和一筐菜，想從河一邊（左岸）乘船到另一邊（右岸），由于船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河，但是如果沒有農(nóng)夫看管，則狼會吃羊，羊會吃菜。其給出過河方案?！鞠敕ā獢?shù)據(jù)模型】用0表示在河的左岸，用1表示在河的右岸，將每一個可能的狀態(tài)抽象為一個頂點，邊表示狀態(tài)轉(zhuǎn)移發(fā)生的條件。左岸河右岸農(nóng)夫

狼

羊

菜

0000農(nóng)夫

羊

1010農(nóng)夫和羊0000010000010101001010101011110111111110教學(xué)計劃編排【問題】已知計算機(jī)專業(yè)的核心課程如下表所示，編制合適的教學(xué)計劃。【想法——數(shù)據(jù)模型】用頂點表示課程，如果從頂點

ci到

cj之間存在邊<ci,cj>，則表示課程

ci是課程

cj的先修課。課程編號課程名稱先修課程c1程序設(shè)計基礎(chǔ)無c2電子技術(shù)基礎(chǔ)無c3離散數(shù)學(xué)c1c4數(shù)據(jù)結(jié)構(gòu)c1c5計算機(jī)原理c1c2c6操作系統(tǒng)c3c4c5c7計算機(jī)網(wǎng)絡(luò)c4c5c6c8數(shù)據(jù)庫原理及應(yīng)用c4c5c2c1c3c4c5c8c6c7社交網(wǎng)絡(luò)路徑規(guī)劃關(guān)于圖結(jié)構(gòu)什么是圖？在邏