Chuyên đề học tập Toán 11

Giải Hoạt động trang 46 Chuyên đề Toán 11

Bài 9. Đường đi Euler và đường đi Hamilton   Đã kiểm chéo

Đề bài

Cho sơ đồ như trên Hình 2.28, ở đó A,B,C,D,E,FA, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.

a) Hãy chỉ ra 2 đường đi từ AA đến FF và so sánh độ dài của hai đường đi đó.

b) Với mỗi đỉnh VV của sơ đồ trên Hình 2.28, ta gắn số l(V)l(V) là khoảng cách ngắn nhất để đi từ AA đến VV và gọi là nhãn vĩnh viễn của đỉnh VV. Như vậy, ta có ngay l(A)=0l(A) = 0. Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn l(B),l(C)l(B), l(C) của hai đỉnh kề với AA là B,CB, C.

Bài có hình vẽ / bảng trong sách — xem ở trang 46 · mở sách.
Hình trong bài (mô tả bằng lời):

Hình 2.28: Đồ thị có trọng số gồm 6 đỉnh A, B, C, D, E, F. A ở bên trái giữa; B ở trên bên trái, D ở trên bên phải; C ở dưới bên trái, E ở dưới bên phải; F ở bên phải giữa. Các cạnh và trọng số: A–B = 3; A–C = 1; B–D = 7; B–C = 6; C–E = 5; D–E = 10; D–F = 9; E–F = 8; hai đường chéo cắt nhau: C–D = 4 và B–E = 2.

Lời giải

### a) Hai đường đi từ AA đến FF và so sánh độ dài

Dựa vào Hình 2.28, ta chọn hai đường đi (không lặp lại đỉnh) từ AA đến FF:

- Đường đi thứ nhất: A→B→D→FA \to B \to D \to F.

Độ dài: l1=AB+BD+DF=3+7+9=19l_1 = AB + BD + DF = 3 + 7 + 9 = 19.

- Đường đi thứ hai: A→C→E→FA \to C \to E \to F.

Độ dài: l2=AC+CE+EF=1+5+8=14l_2 = AC + CE + EF = 1 + 5 + 8 = 14.

So sánh: vì 14<1914 < 19 nên l2<l1l_2 < l_1, tức đường đi thứ hai A→C→E→FA \to C \to E \to F ngắn hơn đường đi thứ nhất A→B→D→FA \to B \to D \to F.

###

b) Nhãn vĩnh viễn l(B), l(C)l(B),\ l(C)

Nhãn vĩnh viễn l(V)l(V) là khoảng cách ngắn nhất để đi từ AA đến VV. Theo giả thiết l(A)=0l(A) = 0.

Xét đỉnh CC kề với AA: cạnh nối trực tiếp AA và CC có độ dài AC=1AC = 1. Mọi đường đi khác từ AA tới CC đều phải qua BB (ngắn nhất là A→B→C=3+6=9>1A \to B \to C = 3 + 6 = 9 > 1). Do đó khoảng cách ngắn nhất từ AA đến CC là
l(C)=1.l(C) = 1.

Xét đỉnh BB kề với AA: cạnh nối trực tiếp AA và BB có độ dài AB=3AB = 3. Đường đi khác tới BB là A→C→B=1+6=7>3A \to C \to B = 1 + 6 = 7 > 3. Do đó khoảng cách ngắn nhất từ AA đến BB là
l(B)=3.l(B) = 3.

Vậy nhãn vĩnh viễn của hai đỉnh kề với AA là l(B)=3l(B) = 3 và l(C)=1l(C) = 1.

Đáp số

Hai đường đi: A→B→D→FA \to B \to D \to F dài 1919 và A→C→E→FA \to C \to E \to F dài 1414; đường thứ hai ngắn hơn (14<1914 < 19).l(B)=3l(B) = 3; l(C)=1l(C) = 1.

Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.