Giáo án điện tử 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ị

CHÀO MỪNG CÁC EM ĐẾN VỚI TIẾT HỌC MỚI!

KHỞI ĐỘNG

Lí thuyết đồ thị có thể giải quyết những vấn đề thực tiễn nào?

BÀI 2: 

MỘT VÀI ỨNG DỤNG CỦA LÍ THUYẾT ĐỒ THỊ 

NỘI DUNG BÀI HỌC

...........................................

2. Thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số

HĐ2:

Giả sử có sáu địa điểm đượ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.

Một người giao hàng cần đi giao hàng tại 6 đị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 đ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 sao cho quãng đường mà người giao hàng phải di chuyển là ngắn nhất.

Gợi ý:

• Vì mỗi đoạn nối 2 điểm trên đồ thị sẽ có một độ dài riêng nên ta có thể xét điểm xuất phát là điểm .
• Từ điểm đi đến điểm nào là ngắn nhất? Cứ liên tiếp tương tự như vậy ta sẽ tìm được đường đi thỏa mãn yêu cầu đề bài.

Giải

Đường đi ngắn nhất và thỏa mãn yêu cầu đề bài: với tổng quãng đường đi là .

Nhận xét:

Những bài toán như HĐ2 được gọi là bài toán về tìm đường có trọng số.

Người ta sử dụng thuật toán Láng giềng gần nhất và thuật toán các nhà tóa học Dijkstra, Whiting và Hillier.

Các bước thực hiện xây dựng thuật toán:

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

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 củ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 .

Chú ý:

Để tìm đườ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ừ 1 đỉnh ban đầu.

Sau đó so sánh độ dài của các chu trình để tìm ra chu trình “tốt nhất” thỏa mãn yêu cầu đề bài.

Ví dụ 2:

Có năm địa điểm với độ dài quãng đường giữa các địa điểm (đơn vị: kilômét) mô tả ở Hình 25.

1. 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 địa điểm, đi qua tất cả các địa điểm khác và trở về địa điểm ban đầu sao cho tổng độ dài các cạnh của chu trình trình là ngắn nhất.
2. Từ đó hãy tìm đường đi ngắn nhất trên đồ thị có trọng số ở Hình 25, tức là tìm một chu trình đi qua tất cả các đỉnh sao cho tổng độ dài các cạnh của chu trình đó là ngắn nhất.

Giải

a) Từ , đỉnh gần nhất là , ;

Từ , đỉnh chưa đến gần nhất là , ;

Từ , đỉnh chưa đến gần nhất là , ;

Từ , đỉnh chưa đến gần nhất là , ;

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

Tổng quãng đường theo chu trình là: 

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)
		51
		50
		45
		45
		50
		45

b) Ba đường đi ngắn nhất có cùng chiều dài 45 km, đó là các chu trình .

   Luyện tập 2 (SGK - tr.46)

Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong HĐ2.

--------------- Còn tiếp ---------------