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

(AI giải đề cho tôi)
Từ hình vẽ, các cạnh và thời gian (phút): $AB=17$, $AE=8$, $AD=20$, $BE=29$, $BC=12$, $CE=19$, $CD=10$, $ED=9$. Cần tìm chu trình Hamilton xuất phát từ $A$ đi qua $B$, $C$, $D$, $E$ mỗi xã đúng một lần rồi quay về $A$ với tổng thời gian nhỏ nhất. Liệt kê các chu trình (không phân biệt hai chiều): $A\to B\to C\to D\to E\to A$: $17+12+10+9+8=56$ phút. $A\to B\to C\to E\to D\to A$: $17+12+19+9+20=77$ phút. $A\to B\to E\to D\to C\to A$: $17+29+9+10+12=77$ phút. $A\to B\to E\to C\to D\to A$: $17+29+19+10+20=95$ phút. $A\to C\to B\to E\to D\to A$: $12+12+29+9+20=82$ phút. $A\to C\to D\to E\to B\to A$: $12+10+9+29+17=77$ phút. $A\to C\to E\to D\to B\to A$: $12+19+9+29+17=86$ phút. $A\to D\to E\to B\to C\to A$: $20+9+29+12+12=82$ phút. $A\to D\to C\to B\to E\to A$: $20+10+12+29+8=79$ phút. $A\to D\to C\to E\to B\to A$: $20+10+19+29+8=86$ phút. $A\to D\to E\to C\to B\to A$: $20+9+19+12+17=77$ phút. $A\to E\to B\to C\to D\to A$: $8+29+12+10+20=79$ phút. Vậy chu trình ngắn nhất là $A\to B\to C\to D\to E\to A$ (và chiều ngược lại) với tổng thời gian $56$ phút $=56/60$ giờ. Chi phí thuê xe nhỏ nhất: $750000\times 56/60=700000$ đồng $=700$ nghìn đồng. Kết quả khớp với đáp án nguồn (700).

(AI giải đề cho tôi)
Từ hình vẽ, các cạnh và thời gian (phút): $AB=17$, $AE=8$, $AD=20$, $BE=29$, $BC=12$, $CE=19$, $CD=10$, $ED=9$. Lưu ý không có cạnh nối trực tiếp $A$ với $C$. Cần tìm chu trình Hamilton xuất phát từ $A$, qua $B,C,D,E$ mỗi xã đúng một lần rồi về $A$ với tổng thời gian nhỏ nhất. Xét các chu trình khả dĩ (không dùng cạnh $AC$ vì không tồn tại):
- $A\to B\to C\to D\to E\to A$: $17+12+10+9+8=56$;
- $A\to B\to C\to E\to D\to A$: $17+12+19+9+20=77$;
- $A\to B\to D\to C\to E\to A$: $17+10+10+19+8=64$;
- $A\to B\to D\to E\to C\to A$: $17+10+9+19+12=67$;
- $A\to B\to E\to C\to D\to A$: $17+29+19+10+20=95$;
- $A\to B\to E\to D\to C\to A$: $17+29+9+10+12=77$;
- $A\to D\to B\to C\to E\to A$: $20+10+12+19+8=69$;
- $A\to D\to B\to E\to C\to A$: $20+10+29+19+12=90$;
- $A\to D\to C\to B\to E\to A$: $20+10+12+29+8=79$;
- $A\to D\to E\to B\to C\to A$: $20+9+29+12+12=82$;
- $A\to D\to E\to C\to B\to A$: $20+9+19+12+17=77$;
- $A\to E\to B\to C\to D\to A$: $8+29+12+10+20=79$.

Chu trình ngắn nhất là $A\to B\to C\to D\to E\to A$ với tổng thời gian $56$ phút $=\frac{56}{60}$ giờ. Chi phí thuê xe thấp nhất: $750000\times \frac{56}{60}=700000$ đồng $=700$ nghìn đồng. Kết quả khớp với đáp án nguồn ($700$).

