Tìm kiếm

Quảng cáo

Hỗ trợ kĩ thuật

Quảng cáo

Quảng cáo

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Chào mừng quý vị đến với Thư viện Đề thi & Kiểm tra.

    Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình.
    Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải.

    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: 7
    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  ↓