染色法和構(gòu)造法在棋盤上的應用.ppt

1、染色法和構(gòu)造法在棋盤上的應用,廣東北江中學 方奇,1 基本概念 2 棋盤的覆蓋 (1) 同形覆蓋 (2) 異形覆蓋 (3) 小結(jié) 3 馬的遍歷 (1) 馬的哈密爾頓鏈 (2) 馬的哈密爾頓圈 4 其它問題 (1) Worm world 5 結(jié)語,目錄,構(gòu)造法 直接列舉出某種滿足條件的數(shù)學對象或反例導致結(jié)論的肯定與否定，或間接構(gòu) 造某種對應關(guān)系，使問題根據(jù)需要進行轉(zhuǎn)化的方法，稱之為構(gòu)造法 。,染色法 用不同顏色對棋盤格子進行染色，起到分類的效果。 類似國際象棋盤上的黑白二染色，稱為“自然染色”。,棋盤 所謂m*n棋盤，指由m行n列方格構(gòu)成的m*n矩形。每個方格成為棋盤的格，位于 第i行j列的格記

2、為a(i,j)。當i+j為奇（偶）數(shù)時，稱a(i,j)為奇（偶）格。,1 基本概念,2 棋盤的覆蓋,棋盤的覆蓋 指用若干圖形去覆蓋棋盤。覆蓋的每個圖形也由若干格子組成，稱為覆蓋形。約定任兩個覆蓋形互不重疊，任一覆蓋形中任一格總與棋盤上某格重合。 按覆蓋效果，可分為完全覆蓋、飽和覆蓋、無縫覆蓋和互異覆蓋。 完全覆蓋：各個覆蓋形的總格子數(shù)等于棋盤的總格子數(shù) 按覆蓋形，可分為同形覆蓋（只有一種覆蓋形）和異形覆蓋（有多種覆蓋形）。,2-1 同形覆蓋,例1 給出m,n,k，試用若干1*k的矩形覆蓋m*n的棋盤。,分析 有定理1：m*n棋盤存在1*k矩形的完全覆蓋的充分必要 條件是k|m或k|n。 證明：

3、 充分性是顯然的。用構(gòu)造法。當k|n時，每一行用n/k個1*k的矩形恰好完全覆蓋。k|m情況類似。 必要性。當n,m均不能被k整除時，設 m=m1*k+r,0=s (否則旋轉(zhuǎn)90),2-1 同形覆蓋,m=m1*k+r n=n1*k+s r=s,2-1 同形覆蓋,由上面的定理1，可徹底解決m*n棋盤的p*q矩形完全覆蓋問題 定理2 m*n棋盤存在p*q矩形的完全覆蓋充分必要條件是m,n滿足下列條件之一： （i） p|x且q|y （ii） p|x,q|x,且存在自然數(shù)a,b，使y=ap+bq 其中x,y=m,n,2-2 異形覆蓋,例2 設有m*n的棋盤，當m*n為奇數(shù)時，嘗試刪去一個格子，剩下部分

4、用若干1*2的矩形覆蓋；當m*n為偶數(shù)時，嘗試刪去兩個格子，剩下部分用若干1*2的矩形覆蓋。,分析： 1 先來考慮m*n為奇數(shù)的情況 一方面，將棋盤自然染色。無論怎么放，一個1*2的矩形必蓋住一個黑格和一個白格，而棋盤上的黑格比白格多1，于是只能去掉一個黑格(即偶格) 。,2-2 異形覆蓋,另一方面，設去掉偶格為a(i,j)，用構(gòu)造法必能得到可行解,i與j同為奇數(shù),i與j同為偶數(shù),2-2 異形覆蓋,再考慮m*n為偶數(shù)的情況 類似地，由自然染色法得知，去掉的兩格必定異色，即一個奇格，一個偶格（不然兩種格子總數(shù)不等） 另一方面，用構(gòu)造法，總可以用一些粗線將棋盤隔成寬為1的長條路線，使從任一格出發(fā)可

5、以不重復地走遍棋盤并回到出發(fā)點。,2-2 異形覆蓋,針對染色法，上面的例子都是利用“各類顏色格子總數(shù)必須相等”這一條件推出矛盾，但有些時候，只考慮這個條件是不夠充分的。,例3 8*8棋盤剪去哪個方格才能用21個1*3的矩形覆蓋？,分析 考慮到對稱性，只有剪去a(3,3)、a(3,6)、a(6,3)、a(6,6)中的某一個才能滿足題意。,藍色：21個 白色：22個 黑色：21個,覆蓋類問題其實是一個難度較大的課題，這里只討論了一些簡單的情況，以說明染色法與構(gòu)造法的應用 需要補充的是，染色法的種類形形色色、五花八門。考慮到可推廣性和易操作性，本文只著重研究了“間隔染色法”（即自然染色法的推廣）,2

