Giải Bài toán tô màu các hình vuông

GiảiBàitoántômàucáchìnhvuông
I .Bàitoán:(Nhiềuphụhuynh HS đauđầu )
Zing vnđưarabàitoáncủatrangfuzzle: Cho lưới ô vuông 4/4, (hãydùng 5 màutôhếtcác ô vuôngnhỏsaochocác ô nhỏ ở hàngngang, .
*Đápán I
/
*Đápán II
/ô
*Cáchgiải
- Người ta đãchứng minh rằng: Vớiđiềukiệnbàitoántrênthìsốmàutốithiểulà 5 (nếu 4 mầuthìbớt 1 đk ;xemphầnthamkhảo);
chỉcó 1 màucho 4 ô, cònlại 4 màuthìmỗimàucho 3 ô (cộng = 16 ô
- Giảsử ta có 5 màu 1=đỏ; 2=hồng; 3=lam; 4=vàng; 5=lục
Ta sẽdùngđỏ( 4 ô; hồng, lamvàng, lục( 3x4 ô
Chia ô vuôngthành 2 phần: Vòngngoài 12 ô;
Phầnlõicó 4 ônhưhìnhbên(
Màuđỏtô 4 ô: chỉcócác ô vòngngoàimàkhôngnằm ở đỉnh (đólà A2-C1-D3-B4hoặc A3-B1-D2-C4)
Cáchchọn ô tômàutiếptheoluôngiốngnhưnướcđiquânMã (trongcờtướng)
/
- Tô 4 ô vòng lõi theo 4 màu còn lại, ta có 4 cách chọn
- Từ 4 phương án trên, chọn tiếp cũng theo “nướcđiquânMã” mỗi màu lại có 2 cách đi ,
- Do đó tổng số ta có 4x2x2 = 16 đáp án thỏa mãn


II. BàitoánthamkhảoTômàubảnđồ
Trêncác bảnđồ, cácmiềnkhácnhau (miền ở đâyđượchiểulàcácquốcgiatrênbảnđồthếgiới hay cáctỉnhtrongmộtbảnđồhànhchínhquốcgia) đượctômàusaocho 2 miềncóchungbiêngiớikhôngtrùngmàunhau. Đốivớibảnđồcónhiềumiền, nếu ta dùngmộtsốlượnglớnmàuthìsẽrấtkhóphânbiệtcácmiềncómàugầngiốngnhau, vìthếngười ta chỉdùngmộtsốlượngmàunhấtđịnhđểtômàubảnđồ. Mộtbàitoánđượcđặtralà: cóthểdùngítnhấtbaonhiêumàuđểtômàumộtbảnđồsaochocácmiềnkềnhaukhôngcùngmộtmàu[2] (tr.593).
Bàitoánnàydẫnđến địnhlýbốnmàu nổitiếngvà địnhlýnămmàu3Cácdạngbàitoántômàubảnđồcóthểápdụng Thuậttoántômàu Greedy đểtìmrasốmàuítnhấtđểtôchocácmiềntrênbảnđồ.
Địnhlýbốnmàu (còngọilà địnhlýbảnđồbốnmàu) phátbiểurằng: đốivớibấtkỳmặtphẳngnàođược chia thànhcácvùngphânbiệt, chẳnghạnnhưbảnđồhànhchínhcủamộtquốcgia, chỉcầndùngtốiđabốnmàuđủđểphânbiệtcácvùnglâncậnvớinhau. Haivùngđượccoilàlâncậnnếunhưchúngcóchungnhaumộtđoạnđườngbiên, khôngtínhchungnhaumộtđiểm.
Địnhlýnămmàu (còngọilà địnhlýbảnđồnămmàu): Làmộtkếtquảtừ Lýthuyếtđồthị, cụthểlàmọibảnđồđềucóthểtôbằngnămmàusaochohainướcnằmkềnhauphảiđượctôbằnghaimàukhácnhau.
Mặcdùđâylàđịnhlýyếuhơn địnhlýbốnmàu, nhưngcáchchứng minh nàycũngđóngvaitròquantrọngbởivìđâylàcơsởbướcđầuđểthiếtlậpcáchchứng minh trọnvẹncho địnhlýbốnmàu màphảikiểmtrabằngchươngtrìnhmáytính.



PHH sưutầmđề&biênsoạnbàigiải 10 – 10 - 2016