Nội dung bài viết

    Xem thêm

    Giả sử chi phí di chuyển giữa các địa điểm được mô tả ở Hình 33 (đơn vị: nghìn đồng)

    Lời giải Bài 3 trang 49 Chuyên đề Toán 11 sách Chuyên đề học tập Toán lớp 11 Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng trả lời các câu hỏi & làm bài tập.

    1 227 03/07/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Chuyên đề Toán 11 Cánh diều Bài 2: Một vài ứng dụng của lí thuyết đồ thị

    Bài 3 trang 49 Chuyên đề Toán 11: Giả sử chi phí di chuyển giữa các địa điểm được mô tả ở Hình 33 (đơn vị: nghìn đồng). Ta nên chọn theo chu trình nào đi qua tất cả các địa điểm để tổng chi phí di chuyển là thấp nhất? Chi phí thấp nhất đó bằng bao nhiêu?

    Bài 3 trang 49 Chuyên đề học tập Toán 11 Cánh diều

    Lời giải:

    Dễ thấy đồ thị Hình 33 có chu trình Hamilton.

    +) Sử dụng thuật toán láng giềng gần nhất đối với đỉnh xuất phát A, ta có:

    Từ A, đỉnh gần nhất là B, AB = 20 nghìn đồng;

    Từ B, đỉnh chưa đến gần nhất là C, BC = 30 nghìn đồng;

    Từ C, đỉnh chưa đến gần nhất là D, CD = 12 nghìn đồng;

    Đến đây không còn đỉnh chưa đến, vì vậy quay về A, DA = 35 nghìn đồng.  

    Tổng chi phí di chuyển theo chu trình ABCDA là: 20 + 30 + 12 + 35 = 97 (nghìn đồng).

    Tương tự bắt đầu với những đỉnh khác, ta có bảng sau:

    Đỉnh bắt đầu

    Chu trình

    Tổng chi phí (nghìn đồng)

    A

    ABCDA

    97

    B

    BADCB

    97

    C

    CDBAC

    108

    D

    DCBAD

    97

    Vậy có ba chu trình ABCDA, BADCB, DCBAD thỏa mãn đề bài và chi phí thấp nhất là 97 nghìn đồng.

    Xem thêm lời giải bài tập Chuyên đề Toán lớp 11 Cánh diều hay, chi tiết khác:

    Khởi động trang 44 Chuyên đề Toán 11: Như chúng ta đã biết, Lí thuyết đồ thị ra đời trong quá trình khái quát...

    Hoạt động 1 trang 44 Chuyên đề Toán 11: Giả sử ba địa điểm A, B, C được nối với nhau theo những con đường AB, BC, CA...

    Luyện tập 1 trang 44 Chuyên đề Toán 11: Hãy cho ví dụ về đồ thị có trọng số.

    Hoạt động 2 trang 44 Chuyên đề Toán 11: Giả sử có sáu địa điểm A, B, C, D, E, F được nối với nhau theo những con đường ...

    Luyện tập 2 trang 46 Chuyên đề Toán 11: Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2.

    Luyện tập 3 trang 47 Chuyên đề Toán 11: Hexane C6H14 có năm đồng phân. Vẽ đồ thị tương ứng với năm đồng phân đó.  

    Bài 1 trang 49 Chuyên đề Toán 11: Hình 31 biểu diễn mạng lưới máy chủ và tốc độ truyền dữ liệu...

    Bài 2 trang 49 Chuyên đề Toán 11: Có bốn địa điểm với độ dài quãng đường giữa các địa điểm...

    Bài 3 trang 49 Chuyên đề Toán 11: Giả sử chi phí di chuyển giữa các địa điểm được mô tả ở Hình 33 ...

    Bài 4 trang 49 Chuyên đề Toán 11: Sử dụng thuật toán láng giềng gần nhất, hãy giải bài toán người giao hàng...

    Bài 5 trang 49 Chuyên đề Toán 11: Một nhân viên của bảo tàng nghệ thuật đang có kế hoạch giới thiệu nội dung...

    Xem thêm lời giải bài tập Chuyên đề Toán lớp 11 Cánh diều hay, chi tiết khác:

    Bài 1: Phép dời hình

    Bài 2: Phép đồng dạng

    Bài 1: Một vài yếu tố của lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton

    Bài 1: Một số nội dung cơ bản về vẽ kĩ thuật

    Bài 2: Đọc và vẽ bản vẽ kĩ thuật đơn giản

    Tham khảo các loạt bài Toán 11 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 227 03/07/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: