Giải chi tiết chuyên đề Toán 11 cánh diều mới chuyên đề 2 Một vài ứng dụng của lí thuyết đồ thị

Lí thuyết đồ thị có thể giải quyết những vấ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ệ.

I. VẬN DỤNG ĐỒ THỊ ĐỂ GIẢI QUYẾT NHỮNG VẤN ĐỀ VỀ TÌM ĐƯỜNG ĐI NGẮN NHẤT TRONG NHỮNG TRƯỜNG HỢP ĐƠN GIẢN

1. Đồ thị có trọng số

Luyện tập, vận dụng 1: Hãy cho ví dụ về đồ thị có trọng số. 

Hướng dẫn trả lời:

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

Luyện tập, vận dụng 2: Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2. 

Hướng dẫn trả lời:

Vậy người giao hàng chọn 1 đường đi trong 7 đường đi trên thì quãng đường phải di chuyển là ngắn nhất.

II. VẬN DỤNG ĐỒ THỊ ĐỂ GIẢI QUYẾT NHỮNG VẤN ĐỀ LIÊN QUAN ĐẾN KHOA HỌC TỰ NHIÊN VÀ CÔNG NGHỆ

1. Liên hệ với khoa học tự nhiên 

Luyện tập, vận dụng 3: Hexane $C_{6}H_{14}$ có năm đồng phân. Vẽ đồ thị tương ứng với năm đồng phân đó. 

Hướng dẫn trả lời:

Hexane $C_{6}H_{14}$ có năm đồng phân là: 

1. $CH_{3}-CH_{2}-CH_{2}-CH_{2}-CH_{2}-CH_{3}$

2. $CH_{3}-CH-CH_{2}-CH_{2}-CH_{3}$

                     |

                 $CH_{3}$

3. $CH_{3}-CH_{2}-CH-CH_{2}-CH_{3}$

                                   |

                               $CH_{3}$

4.                     $CH_{3}$

                             |

$CH_{3}-CH_{2}-C-CH_{3}$

                             |

                        $CH_{3}$

5. $CH_{3}-CH-CH-CH_{3}$

                      |           |

                $CH_{3}$    $CH_{3}$

BÀI TẬP

Bài 1: 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 đó. 

Hướng dẫn trả lời:

Bài 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. 

Hướng dẫn trả lời:

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.

Bài 3: 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). Ta nên chọn theo chu trình nào đi qua tất cả các địa điểm để tổng chi phí di chuyển là thấp nhất? Chi phí thấp nhất đó bằng bao nhiêu?

Hướng dẫn trả lời:

Có ba chu trình ABCDA, BADCB, DCBAD thỏa mãn đề bài. Chi phí thấp nhất là 97 (nghìn đồng).

Bài 4: 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).

Hướng dẫn trả lời:

Ta thấy chu trình xuất phát từ đỉnh A: AEDBCA thỏa mãn đề bài với tổng quãng đường nhỏ nhất là 21 (kilômét).

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ài 5: 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.  

Hướng dẫn trả lờ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: 19 + 38 + 32 + 51 = 140 (phút).