Hằng năm, trường THPT M tổ chức các đoàn đi thăm hỏi và chúc Tết tứ thân phụ mẫu cao tuổi của cán bộ, giáo viên và nhân viên trong trường. Đoàn số 1 có nhiệm vụ đến thăm 4 gia đình tại các địa điểm A, B, C, D. Đoàn xuất phát từ trường THPT M, đến thăm đủ 4 gia đình (mỗi gia đình đúng một lần). Sau khi thăm xong gia đình cuối cùng, đoàn kết thúc hành trình tại đó (không quay về trường). Do điều kiện giao thông dịp cuối năm, đoạn đường AB chỉ có thể đi theo chiều từ A đến B, không đi được theo chiều ngược lại (hình vẽ). Đoàn số 1 đã chọn được lộ trình di chuyển có tổng quãng đường di chuyển ngắn nhất. Tổng quãng đường ngắn nhất đó dài bao nhiêu km?

Bài 1 :

Một trò chởi điện tử quy định như sau: Có 4 trụ A, B, C, D với số lượng các thử thách trên đường đi giữa các cặp trụ được mô tả trong hình bên. Người chơi xuất phát từ một trụ nào đó, đi qua tất cả các trụ còn lại, mỗi khi đi qua một trụ thì trụ đó sẽ bị phá hủy và không thể quay trở lại trụ đó được nữa, nhưng người chơi vẫn phải trở về trụ ban đầu. Tổng số thử thách của đường đi thoả mãn điều kiện trên nhận giá trị nhỏ nhất là bao nhiêu?

Bài 2 :

Một công ty vận tải cần giao hàng đến tất cả các thành phố A, B, C, D, E (hình vẽ bên dưới). Chi phí di chuyển giữa các thành phố được mô tả trên hình. Xe giao hàng của công ty xuất phát từ một thành phố trong năm thành phố trên đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố ban đầu. Tìm chi phí thấp nhất của xe giao hàng.

Bài 3 :

Công ty giao hàng nhanh có 4 kho hàng A, B, C và D . Quản lý muốn lên kế hoạch cho xe giao hàng đi qua tất cả các kho hàng để lấy hàng và quay lại kho hàng ban đầu, với điều kiện là mỗi kho hàng chỉ ghé qua một lần. Khoảng cách giữa các kho hàng (km) được mô tả trong hình bên. Quãng đường ngắn nhất để xe
giao hàng hoàn thành việc lấy hàng ở các kho và quay trở lại kho hàng ban đầu là bao nhiêu?

Bài 4 :

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 vẽ.Tìm thời gian đi ít nhất để thực hiện chu trình trên.

Bài 5 :

Từ kho D xe bưu chính đến lấy thư từ các hộp thư tại E, F, G và H rồi quay lại kho. Sơ đồ bên dưới hiển thị thời gian xe bưu chính di chuyển giữa các hộp thư (đơn vị: phút). Thời gian ngắn nhất để xe bưu chính thực hiện điều đó là bao nhiêu phút?

Bài 6 :

Công ty A có kế hoạch tổ chức tour du lịch tâm linh tại tỉnh Bắc Giang đi qua 5 địa điểm: Đền Xương Giang, Chùa Bổ Đà, Chùa Vĩnh Nghiêm, Thiền viện Trúc lâm Phượng Hoàng, Đền Ngọc Lâm. Hành khách sẽ xuất phát từ Đền Xương Giang và đi thăm mỗi địa điểm đúng một lần. Qua khảo sát thực địa, công ty xây dựng được lược đồ như hình (khoảng cách giữa mỗi cặp địa điểm được ghi trên đường nói). Để tiết kiệm chi phí, công ty dự định chọn tuyến đường có tổng độ dài ngắn nhất. Độ dài của tuyến đường này là bao nhiêu km (làm tròn đến hàng phần mười)?

Bài 7 :

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. 

Bài 8 :

