Giải chuyên đề học tập Toán lớp 11 Kết nối tri thức Bài 9. Đường đi Euler và đường đi Hamilton Chuyên đề họ..

Giải mục 2 trang 43, 44 Chuyên đề học tập Toán 11 - Kết nối tri thức


Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20

Đã có lời giải SGK Toán lớp 12 - Kết nối tri thức (mới)

Đầy đủ - Chi tiết - Chính xác

Lựa chọn câu để xem lời giải nhanh hơn

Hoạt động 2

Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20. Hãy chỉ ra một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần.

Phương pháp giải:

Quan sát hình 2.20  để làm

Lời giải chi tiết:

Một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần là ta có thể đi theo thứ tự EABCD (hoặc có thể chọn ECBAD, hoặc BADCE,...).

Luyện tập 2

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

Phương pháp giải:

Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần.

Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton.

Lời giải chi tiết:

- Đồ thị Hình 2.23 a) có 5 đỉnh, trong đó đỉnh A và B đều có bậc 3, các đỉnh còn lại E, D, C đều có bậc 2 nên mỗi đỉnh đều có bậc không nhỏ hơn \(\frac{{5 - 1}}{2} = \frac{4}{2} = 2\). Do đó, theo định lí 4 (suy ra từ định lí Dirac), đồ thị này có đường đi Hamilton. Một đường đi Hamilton của đồ thị này là CBDAE.

- Đồ thị Hình 2.23 b) có 4 đỉnh, mỗi đỉnh đều có bậc là 3 nên mỗi cặp đỉnh không kề nhau bất kì đều có tổng bậc là 3 + 3 = 6 > 4. Do đó, theo định lí Ore, đồ thị này có một chu trình Hamilton nên nó có đường đi Hamilton. Một đường đi Hamilton của đồ thị này là ABCD.


Bình chọn:
4.9 trên 7 phiếu
Bài tiếp theo

>> Xem thêm

Luyện Bài Tập Trắc nghiệm Toán 11 - Kết nối tri thức - Xem ngay

Báo lỗi - Góp ý

2K7 tham gia ngay group để nhận thông tin thi cử, tài liệu miễn phí, trao đổi học tập nhé!

>> Lộ Trình Sun 2025 - 3IN1 - 1 lộ trình ôn 3 kì thi (Luyện thi TN THPT & ĐGNL; ĐGTD) tại Tuyensinh247.com. Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.

Các bài khác cùng chuyên mục


App Loigiaihay trên google play store App Loigiaihay trên apple store

Copyright © 2021 loigiaihay.com

DMCA.com Protection Status
App Loigiaihay trên apple store App Loigiaihay trên google play store

Đăng ký để nhận lời giải hay và tài liệu miễn phí

Cho phép loigiaihay.com gửi các thông báo đến bạn để nhận được các lời giải hay cũng như tài liệu miễn phí.

Đồng ý Bỏ qua