(AI giải đề cho tôi)
Đây là bài toán người đưa thư Trung Hoa (Chinese Postman) trên đồ thị vô hướng. Các cạnh của hình vẽ: $AB=8$, $BC=12$, $CD=8$, $AD=12$ (vì $ABCD$ là hình chữ nhật), $AF=FD=6$ ($F$ là trung điểm $AD$), $AE=8$, $ED=10$, $BF=8$, $BG=8$, $CF=8$, $CG=8$. Tổng độ dài tất cả các cạnh: $8+12+8+12+6+6+8+10+8+8+8+8=102$. Xét bậc của từng đỉnh: $A$ nối với $B,D,F,E$ → bậc 4; $B$ nối với $A,C,F,G$ → bậc 4; $C$ nối với $B,D,F,G$ → bậc 4; $D$ nối với $A,C,F,E$ → bậc 4; $E$ nối với $A,D$ → bậc 2; $F$ nối với $A,D,B,C$ → bậc 4; $G$ nối với $B,C$ → bậc 2. Mọi đỉnh đều có bậc chẵn nên đồ thị có chu trình Euler: tồn tại đường đi khép kín đi qua mỗi cạnh đúng một lần. Vậy tổng độ dài đường đi ngắn nhất bằng tổng độ dài các cạnh, tức $102$.

(AI giải đề cho tôi)
Tổng độ dài các cạnh: $AB=200,BC=700,CD=400,BD=900,BE=800,AE=700,ED=1000,EF=900,FA=1000$, tổng $=6600$ m. Bậc các đỉnh: $A:3$, $B:4$, $C:2$, $D:3$, $E:4$, $F:2$. Chỉ có hai đỉnh bậc lẻ là $A$ và $D$, nên theo bài toán người đưa thư (Chinese Postman) phải lặp lại đường đi ngắn nhất từ $A$ đến $D$. Các phương án: $A\to B\to D=200+900=1100$; $A\to B\to C\to D=1300$; $A\to E\to D=700+1000=1700$; $A\to B\to E\to D=1900$; $A\to E\to B\to D=2400$. Ngắn nhất là $1100$ m. Đáp số: $6600+1100=7700$ m.

Ta coi như đây là hình chóp E.ABCD, khi xuất phát từ A và kết thúc tại A thì tương đương với việc bắt đầu từ một điểm thuộc đáy và trong quá trình di chuyển phải đi qua đỉnh hình chóp. Nên ta sẽ luôn bỏ qua một cạnh đáy và hai cạnh bên đối diện với cạnh đáy đó. Ví dụ: chu trình ABCDEA thì ta bỏ qua AD và BE với BC. Suy ra để thời gian di chuyển ngắn nhất thì lấy tổng thời gian đi trừ đi thời gian đi ba cạnh trên. Mà có 4 cạnh đáy nên xét 4 trường hợp (AD; BE; CE), (AB; DE; CE) …. Tổng thời gian di chuyển trên tất cả các cạnh của sơ đồ là $16+7+18+23+13+15+12+8=112$ phút. Trong các trường hợp trên thì trường hợp bỏ (AD; BE; CE) có tổng thời gian ba cạnh bị bỏ lớn nhất: $18+23+15=56$ phút, nên thời gian di chuyển ít nhất là $112-56=56$ phút. Cộng thêm thời gian giao hàng tại 4 địa điểm $B,C,D,E$: $4\times 5=20$ phút. Vậy thời gian ít nhất để anh Hà hoàn thành công việc là $56+20=76$ phút.

Lưu ý: lời giải gốc trong tài liệu kết luận 56 phút nhưng đã quên cộng thời gian giao hàng (20 phút), nên đáp án đúng theo tính toán đầy đủ là 76 phút (B).

(AI giải đề cho tôi)
Từ sơ đồ, các cạnh có: AB=16, AE=7, AD=18, BE=23, BC=13, CE=15, CD=12, DE=8. Thời gian giao hàng tại 4 điểm là 4·5=20 phút. Xét các chu trình Hamilton xuất phát và kết thúc tại A (chu trình thuận và nghịch cùng giá trị):
- A→B→C→D→E→A: 16+13+12+8+7 = 56 phút di chuyển.
- A→B→C→E→D→A: 16+13+15+8+18 = 70.
- A→B→E→C→D→A: 16+23+15+12+18 = 84.
- A→B→E→D→C→A: 16+23+8+12+12? kiểm tra lại: BE=23, ED=8, DC=12, CA không có cạnh trực tiếp nên chu trình này không hợp lệ (A chỉ nối B, E, D).
- A→C→D→E→B→A: 13+12+8+23+16 = 72.
- A→D→C→B→E→A: 18+12+13+23+7 = 73.
- A→D→E→C→B→A: 18+8+15+13+16 = 70.
- A→E→D→C→B→A: 7+8+12+13+16 = 56.
Thời gian di chuyển nhỏ nhất là 56 phút, cộng thêm 20 phút giao hàng: 56+20 = 76 phút. Đáp án B.

