排列組合中的涂色問題.ppt

《排列組合中的涂色問題.ppt》由會員分享，可在線閱讀，更多相關《排列組合中的涂色問題.ppt（16頁珍藏版）》請在裝配圖網上搜索。

排列組合中涂色問題,、區(qū)域涂色問題,根據(jù)分步計數(shù)原理，對各個區(qū)域分步涂色，這是處理 染色問題的基本方法。,例1、用5種不同的顏色給圖中標①、②、③、④的 各部分涂色，每部分只涂一種顏色，相鄰部分涂不 同顏色，則不同的涂色方法有多少種？,分析：先給①號區(qū)域涂色有5種方法，再給②號涂色有4種方法， 接著給③號涂色方法有3種，由于④號與①、②不相鄰，因此 ④號有4種涂法，根據(jù)分步計數(shù)原理，不同的涂色方法有,2、根據(jù)共用了多少種顏色討論，分別計算出各種出各種 情形的種數(shù)，再用加法原理求出不同的涂色方法種數(shù)。,例2、（2003江蘇卷）四種不同的顏色涂在如圖所示的6個區(qū)域， 且相鄰兩個區(qū)域不能同色,分析：依題意只能選用4種顏色，要分四類： （1）②與⑤同色、④與⑥同色，則有,（2）③與⑤同色、④與⑥同色，則有,（3）②與⑤同色、③與⑥同色，則有,（5）②與④同色、③與⑥同色，則有,,（4）③與⑤同色、②與④同色，則有,所以根據(jù)加法原理得涂色方法總數(shù)為,例3、（2003年全國高考題）如圖所示，一個地區(qū)分為5個 行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色， 現(xiàn)有4種顏色可供選擇，則不同的著方法共有多少種？,分析：依題意至少要用3種顏色,3.根據(jù)某兩個不相鄰區(qū)域是否同色分類討論，從某兩個不相鄰 區(qū)域同色與不同色入手，分別計算出兩種情形的種數(shù)，再用加 法原理求出不同涂色方法總數(shù)。,例4.用紅、黃、藍、白、黑五種顏色涂在如圖所示的四個區(qū)域內， 每個區(qū)域涂一種顏色，相鄰兩個區(qū)域涂不同的顏色，如果顏色可 以反復使用，共有多少種不同的涂色方法？,4.根據(jù)相間區(qū)使用顏色的種類分類,,例5如圖， 6個扇形區(qū)域A、B、C、D、E、F，現(xiàn)給這6個區(qū)域著色， 要求同一區(qū)域涂同一種顏色，相鄰的兩個區(qū)域不得使用同一種顏色， 現(xiàn)有4種不同的顏色可有多少種方法？,,二、點的涂色問題 方法：（1）可根據(jù)共用了多少種顏色分類討論，（2）根據(jù)相對頂點是否同色分類討論， （3）將空間問題平面化，轉化成區(qū)域涂色 問題。,,四、面涂色問題 例9、從給定的六種不同顏色中選用若干種顏色，將一個正方體的6 個面涂色，每兩個具有公共棱的面涂成不同的顏色，則不同的 涂色方案共有多少種？,分析：顯然，至少需要3三種顏色，由于有多種不同情況， 仍應考慮利用加法原,理分類、乘法原理分步進行討論,