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

Giải Luyện tập 2 trang 44 Chuyên đề Toán 11

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

Đề bài

Đồ thị nào trong Hình 2.23 có đường đi Hamilton? Hãy chỉ ra một đường đi Hamilton của nó.

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

Hình 2.23 gồm hai đồ thị:
a) 5 đỉnh A, B ở hàng trên; E, D, C ở hàng dưới. Các cạnh: A–E, A–D, A–C (A nối tới E, D, C tạo hình chữ V), B–E, B–D, B–C (B nối tới E, D, C). Tức A và B đều nối tới cả E, D, C, tạo các đường chéo cắt nhau; các cạnh thực tế: A–E, A–C, B–E, B–D... (đồ thị hai nhánh tam giác đan chéo).
b) 4 đỉnh: A ở đỉnh trên, D ở giữa, C ở dưới trái, B ở dưới phải. Các cạnh: A–C, A–B, A–D, C–D, D–B, C–B. (A, C, B tạo tam giác ngoài, D ở trong nối với cả A, C, B).

Lời giải

Nhắc lại khái niệm. Một *đường đi Hamilton* của đồ thị là đường đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần.

### a) Đồ thị thứ nhất (5 đỉnh A,B,C,D,EA,B,C,D,E)

Theo hình, các cạnh là:
A–E, A–D, A–C, B–E, B–D, B–C.A\text{–}E,\ A\text{–}D,\ A\text{–}C,\ B\text{–}E,\ B\text{–}D,\ B\text{–}C.
Như vậy hai đỉnh A,BA,B đều nối với cả ba đỉnh C,D,EC,D,E, còn giữa AA và BB cũng như giữa các đỉnh C,D,EC,D,E không có cạnh nào (đồ thị hai phần với hai lớp {A,B}\{A,B\} và {C,D,E}\{C,D,E\}).

Ta thử đi lần lượt, xen kẽ một đỉnh ở lớp {C,D,E}\{C,D,E\} rồi một đỉnh ở lớp {A,B}\{A,B\}:
C⟶A⟶D⟶B⟶E.C \longrightarrow A \longrightarrow D \longrightarrow B \longrightarrow E.
Kiểm tra các cạnh: C–AC\text{–}A (có), A–DA\text{–}D (có), D–BD\text{–}B (có), B–EB\text{–}E (có). Đường đi này qua đủ cả 5 đỉnh, mỗi đỉnh đúng một lần.

➡️ Đồ thị a) có đường đi Hamilton, chẳng hạn C–A–D–B–EC\text{–}A\text{–}D\text{–}B\text{–}E.

*(Nhận xét thêm: đồ thị a) không có chu trình Hamilton, vì đây là đồ thị hai phần với hai lớp có số đỉnh khác nhau — nhưng ở đây chỉ yêu cầu đường đi.)*

###

b) Đồ thị thứ hai (4 đỉnh A,B,C,DA,B,C,D)

Theo hình, các cạnh là:
A–B, A–C, A–D, B–C, B–D, C–D.A\text{–}B,\ A\text{–}C,\ A\text{–}D,\ B\text{–}C,\ B\text{–}D,\ C\text{–}D.
Đây là đồ thị đầy đủ 44 đỉnh (mọi cặp đỉnh đều có cạnh nối), nên chắc chắn có đường đi Hamilton.

Chọn thứ tự:
A⟶B⟶C⟶D.A \longrightarrow B \longrightarrow C \longrightarrow D.
Kiểm tra các cạnh: A–BA\text{–}B (có), B–CB\text{–}C (có), C–DC\text{–}D (có). Đường đi này qua đủ cả 4 đỉnh, mỗi đỉnh đúng một lần.

➡️ Đồ thị

b) có đường đi Hamilton, chẳng hạn A–B–C–DA\text{–}B\text{–}C\text{–}D.

### Kết luận
Cả hai đồ thị trong Hình 2.23 đều có đường đi Hamilton.

Đáp số

Có đường đi Hamilton; ví dụ: C–A–D–B–ECó đường đi Hamilton; ví dụ: A–B–C–D

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.