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.

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.
[IMAGE:img_q18_graph]

Câu 4. (5 điểm) Trong một giải cờ vua, có 20 vận động viên tham gia. Mỗi vòng, các vận động viên được chia thành 10 cặp thi đấu với nhau. Hai vận động viên bất kỳ thi đấu với nhau không quá một lần. Tìm số nguyên dương $k$ lớn nhất thỏa mãn: Sau 4 vòng đấu, bất kể cách chia cặp đấu ra sao, có thể chắc chắn chọn ra $k$ vận động viên đôi một chưa từng thi đấu với nhau?

Có năm địa điểm A, B, C, D, E được nối với nhau theo những con đường với độ dài (đơn vị là kilômét) được mô tả bằng đồ thị có trọng số ở hình vẽ dưới đây. Một người giao hàng đi giao hàng bắt đầu xuất phát từ địa điểm A đến các địa điểm còn lại và phải đi qua tất cả các con đường sau đó quay trở về địa điểm A. Hỏi người đó phải đi quãng đường ngắn nhất là bao nhiêu kilômét?

Có năm địa điểm A, B, C, D, E được nối với nhau theo những con đường với độ dài (đơn vị là kilômét) được mô tả bằng đồ thị có trọng số ở hình vẽ dưới đây. Một người giao hàng đi giao hàng bắt đầu xuất phát từ địa điểm A đến các địa điểm còn lại và phải đi qua tất cả các con đường sau đó quay trở về địa điểm A. Hỏi người đó phải đi quãng đường ngắn nhất là bao nhiêu kilômét?

Có một vùng biển gồm 300 hòn đảo. Người ta xây dựng $m$ cây cầu; mỗi cây cầu nối trực tiếp hai hòn đảo với nhau, và giữa hai hòn đảo có không quá một cây cầu.
(1) Tìm số lượng cây cầu $m$ lớn nhất có thể xây dựng, biết rằng tồn tại ít nhất một tuyến du lịch khép kín đi qua tất cả các cây cầu, mỗi cây cầu đúng một lần; một hòn đảo có thể được đi qua nhiều lần.
(2) Các hòn đảo được phân cho 5 vương quốc khác nhau quản lí, mỗi hòn đảo do đúng một vương quốc quản lí. Hệ thống cầu có tính chất: mọi tuyến du lịch khép kín đều phải đi qua các hòn đảo thuộc đủ cả 5 vương quốc. Hỏi tổng số cây cầu có thể vượt quá 398 hay không?

Cho bảy điểm $A,B,C,D,E,F,G$ có $ABCD$ là hình chữ nhật, $F$ là trung điểm $AD$, độ dài các cạnh được ghi trên hình vẽ (đơn vị độ dài). Một trò chơi được quy định như sau: xuất phát từ một điểm bất kỳ trong bảy điểm trên đi qua hết tất cả các cạnh trên hình vẽ mỗi cạnh ít nhất một lần rồi quay lại điểm xuất phát. Người chơi là người thắng cuộc nếu tổng độ dài đường đi là ngắn nhất. Tính tổng độ dài đường đi đó.