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.

Câu hỏi trong đề: Chuyên đề Toán 11 Cánh diều Chuyên đề 2. Làm quen với một vài yếu tố của lí thuyết đồ thị có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

Để tìm quãng đường đi ngắn nhất trên đồ thị có trọng số, ta áp dụng thuật toán láng giềng gần nhất để tìm tất cả các chu trình xuất phát từ một đỉnh ban đầu, đi qua các đỉnh khác và trở về đỉnh ban đầu sao cho tổng độ dài các cạnh của chu trình đó là ngắn nhất. Sau đó, ta so sánh độ dài của tất cả các chu trình “tốt nhất” vừa tìm được để tìm ra chu trình có tổng độ dài các cạnh là ngắn nhất. Việc giải cụ thể Hoạt động 2 trang 46, ta cùng xem chi tiết ở Luyện tập 2 trang 46.

Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

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.

Tìm chu trình xuất phát từ viện bảo tàng sao cho thời gian đi là ít nhất.

Xem đáp án

Lời giải

Từ viện bảo tàng, thời gian di chuyển đến trường A là ngắn nhất: 19 phút.

Từ trường A, thời gian di chuyển đến trường B là ngắn nhất: 38 phút.

Từ trường B, thời gian di chuyển đến trường C là ngắn nhất: 32 phút.

Đến đây, không còn địa điểm nào chưa đi qua nên quay lại viện bảo tàng với thời gian di chuyển: 51 phút.

Do đó, chu trình xuất phát từ viện bảo tàng, qua trường A, trường B, trường C rồi quay lại viện bảo tàng có thời gian đi là ít nhất và thời gian đi là: 19 + 38 + 32 + 51 = 140 (phút).

Câu 2

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.

Xem đáp án

Lời giải

Dễ thấy đồ thị Hình 32 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à C, AC = 3 km;

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

Từ D, đỉnh chưa đến gần nhất là B, DB = 10 km;

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

Tổng quãng đường theo chu trình ACDBA là: 3 + 8 + 10 + 4 = 25 (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	ACDBA	25
B	BACDB	25
C	CABDC	25
D	DCABD	25

Các chu trình trên thỏa mãn điều kiện 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 và tổng độ dài các cạnh của chu trình là nhỏ nhất.

Câu 3