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 2026” đế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ẽ bên. 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?
[IMAGE:img_q20_schools]

Câu 1: Một khu vui chơi có sơ đồ như hình vẽ. Khách hàng xuất phát từ khu Trung tâm, đi qua các cánh cửa để tham quan các khu vực khác. Giá vé cho mỗi lần bước qua một cánh cửa (theo bất kỳ chiều nào) được ghi trên sơ đồ (đơn vị tiền là đồng). Sau khi đã đi qua tất cả các khu vực, khách hàng phải trở lại khu Trung tâm để ra ngoài. Hỏi khách hàng phải tốn ít nhất bao nhiêu nghìn đồng tiền mua vé?

Một người đưa thư xuất phát từ bưu điện (vị trí A) và phải đi qua các địa điểm B, C, D để phát thư rồi quay trở lại bưu điện. Sơ đồ các địa điểm và thời gian di chuyển giữa các địa điểm được mô tả như hình bên dưới (đơn vị phút). Tính thời gian ít nhất mà người đưa thư cần để hoàn thành công việc.

Câu 4. 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 (đơn vị tính: triệu đồng). 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.

Câu 2. 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?

Nam và ba người bạn lên kế hoạch cho một chuyến đi phượt xuyên Việt, ghé thăm $4$ thành phố: Hà Nội, Đà Nẵng, Thành phố Hồ Chí Minh (TP.HCM) và Cần Thơ. Họ xuất phát từ Hà Nội, đi qua tất cả các thành phố còn lại đúng một lần rồi quay về Hà Nội. Bảng chi phí nhiên liệu (tính bằng lít xăng) giữa các thành phố như sau:



Xe của nhóm hiện đã có sẵn $150$ lít xăng. Để hoàn thành hành trình, họ cần đổ thêm ít nhất bao nhiêu lít xăng?

Bạn Hóa muốn leo núi với địa điểm xuất phát từ $A$ và kết thúc tại $B$ với bản đồ đường đi được minh họa bởi hình vẽ dưới, trong đó các đường đi là các đoạn thẳng và thời gian di chuyển (tính bằng phút) tương ứng được gắn bởi một số trên đoạn thẳng đó. Hãy xác định thời gian ngắn nhất (tính bằng phút) để bạn Hóa hoàn thành chuyến đi từ $A$ đến $B$.

Trong một trò chơi điện tử, người chơi sẽ khởi đầu tại một trong năm vị trí xuất phát tại các điểm $A,B,C,D,O$. Ban đầu, người chơi sẽ có $50$ HP (HP là từ viết tắt của: “Health Points”) và người chơi sẽ đi từ điểm xuất phát đến các điểm còn lại để tiêu diệt địch (các đường đi qua sẽ không thể quay trở lại). Ứng với mỗi đường đi qua, người chơi sẽ mất một lượng HP nhất định được ký hiệu trên sơ đồ dưới đây. Sau cùng, người chơi phải quay lại vị trí xuất phát và tiêu diệt địch cuối cùng ngay tại đó. Biết đường đi cuối cùng này sẽ mất gấp đôi lượng HP yêu cầu. Hỏi sau khi hoàn thành nhiệm vụ thì người chơi có thể giữ lại tối đa bao nhiêu HP?

Trên mỗi cạnh của hình bên dưới, có ghi số phút để đi từ điểm này đến điểm kế tiếp:

Tìm tổng thời gian ngắn nhất để di chuyển từ điểm A đến điểm D trên hình.

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.

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 đó.

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?