(AI giải đề cho tôi)
Đây là bài toán tìm chu trình Hamilton ngắn nhất trên đồ thị với các cạnh: $AB=16$, $AC=12$, $AD=20$, $BC=10$, $BD=13$, $CD=9$. Xét các chu trình xuất phát từ $A$ (do tính đối xứng, chỉ cần 3 chu trình):
- $A\to B\to C\to D\to A$: $16+10+9+20=55$.
- $A\to B\to D\to C\to A$: $16+13+9+12=50$.
- $A\to C\to B\to D\to A$: $12+10+13+20=55$.
Vậy quãng đường ngắn nhất là $50$ mét (chu trình $A\to B\to D\to C\to A$ hoặc chiều ngược lại).

(AI giải đề cho tôi)
Đây là bài toán người đưa thư Trung Hoa (Chinese Postman). Từ hình vẽ trang 6, đồ thị có các cạnh: $AB=1$, $BC=2$, $CD=3$, $BD=4$, $ED=5$, $AE=6$ (cạnh thẳng đứng), $BE=7$ (đường chéo), và cạnh cong ngoài $AE=8$. Tổng trọng số các cạnh: $1+2+3+4+5+6+7+8=36$ km. Xét bậc các đỉnh: $A$ bậc 3 (các cạnh $AB$, $AE=6$, cạnh cong $AE=8$) — lẻ; $B$ bậc 4 — chẵn; $C$ bậc 2 — chẵn; $D$ bậc 3 (các cạnh $BD$, $CD$, $ED$) — lẻ; $E$ bậc 4 — chẵn. Vậy chỉ có hai đỉnh bậc lẻ là $A$ và $D$, nên cần lặp lại con đường ngắn nhất nối $A$ với $D$. Đường đi ngắn nhất từ $A$ đến $D$: $A\to B\to D$ có độ dài $1+4=5$ (so sánh: $A\to E\to D=6+5=11$; $A\to B\to E\to D=1+7+5=13$). Quãng đường ngắn nhất $=36+5=41$ km. Hành trình cụ thể đạt 41 km: đi cạnh $A\to B\to D$ (lặp lại một lần) và mỗi cạnh còn lại đúng một lần, ví dụ $A\to B\to C\to D\to B\to E\to D\to E\to A(6)\to A(8)\to B\to A$... tổng bằng $36+5=41$. Kết quả khớp với đáp án nguồn: 41.

(AI giải đề cho tôi)
Bài toán tìm chu trình Euler có trọng số nhỏ nhất (bài toán người đưa thư Trung Hoa). Các cạnh: $AB=1$, $AE=8$ (cung), $AE=6$, $EB=7$, $ED=5$, $BD=4$, $BC=2$, $CD=3$. Tổng trọng số tất cả các cạnh: $1+8+6+7+5+4+2+3=36$. Bậc các đỉnh: $A$ có bậc $3$ ($AB$, $AE=8$, $AE=6$) lẻ; $B$ có bậc $4$ chẵn; $C$ có bậc $2$ chẵn; $D$ có bậc $3$ ($ED$, $BD$, $CD$) lẻ; $E$ có bậc $4$ chẵn. Hai đỉnh bậc lẻ là $A$ và $D$, nên cần lặp lại con đường ngắn nhất từ $A$ đến $D$. Đường đi ngắn nhất $A$ đến $D$: $A$–$B$–$D=1+4=5$ (so với $A$–$E$–$D=8+5=13$ hay $6+5=11$). Tổng quãng đường ngắn nhất $=36+5=41$ km.

Xét các lộ trình hợp lệ xuất phát từ $M$ đi qua cả $4$ địa điểm $A,B,C,D$ (không đi theo chiều từ $B$ đến $A$), lộ trình ngắn nhất là $M\to C\to B\to D\to A$ với tổng quãng đường bằng $4+3+4+5=16\text{ km}$.

Xét các chu trình xuất phát từ $A$ đi qua $B,C,D$ rồi về $A$:
- $A\to C\to B\to D\to A$: $15+34+20+30=99$ (phút).
- $A\to B\to D\to C\to A$: $42+20+35+15=112$ (phút).
- $A\to B\to C\to D\to A$: $42+34+35+30=141$ (phút).
Vậy thời gian đi ít nhất là $99$ phút.

