Hãy cho ví dụ về đồ thị có trọng số.

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

Ví dụ về đồ thị có trọng số: Có 4 trạm xe bus A, B, C, D được nối với nhau theo những con đường AB, BC, CD, DA với độ dài lần lượt là 3 km, 2 km, 5 km, 6 km. Ta có đồ thị mô tả tình huống trên như sau.

Hãy cho ví dụ về đồ thị có trọng số. (ảnh 1)

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

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.

Xem đáp án

Lời giải

Để 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.

Câu 2

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 3