Giải bài 4 trang 49 Chuyên đề học tập Toán 11 Cánh diều

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

Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Cánh diều

Toán - Văn - Anh - Lí - Hóa - Sinh

Đề bài

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).

Phương pháp giải - Xem chi tiết

Bước 1. Chọn một đỉnh bắt đầu, ta gọi là đỉnh V.

Bước 2. Xuất phát từ đỉnh hiện hành, chọn cạnh có độ dài nhỏ nhất nối đến một trong các đỉnh chưa đến. Đánh dấu đỉnh cuối của cạnh vừa chọn.

Bước 3. Xuất phát từ đỉnh vừa đánh dấu, nếu còn đỉnh chưa đến thì quay lại bước 2.

Bước 4. Quay lại đỉnh V.

Lời giải chi tiết

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

Ta thấy chu trình xuất phát từ đỉnh A là AEDBCA thỏa mãn đề bài với tổng quãng đường nhỏ nhất là AE + ED + DB + BC + CA = 5 + 5 + 3 + 5 + 3 = 21 (km).

Các chu trình xuất phát từ đỉnh B, C, D, E có 1 đỉnh được đi qua hai lần nên không thỏa mãn quy tắc của thuật toán láng giềng gần nhất nên loại.

Bình luận

Chia sẻ

Bình chọn:

4.9 trên 7 phiếu

Bài tiếp theo

Giải bài 5 trang 49 Chuyên đề học tập Toán 11 Cánh diều
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.
Giải bài 3 trang 49 Chuyên đề học tập Toán 11 Cánh diều
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).
Giải bài 2 trang 49 Chuyên đề học tập Toán 11 Cánh diều
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.
Giải bài 1 trang 49 Chuyên đề học tập Toán 11 Cánh diều
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 đó.
Giải mục 2 trang 47, 48 Chuyên đề học tập Toán 11 - Cánh diều
Hexane C6H14 có năm đồng phân. Vẽ đồ thị tương ứng với năm đồng phân đó.
Giải mục 1 trang 44, 45, 46 Chuyên đề học tập Toán 11 - Cánh diều
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 đó.
Giải khởi động trang 44 Chuyên đề học tập Toán 11 - Cánh diều
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.