Bài Tập Trắc Nghiệm Chuyên Đề: Chuyên đề: lí thuyết đồ thị (Toán học Lớp 11)

Một nhân viên của thư viện tỉnh muốn lập kế hoạch giới thiệu nội dung chương trình “Kết nối bạn đọc yêu sách 2025” đến bốn trường học trong khu vực lân cận. Độ dài quãng đường giữa các địa điểm (đơn vị: kilômét) được mô tả trong hình vẽ sau:

Người nhân viên đó muốn xuất phát từ thư viện tỉnh và phải đi thăm cả bốn trường, mỗi trường chỉ đến đúng một lần, rồi quay trở về thư viện tỉnh. Tổng độ dài quãng đường đi (đơn vị: kilômét) thỏa mãn điều kiện trên nhận giá trị nhỏ nhất là bao nhiêu?

Trong kì nghỉ hè bạn Phong muốn đi du lịch qua các địa điểm du lịch $A,B,C,D,E$ như hình vẽ. Khoảng cách giữa các địa điểm du lịch như sau $AB=16,BC=17,CD=11,DE=15,EA=14,AC=6,CE=20,EB=5,BD=3,DA=9$ (đơn vị là km). Biết rằng số tiền bạn Phong phải trả cho $1\text{ km}$ là $15000$ đồng. Giả sử rằng bạn Phong xuất phát từ điểm $A$ đi qua các điểm $B,C,D,E$ đúng một lần sau đó trở về điểm $A$. Số tiền bạn Phong phải trả thấp nhất là bao nhiêu (kết quả làm tròn đến hàng nghìn)?

Một công ty vận tải đang lên kế hoạch giao hàng từ kho hàng A đến điểm nhận J. Trên hành trình, xe có thể đi qua một số điểm trung chuyển như B, C, D, E, F, G, H, I. Các tuyến đường cùng khoảng cách giữa các địa điểm được minh họa như trong hình vẽ bên. Các con số trên đoạn đường biểu thị độ dài (tính bằng kilômét). Tuyến đường ngắn nhất từ A đến J có chiều dài bao nhiêu kilômét?

Mạng lưới giao thông ở một thành phố được mô phỏng như hình vẽ bên dưới, trong đó $A,B,C,D,E$ là các điểm nút giao thông, số ghi trên mỗi cạnh trong hình vẽ là khoảng cách giữa hai điểm đầu và cuối của con đường đó (đơn vị là $\text{km}$). Một khách du lịch muốn đi tham quan thành phố bằng cách xuất phát từ một vị trí bất kì trong các điểm nút $A,B,C,D,E$. Hỏi quãng đường ngắn nhất để hành khách đi hết các con đường và trở về vị trí xuất phát là bao nhiêu $\text{km}$?

Cho một đồ thị gồm có 6 đỉnh được nối với nhau bằng 12 cạnh (như hình vẽ dưới). Giả sử có một con kiến bắt đầu đi từ đỉnh $A$ và đi trên các cạnh, nhưng không được đi cạnh nào quá 1 lần. Biết con kiến đó đi qua mỗi đỉnh đúng 1 lần trước khi quay trở về đỉnh $A$. Hỏi có bao nhiêu đường đi thỏa mãn?

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 vẽ. Xe giao hàng của công ty xuất phát từ một 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.

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ạn Nam muốn đi từ quốc gia A tới quốc gia G. Hai quốc gia này đều có sân bay nhưng không có đường bay thẳng, nên muốn đi được thì Nam phải bay trung chuyển qua các quốc gia khác. Nam khảo sát giá vé và các đường bay phù hợp với thời gian và tài chính của mình thì thấy có thể chọn trung chuyển ở sân bay các quốc gia A, B, C, D, E, F, G, giá tiền bay mỗi chiều giữa 2 nước là như nhau, được cho trong các bảng sau:

Tính số tiền vé ít nhất có thể để Nam đi được từ quốc gia A tới quốc gia G.

Trong một lần sáp nhập tỉnh, tỉnh A được thành lập gồm có 6 phường và 55 xã. Ta kí hiệu 6 phường này là 1, 2, 3, 4, 5, 6. Giữa các phường có các con đường mới xây dựng và có thể di chuyển bằng ô tô, được biểu diễn bằng các đoạn thẳng hoặc đoạn cong như hình vẽ. Anh Hoàng ở Phường 2, anh định dùng ô tô để đi tham quan tất cả các con đường nói trên sao cho mỗi con đường chỉ đi đúng một lần rồi trở về Phường 2. Nhưng tiếc rằng hiện tại chắc chắn không có cách nào để đi được như thế.

Gọi $ik$ là con đường đi trực tiếp từ Phường $i$ đến Phường $k$ và không giao nhau với các con đường khác, với $i,k\in \{1;2;3;4;5;6\mid i\ne k\}$. Nếu bạn được phép xây dựng thêm duy nhất một con đường $ik$ thì hãy cho biết giá trị $i+k$ bằng bao nhiêu để anh Hoàng có thể thực hiện được ý định nêu trên?

Trong một trò chơi điện tử, game thủ phải điều khiển một nhân vật trong game có 100 HP (HP là viết tắt của từ Health point hay gọi đơn giản là chỉ số máu của nhân vật) thực hiện một hành trình xuất phát từ điểm $A$ đi đến điểm $I$. Các tuyến đường nối từ điểm $A$ đến điểm $I$ được biểu diễn trong sơ đồ sau, với các con số ghi trên mỗi tuyến là số HP mà nhân vật bị mất đi.

Số điểm đạt được của game thủ sau khi kết thúc trò chơi bằng số HP còn lại của nhân vật trong game. Hỏi số điểm cao nhất mà game thủ có thể đạt được là bao nhiêu điểm?

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.