Một bác Shipper giao hàng xuất phát từ kho A để lấy hàng và đi giao tất cả các con đường sau đó lại trở về kho A để trả lại những hàng hóa mà khách hàng chưa nhận. Con đường có sơ đồ và thời gian giao hàng (phút) trên mỗi con đường được mô tả trong hình sau:

Thời gian ngắn nhất để bác Shipper hoàn thành công việc trên là bao nhiêu phút?

Bài 9 :

Có năm địa điểm A, B, C, D, E. Một số địa điểm có đường đi tới nhau mô tả bằng các cạnh với độ dài quãng đường tính theo kilomet cho bởi số gắn với cạnh đó như hình vẽ. Một người đưa thư xuất phát từ bưu điện C cần đi qua tất cả các đường (mỗi đường đi qua ít nhất một lần), và sau đó phải trở về vị trí ban đầu C. Tổng số kilomet mà người đưa thư cần phải đi nhỏ nhất bằng bao nhiêu?

Bài 10 :

Trong một trò chơi, người chơi muốn tìm đường đi ngắn nhất để đi từ A đến P, biết từ A đến P có những đường đi như hình vẽ và khoảng cách giữa các vị trí được cho trên hình. Đường đi thỏa mãn điều kiện trên nhận giá trị nhỏ nhất là bao nhiêu?

Bài 11 :

Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.

a) Hãy chỉ ra 2 đường đi từ A đến F và so sánh độ dài của hai đường đi đó.

b) Với mỗi đỉnh V của sơ đồ trên Hình 2.28, ta gắn số I(V) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, ta có ngay I(A) = 0. Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn I(B), I(C) của hai đỉnh kề với A là B, C. 

Bài 12 :

Tìm đường đi ngắn nhất từ A đến D trong đồ thị có trọng số trên Hình 2.33.

Bài 13 :

Tìm đường đi ngắn nhất từ đỉnh S đến  mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.

Bài 14 :

Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.

Bài 15 :

Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.36.

Bài 16 :

Viết tập hợp các đỉnh và tập hợp các cạnh của mỗi đồ thị sau:

Bài 17 :

Vẽ đồ thị G = (V, E) với các đỉnh và các cạnh như sau:

V = {1; 2; 3; 4; 5; 6; 7; 8} và E = {12; 13; 23; 34; 35; 67; 68; 78}.

Đồ thị này có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?

Bài 18 :

Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.41.

Bài 19 :

Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.42.

Bài 20 :

Như chúng ta đã biết, Lí thuyết đồ thị ra đời trong quá trình khái quát, mô phỏng những vấn đề của khoa học và thực tiễn thành những mô hình toán học. Vì thế, các kết quả của Lí thuyết đồ thị có nhiều ứng dụng trong khoa học và thực tiễn.

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

Bài 21 :

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.

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.

Bài 22 :

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.

Bài 23 :

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

Bài 24 :

Giả sử ba địa điểm A, B, C được nối với nhau theo những con đường AB, BC, CA với độ dài lần lượt là 15 km, 20 km, 16 km. Sử dụng đồ thị để mô tả tình huống đó.

Bài 25 :

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.

Bài 26 :

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?

Bài 27 :

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

Bài 28 :

Phần mềm chỉ đường thường chỉ ra đường đi ngắn nhất khi người dùng muốn tìm đường đi từ một địa điểm đến một địa điểm khác.

Làm thế nào để tìm ra đường đi đó?

Bài 29 :

Cho đồ thị có trọng số như Hình 5.

a) Chỉ ra trọng số của các cạnh AE, MN, CN.

b) Tính độ dài của các đường đi ABEN, EMFNE.

c) Chỉ ra ba đường đi khác nhau từ A đến D và tính độ dài của chúng.

d) Đường đi EMF có phải là đường đi ngắn nhất từ E đến F không?

Bài 30 :

Để biểu diễn các con đường nối các giao lộ cùng với độ dài của chúng như sơ đồ ở Hình 1, một học sinh đã vẽ đồ thị như Hình 2. Chỉ ra các cạnh và số biểu diễn độ dài con đường còn thiếu trong Hình 2.