Tìm kiếm Đề thi, Kiểm tra

Quảng cáo

Quảng cáo

Hướng dẫn sử dụng thư viện

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (04) 66 745 632
  • 0166 286 0000
  • contact@bachkim.vn

giải bài toán tô màu

Nhấn vào đây để tải về
Hiển thị toàn màn hình
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn: sưu tầm
Người gửi: nguyễn phương
Ngày gửi: 10h:50' 20-03-2017
Dung lượng: 73.8 KB
Số lượt tải: 8
Số lượt thích: 0 người
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

 
Gửi ý kiến

↓ CHÚ Ý: Bài giảng này được nén lại dưới dạng RAR và có thể chứa nhiều file. Hệ thống chỉ hiển thị 1 file trong số đó, đề nghị các thầy cô KIỂM TRA KỸ TRƯỚC KHI NHẬN XÉT  ↓