Xét các chu trình đi qua tất cả $5$ thành phố rồi quay về điểm xuất phát:
- $A\to B\to E\to C\to D\to A$ (hoặc ngược lại): $9+8+12+13+11=53$.
- $A\to E\to B\to C\to D\to A$: $10+8+14+13+11=56$.
- $A\to B\to C\to E\to D\to A$: $9+14+12+14+11=60$.
Vậy chi phí thấp nhất là $53$.

Chu trình đi qua tất cả $5$ trụ và quay về trụ ban đầu có tổng số thử thách nhỏ nhất là $A-B-D-C-E-A$ (hoặc ngược lại) với tổng số thử thách là $9+10+8+4+14=45$.

Chu trình ngắn nhất đi qua tất cả các đỉnh và quay về Thư viện tỉnh là: Thư viện tỉnh $\to$ Trường A ($3$) $\to$ Trường C ($7$) $\to$ Trường D ($2$) $\to$ Trường B ($3$) $\to$ Thư viện tỉnh ($2$) (hoặc chiều ngược lại), có tổng độ dài $3+7+2+3+2=17\text{ km}$. Đáp án chính thức của đề (Mã đề 0101, trang 5): 17.

Theo bảng đáp án chính thức (Mã đề 0110, trang 5), Câu 1 (Phần III) có kết quả là: 560.

Để tham quan tất cả các khu vực và quay về Trung tâm với chi phí nhỏ nhất, hành trình tối ưu có tổng chi phí là $560000$ đồng, tương ứng với $560$ nghìn đồng.

Xét các chu trình Hamilton đi qua 4 đỉnh trên đồ thị trọng số: chu trình có tổng thời gian nhỏ nhất đi theo các cạnh có trọng số $15,34,20,30$ với tổng thời gian là $15+34+20+30=99$ (phút). Đáp án: 99.

Xét các chu trình Hamilton đi qua $5$ đỉnh $A,B,C,D,E$: chu trình $A-B-E-C-D-A$ có tổng chi phí là $9+8+12+13+11=53$ (triệu đồng), là chi phí thấp nhất.

Theo bảng đáp án chính thức (Mã đề thi 2009, trang 5), Câu 2 (Phần III) có đáp số là $145$.

Tổng trọng số của tất cả $14$ cạnh trên đồ thị là $4+5+17+3+8+8+7+9+6+6+10+18+12+10=123$ (phút).
Các đỉnh có bậc lẻ là $A$ (bậc $3$), $D$ (bậc $3$), $E$ (bậc $5$), $G$ (bậc $7$).
Ghép cặp đường đi ngắn nhất giữa $4$ đỉnh bậc lẻ $(A,G)$ và $(D,E)$: $d(A,G)=4+3+7=14$? Kiểm tra: $A\to F\to G$ là $5+7=12$, nhưng $A\to B\to F\to G$ là $4+3+7=14$, còn ghép $(A,E)$ và $(G,D)$ hoặc $(A,G)=12$ và $(D,E)=10$ cho tổng các cạnh lặp lại nhỏ nhất là $12+10=22$ (phút).
Vậy tổng thời gian ngắn nhất là $123+22=145$ (phút).

Xét các chu trình xuất phát từ Hà Nội (HN), đi qua Đà Nẵng (ĐN), TP.HCM (HCM), Cần Thơ (CT) đúng một lần rồi quay về HN:
- $\text{HN}\to \text{ĐN}\to \text{HCM}\to \text{CT}\to \text{HN}$: $40+50+30+110=230$ (lít).
- $\text{HN}\to \text{ĐN}\to \text{CT}\to \text{HCM}\to \text{HN}$: $40+70+30+90=230$ (lít).
- $\text{HN}\to \text{HCM}\to \text{ĐN}\to \text{CT}\to \text{HN}$: $90+50+70+110=320$ (lít).
Chi phí nhiên liệu ít nhất cho hành trình là $230$ lít xăng.
Số lít xăng cần đổ thêm ít nhất là $230-150=80$ (lít).

Theo lời giải chi tiết và đáp án chính thức của Sở GD&ĐT Bình Phước, số HP tối đa giữ lại được là $19$.