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

Van Anh Ngày: 03-07-2023 Lớp 11
466
466

Với giải Luyện tập 2 trang 46 Chuyên đề Toán 11 Cánh diều chi tiết trong Bài 2: Một vài ứng dụng của lí thuyết đồ thị giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập Chuyên đề Toán 11. Mời các bạn đón xem:

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

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.

Lời giải:

Luyện tập 2 trang 46 Chuyên đề học tập Toán 11 Cánh diều

Dễ thấy đồ thị Hình 24 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 = 3 km;

Từ B, đỉnh chưa đến gần nhất là C, BC = 5 km;

Từ C, đỉnh chưa đến gần nhất là D, CD = 5 km;

Từ D, đỉnh chưa đến gần nhất là E, DE = 9 km;

Từ E, đỉnh chưa đến gần nhất là F, EF = 6 km;

Đến đây không còn đỉnh chưa đến, vì vậy quay về A, FA = 4 km.

Tổng quãng đường theo chu trình ABCDEFA là: 3 + 5 + 5 + 9 + 6 + 4 = 32 (km).

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ều dài (km)

A

ABCDEFA

32

B

BAFEDCB

32

C

CBAFEDC

32

C

CDEFABC

32

D

DCBAFED

32

E

EFABCDE

32

F

FABCDEF

32

Vậy người giao hàng chọn 1 đường đi trong 7 đường đi trên thì quãng đường phải di chuyển là ngắn nhất.

Xem thêm lời giải bài tập Chuyên đề học tập 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, mô phỏng những vấn đề của khoa học và thực tiễn thành những mô hình toán học. Vì thế, các kết quả của Lí thuyết đồ thị có nhiều ứng dụng trong khoa học và thực tiễn.....

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 với độ dài lần lượt là 15 km, 20 km, 16 km. Sử dụng đồ thị để mô tả tình huống đó....

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 với độ dài (đơn vị: kilômét) được mô tả bằng đồ thị có trọng số ở Hình 24. Người giao hàng cần đi giao hàng tại sáu địa điểm trên. Người giao hàng xuất phát từ một địa điểm nào đó, đi qua các địa điểm còn lại để giao hàng và trở về địa điểm ban đầu. Hãy tìm một đường đi thỏa mãn điều kiện trên cho người giao hàng sao cho quãng đường mà người giao hàng phải di chuyển là ngắn nhất....

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 (đơn vị: Megabit/ giây, kí hiệu là Mbps) giữa một số thành phố. Vẽ một đồ thị sử dụng điểm, đường để biểu diễn mạng lưới đó.....

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 (đơn vị: kilômét) mô tả trong Hình 32. Sử dụng thuật toán láng giềng gần nhất, tìm các chu trình xuất phát từ một đỉnh đi qua tất cả các địa điểm, mỗi địa điểm đúng một lần sao cho tổng độ dài các cạnh của chu trình là nhỏ nhất.....

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 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 đối với đồ thị ở Hình 34, số ghi trên mỗi cạnh của đồ thị mô tả độ dài quãng đường giữa các địa điểm (đơn vị: kilômét)....

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 cuộc triển lãm của bảo tàng đến ba trường học trong khu vực. Người đó muốn đến từng trường và quay trở lại bảo tàng sau khi thăm cả ba trường. Thời gian di chuyển (đơn vị: phút) giữa các trường học và giữa bảo tàng với mỗi trường học được mô tả trong Hình 35.....

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

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 2: Một vài ứng dụng của lí thuyết đồ thị

Xem thêm các nội dung khác:

Từ khóa :
Toán 11
Đánh giá

0

0 đánh giá

Đánh giá
Bài viết cùng môn học
Toán Tổng hợp kiến thức
Biết a - b chia hết cho 6 chứng minh rằng các biểu thức sau cũng chia hết cho 6
Biết a - b chia hết cho 6 chứng minh rằng các biểu thức sau cũng chia hết cho 6 Lữ Ngọc My My
164
Toán Tổng hợp kiến thức
Tìm các tập hợp Ư(8); Ư(12); Ư(15)
Tìm các tập hợp Ư(8); Ư(12); Ư(15) Lữ Ngọc My My
137
Toán Tổng hợp kiến thức
Tìm BCNN của 84 và 108
Tìm BCNN của 84 và 108 Lữ Ngọc My My
115
Toán Tổng hợp kiến thức
Cho biết cos∝ = 12/13 giá trị của tan ∝ là
Cho biết cos∝ = 12/13 giá trị của tan ∝ là Lữ Ngọc My My
110

Tìm kiếm

tailieugiaovien.com.vn

Bài Viết Xem Nhiều

CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK

- Người đại diện: Nguyễn Thanh Tuyền

- Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.

© 2021 Vietjack. All Rights Reserved.

DMCA.com Protection Status