Qua bài học này, ta thấy Lí thuyết đồ thị có thể giải quyết những vấn đề thực tiễn:

- Vấn đề về tìm đường đi ngắn nhất trong những trường hợp đơn giản.

- Vấn đề liên quan đến khoa học tự nhiên và công nghệ.

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.

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

Năm đồng phân của hexane C₆H₁₄ là:

CH₃ – CH₂ – CH₂ – CH₂ – CH₂ – CH₃

Các đồ thị ở hình dưới đây tương ứng minh họa biểu diễn năm đồng phân của hexane C₆H₁₄. Trong đó các nguyên tử C, CH, CH₂, CH₃ tạo nên các đỉnh của đồ thị, còn các liên kết CH₃ – CH₂, CH₂ – CH₂, CH₂ – CH₃, CH₃ – CH, CH – CH₃, CH – CH₂, CH₂ – C, C – CH₃, CH₂ – CH, CH – CH tạo nên các cạnh của đồ thị.

Giả sử các điểm A, B, C, D, E, G lần lượt biểu diễn cho các thành phố Seoul, Tokyo, Sydney, Hà Nội, Beijing, New York.

Ta có đồ thị 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ố như sau:

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:

Dễ thấy đồ thị Hình 33 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 = 20 nghìn đồng;

Từ B, đỉnh chưa đến gần nhất là C, BC = 30 nghìn đồng;

Từ C, đỉnh chưa đến gần nhất là D, CD = 12 nghìn đồng;

Đến đây không còn đỉnh chưa đến, vì vậy quay về A, DA = 35 nghìn đồng.  

Tổng chi phí di chuyển theo chu trình ABCDA là: 20 + 30 + 12 + 35 = 97 (nghìn đồng).

Tương tự bắt đầu với những đỉnh khác, ta có bảng sau:

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. 

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