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

Giả sử có sáu bến xe buýt $A$, $B$, $C$, $D$, $E$ và $F$ được nối với nhau theo những con đường với thời gian di chuyển (đơn vị: giờ) được mô tả trong hình bên. Một người cần ít nhất bao nhiêu thời gian để di chuyển từ bến $A$ đến bến $C$ bằng xe buýt của các tuyến trên? Biết rằng thời gian tại bến để chuyển tiếp từ tuyến này qua tuyến kia là không đáng kể.

[Hình cần kiểm tra lại: p3_f1]

Một anh phục vụ bàn đang phục vụ trong một khu vực có 4 bàn đặt tại $A,B,C,D$ với khoảng cách (được tính theo đơn vị mét) được ghi như các trọng số của các cạnh trong hình bên. Anh nhân viên này xuất phát từ một bàn $A$ và phải đi qua tất cả các bàn và phải quay về vị trí ban đầu, mỗi bàn chỉ được đi qua một lần (trừ lần trở về bàn ban đầu). Hỏi quãng đường ngắn nhất để anh nhân viên thực hiện được công việc là bao nhiêu mét?

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 năm 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:
[IMAGE:img_q19_graph]

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?

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

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.

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 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?