6、-3 小結(jié),3 馬的遍歷,馬行走規(guī)則 從2*3的矩形一個角按對角線跳到另一個角上 馬的遍歷 從一個格出發(fā)按跳馬規(guī)則不重復地走遍所有格 棋盤中馬的遍歷問題分兩類 (1) 馬的哈密爾頓鏈 (2) 馬的哈密爾頓圈,3-2 馬的哈氏鏈,通常有三種方法 貪心法每一步跳向度最小的點 （度數(shù)指可一步到達且未經(jīng)過的點的個數(shù)） 分治法將棋盤分成幾個小棋盤，分別找哈氏鏈，再接起來 鑲邊法先在一個小棋盤中找到哈氏鏈，然后在棋盤四周鑲邊，已產(chǎn)生大棋盤的哈氏鏈。 按上述方法不難得到下面結(jié)論： n*n棋盤存在哈氏鏈的充要條件是n3。,3-2 馬的哈氏圈,例4 求n*n棋盤的哈氏圈,分析 ： 將棋盤自然染色，考察無解情況。

7、 馬無論怎么走，都必須按黑格白格黑格白格如此循環(huán)。由于要回到起點（起點與終點同色），途經(jīng)兩種顏色的格子數(shù)必相等，可知n為奇數(shù)時無解。 因為大小限制，n6時也無解,3-2 馬的哈氏圈,當n=6且為偶數(shù)時，用鑲邊法構(gòu)造 n*n的大矩形是由(n-4)*(n-4)的小矩形套上一個寬為2的環(huán)組成的。而寬為2的環(huán)有一個特點，就是可用四條回路A、B、C、D剛好覆蓋 假設(n-4)*(n-4)的棋盤已找到哈氏圈 那么只要設法將A、B、C、D四條回路嵌入其中，則n*n的矩形的哈式圈就構(gòu)造出來了,3-2 馬的哈氏圈,1） n除以4余2時， 在內(nèi)矩形四個角（A、E、I、M）上分別開口。,1 將C與D所在的外回路與“

8、內(nèi)矩形”的回路在A、B上對接，變成A-C-D-B 2 將G與H所在的外回路與“內(nèi)矩形”的回路在E、F上對接，變成E-G-H-F 3 將K與L所在的外回路與“內(nèi)矩形”的回路在I、J上對接，變成I-K-L-J 4 將O與P所在的外回路與“內(nèi)矩形”的回路在M、N上對接，變成M-O-P-N,3-2 馬的哈氏圈,2） n除以4余0時 在內(nèi)矩形四個角（A、E、I、M）上分別開口。,1 將C與D所在的外回路與“內(nèi)矩形”的回路在A、B上對接，變成A-C-D-B 2 將G與H所在的外回路與“內(nèi)矩形”的回路在E、F上對接，變成E-G-H-F 3 將K與L所在的外回路與“內(nèi)矩形”的回路在I、J上對接，變成I-K-L

9、-J 4 將O與P所在的外回路與“內(nèi)矩形”的回路在M、N上對接，變成M-O-P-N,3-2 馬的哈氏圈,一個猜想： m*n（m=n）棋盤不存在哈氏圈的充要條件是： m,n滿足下列條件之一 （1） m,n都是奇數(shù) （2） m=1,2或4 （3） m=3且n=4,6,8 還沒有證明, 其它應用,例5 蠕蟲世界 （Uva） 蠕蟲在一張N*N的網(wǎng)上爬行。每個網(wǎng)格上有一個數(shù)字，蠕蟲不能經(jīng)過相同的數(shù)字兩次。開始的時候，蠕蟲任意選擇一個格子作為起始點。它爬行只能沿水平或豎直方向，且不能超出網(wǎng)外。蠕蟲如何移動才能到達盡可能多的網(wǎng)格呢？右面是一個樣例。, 其它應用, 分析： 采用“染色法”貪心出一個上界。 1 自然染色 2 設Tfree,Tblack,Twhite分別記錄三類格子數(shù)量 對每一種數(shù)字（1，2，3）分析 1）只存在標有該數(shù)字的白色格子，TwhiteTwhite+1 2）只存在標有該數(shù)字的黑色格子，TblackTblack+1 3）存在標有該數(shù)字的黑白兩色格子，TfreeTfree+1 3 估價上界 Lmax= (Twhite+Tfree)*2+1 (Twhit